Problem Statement
There is a farm. The farm is an infinite horizontal chessboard. Cells of the chessboard have integer coordinates (r, c).
There is a corral for the horses. The corral is the rectangle consisting of all cells (r, c) such that 0 <= r <= R and 0 <= c <= C.
There are horses inside the corral. Currently, each cell (r, c) such that R1 <= r <= R2 and C1 <= c <= C2 contains one horse.
The horses are completely independent of each other. I.e., arbitrarily many horses may share the same cell without influencing each other.
All horses have decided to escape the corral.
There is only one cowboy around. His job is to catch all horses before any one of them gets out.
The cowboy can repeatedly use his lasso to catch and tie up a horse. This takes L seconds, regardless of where the horse is located. (L may be non-integer.) Once a horse has been tied up, it can no longer escape.
We can view the entire commotion as a turn-based process:
- The process starts at time 0.
- At positive integer multiples of L (i.e., at times L, 2L, 3L, ...) the cowboy gets his turn and catches one of the horses. The cowboy gets to choose which horse he catches.
- At positive integer times (i.e., at times 1, 2, 3, ...) the horses get their turn. As you might expect, each horse moves like a chess knight (see Notes).
- During each of the horses' turns each horse that still hasn't been caught makes exactly one move. Naturally, each horse tries to leave the corral as quickly as possible. A horse has escaped if its move ends on a cell outside the corral.
- If the cowboy and the horses should have their turns at the exact same moment in time, the cowboy's action is evaluated first.
Find and return the largest positive real L such that the cowboy can still guarantee (by using a good strategy) that he will catch all the horses before any one of them can escape.
Definition
- Class:
- Lasso
- Method:
- lasso
- Parameters:
- int, int, int, int, int, int
- Returns:
- double
- Method signature:
- double lasso(int R, int C, int R1, int C1, int R2, int C2)
- (be sure your method is public)
Notes
- In a single move, a chess knight always jumps in such a way that one of its coordinates changes by 2 and the other changes by 1. For example, a knight at (4, 7) may jump to (6, 8), (6, 6), (3, 9), (3, 5), or four other cells.
- Your return value may have an absolute or a relative error at most 10^(-9).
Constraints
- 0 <= R1 <= R2 <= R <= 1000.
- 0 <= C1 <= C2 <= C <= 1000.
Examples
0
0
0
0
0
0
Returns: 1.0
The corral is a single cell with a single horse. The cowboy must act before the horse to catch it.
4
4
2
2
2
2
Returns: 2.0
The corral is a 5x5 cell square with a single horse on the middle cell. The horse will escape if it gets a second turn, so the cowboy must act before that.
3
2
0
0
2
1
Returns: 0.16666666666666666
The corral is a 4x3 rectangle. In the corral there are six horses forming a 3x2 rectangle. Each horse can escape the corral in a single move, so the cowboy must catch all of them before they get their first move.
4
4
2
2
2
3
Returns: 1.0
Here the cowboy's strategy matters. He should catch the horse that starts at (2, 3) before the horse that starts at (2, 2). In the slowest valid solution the cowboy catches the first horse at time 1, then also at time 1 the second horse moves - e.g., to (3, 4) - and then at time 2 the cowboy catches that second horse just before it can escape the corral.
4
4
2
2
2
4
Returns: 0.5
4
7
1
1
3
6
Returns: 0.07142857142857142
8
8
4
4
4
7
Returns: 0.6666666666666666
6
8
3
4
4
5
Returns: 0.5
6
9
0
0
6
6
Returns: 0.029411764705882353
0
4
0
2
0
4
Returns: 0.3333333333333333
3
8
2
0
3
3
Returns: 0.125
5
9
2
3
4
9
Returns: 0.09090909090909091
0
2
0
1
0
2
Returns: 0.5
8
4
1
1
3
2
Returns: 0.25
1
6
1
6
1
6
Returns: 1.0
8
4
5
0
8
4
Returns: 0.05555555555555555
9
6
4
1
8
6
Returns: 0.05555555555555555
10
3
6
1
7
2
Returns: 0.25
2
8
0
1
2
4
Returns: 0.08333333333333333
9
8
6
0
7
5
Returns: 0.16666666666666666
10
9
8
5
10
7
Returns: 0.16666666666666666
9
3
3
1
5
3
Returns: 0.1111111111111111
3
2
0
2
1
2
Returns: 0.5
6
1
2
0
3
0
Returns: 0.5
5
0
0
0
2
0
Returns: 0.3333333333333333
7
3
7
0
7
0
Returns: 1.0
2
8
1
0
2
3
Returns: 0.125
9
4
0
0
1
2
Returns: 0.16666666666666666
7
6
2
4
4
6
Returns: 0.16666666666666666
10
8
0
1
8
6
Returns: 0.0392156862745098
7
10
1
1
2
8
Returns: 0.1111111111111111
10
3
6
0
9
2
Returns: 0.08333333333333333
10
4
3
1
5
2
Returns: 0.3333333333333333
4
10
2
8
3
10
Returns: 0.2
3
6
0
2
2
6
Returns: 0.06666666666666667
9
4
1
4
8
4
Returns: 0.125
8
7
3
1
6
1
Returns: 0.25
7
9
5
1
5
1
Returns: 1.0
9
8
0
0
5
6
Returns: 0.045454545454545456
7
7
3
3
4
7
Returns: 0.2
7
10
5
0
7
10
Returns: 0.038461538461538464
10
3
0
3
6
3
Returns: 0.14285714285714285
7
7
1
1
4
2
Returns: 0.2
10
9
3
8
8
9
Returns: 0.08333333333333333
3
9
1
0
3
6
Returns: 0.047619047619047616
5
4
3
0
3
1
Returns: 0.5
9
3
2
0
9
3
Returns: 0.03125
10
10
5
1
10
8
Returns: 0.047619047619047616
4
9
3
1
4
9
Returns: 0.05555555555555555
10
10
7
1
9
6
Returns: 0.1111111111111111
8
9
3
1
5
6
Returns: 0.125
10
8
10
1
10
4
Returns: 0.25
4
8
0
1
3
3
Returns: 0.1
6
7
5
1
6
4
Returns: 0.125
3
7
1
3
3
6
Returns: 0.08333333333333333
3
9
1
1
2
5
Returns: 0.1
4
6
0
1
1
4
Returns: 0.125
5
4
0
3
1
4
Returns: 0.25
4
9
2
3
4
5
Returns: 0.16666666666666666
8
4
0
1
3
4
Returns: 0.07142857142857142
4
8
3
5
4
8
Returns: 0.125
9
10
6
0
6
7
Returns: 0.25
8
3
1
0
6
3
Returns: 0.041666666666666664
8
9
0
2
5
6
Returns: 0.07142857142857142
10
4
3
0
3
4
Returns: 0.25
5
5
0
0
2
5
Returns: 0.0625
7
3
0
1
4
2
Returns: 0.1
8
8
2
0
3
7
Returns: 0.125
7
7
1
6
6
6
Returns: 0.16666666666666666
10
7
0
3
9
7
Returns: 0.034482758620689655
3
3
1
2
3
3
Returns: 0.16666666666666666
8
8
1
1
7
7
Returns: 0.041666666666666664
5
6
1
3
3
6
Returns: 0.125
3
4
0
1
2
4
Returns: 0.08333333333333333
10
6
5
0
6
5
Returns: 0.16666666666666666
9
8
5
0
8
1
Returns: 0.125
3
6
0
4
0
6
Returns: 0.3333333333333333
9
10
1
4
3
10
Returns: 0.09090909090909091
9
8
0
4
1
4
Returns: 0.5
10
10
5
1
6
4
Returns: 0.3333333333333333
9
8
1
2
6
6
Returns: 0.07142857142857142
3
6
1
0
1
0
Returns: 1.0
9
9
2
2
9
6
Returns: 0.05555555555555555
10
7
10
1
10
2
Returns: 0.5
6
5
0
0
0
1
Returns: 0.5
5
7
4
6
4
7
Returns: 0.5
3
5
1
0
1
1
Returns: 0.5
917
929
291
495
631
919
Returns: 0.0013835881571072125
826
666
471
316
501
619
Returns: 0.017720713073005094
419
771
230
13
310
187
Returns: 0.005921959925367081
438
827
249
501
403
749
Returns: 0.0023789662310377854
417
351
191
154
284
157
Returns: 0.21010638297872342
403
852
18
638
192
781
Returns: 0.0032744947556919927
538
275
145
51
478
200
Returns: 0.001377245508982036
855
903
675
110
789
607
Returns: 0.0015833362654375286
34
376
9
0
21
133
Returns: 0.005166475315729047
359
163
20
105
317
123
Returns: 0.005298481102084069
734
331
151
131
272
169
Returns: 0.01744430432955023
418
672
57
180
105
636
Returns: 0.0023668110570267496
900
236
288
62
680
117
Returns: 0.0026808433296982917
712
784
349
159
540
540
Returns: 0.002386879484551179
369
114
74
29
90
72
Returns: 0.03877005347593583
552
865
328
654
540
810
Returns: 0.0025230225810521003
654
554
210
41
652
255
Returns: 0.0011690879394825066
374
960
88
501
194
623
Returns: 0.007142314413798344
955
750
743
174
922
197
Returns: 0.02285579641847314
412
823
342
54
372
480
Returns: 0.0027196494674019793
334
561
38
97
276
265
Returns: 0.0020601674546366975
141
870
53
280
131
611
Returns: 0.0013691128148959474
398
890
56
366
130
566
Returns: 0.004370041683474519
122
384
47
115
83
272
Returns: 0.005302771125555936
297
256
164
19
291
106
Returns: 0.0038429865495470767
303
456
58
74
166
303
Returns: 0.0030315117670522535
187
903
66
96
87
280
Returns: 0.010810810810810811
301
212
19
156
138
166
Returns: 0.02196969696969697
222
203
126
19
174
126
Returns: 0.008704453441295546
390
664
11
153
335
607
Returns: 6.472491909385113E-4
108
908
38
225
53
873
Returns: 0.0026001540832049307
423
769
44
219
97
657
Returns: 0.0020669872606091286
649
896
228
91
561
568
Returns: 0.0010178308892826178
429
316
161
46
191
60
Returns: 0.06666666666666667
708
321
216
44
465
60
Returns: 0.007294117647058823
548
680
348
60
495
224
Returns: 0.0036358127556430845
326
315
135
30
194
303
Returns: 0.0046776232616940585
77
262
58
112
64
262
Returns: 0.00946073793755913
523
496
290
223
326
264
Returns: 0.07528957528957529
254
624
174
336
218
584
Returns: 0.0036376864314296106
749
314
42
15
63
17
Returns: 0.13636363636363635
811
722
203
351
227
401
Returns: 0.08941176470588236
706
985
335
381
361
402
Returns: 0.29797979797979796
289
260
100
237
163
238
Returns: 0.09375
811
560
642
439
646
502
Returns: 0.190625
376
441
38
130
43
189
Returns: 0.06111111111111111
726
491
247
93
254
98
Returns: 1.0416666666666667
471
335
12
182
16
185
Returns: 0.45
109
745
96
542
102
571
Returns: 0.03333333333333333
341
565
206
453
214
454
Returns: 3.1666666666666665
291
353
272
268
273
328
Returns: 0.08196721311475409
202
671
150
165
151
196
Returns: 0.421875
262
906
99
570
102
622
Returns: 0.24528301886792453
791
972
345
537
357
549
Returns: 1.0591715976331362
219
326
62
229
67
230
Returns: 2.8333333333333335
853
831
331
641
332
686
Returns: 1.0434782608695652
196
911
35
766
40
772
Returns: 0.5
268
180
52
73
54
94
Returns: 0.42424242424242425
142
921
70
101
75
102
Returns: 3.0
405
300
69
124
100
144
Returns: 0.07589285714285714
1000
1000
0
0
1000
1000
Returns: 1.2512512512512512E-4
1000
1000
500
500
500
500
Returns: 251.0
1000
999
101
199
499
702
Returns: 0.001102202119883041
100
100
0
6
47
27
Returns: 0.011904761904761904
1000
1000
3
0
3
12
Returns: 0.15384615384615385
10
10
1
1
6
6
Returns: 0.07407407407407407