Problem Statement
You are going to play a hole of golf. The golf course is a horizontal plane. The ball is a point and the hole is also a point. Everything in this problem is continuous: distances are real numbers and points have real coordinates.
The distance from the tee (i.e., the point where you start) to the hole is exactly D meters.
You are extremely good at golf: you can position your shots exactly. However, you are limited by the golf clubs you have. For each club you know the range of distances at which you can be exact.
You are given the information on your clubs in the
For example, if you have a club that works for the interval [4,7], this means that you can use this club to move the ball from its current point A to any point B of the plane such that the distance between A and B is between 4 and 7 meters, inclusive.
Compute and return the minimal number of strokes in which you can get the ball from the tee into the hole.
Definition
- Class:
- OptimalGolf
- Method:
- minStrokes
- Parameters:
- int, int[], int[]
- Returns:
- int
- Method signature:
- int minStrokes(int D, int[] clubLo, int[] clubHi)
- (be sure your method is public)
Notes
- The last stroke must end with the ball exactly reaching the hole. It is not enough if the trajectory of the stroke passes through the hole.
Constraints
- D will be between 1 and 1000, inclusive.
- clubLo will have between 1 and 5 elements, inclusive.
- clubHi will have the same number of elements as clubLo.
- For each i, we will have 1 <= clubLo[i] <= clubHi[i] <= 1000.
Examples
7
{1}
{1}
Returns: 7
The hole is 7 meters away from the tee. The only club we have is exact only at the distance of 1 meter. The optimal way to play the hole is to make 7 strokes, each time moving the ball exactly 1 meter in the direction of the hole.
7
{2}
{2}
Returns: 4
Now the only club we have can only be used for the distance of exactly 2 meters. If we were to hit the ball exactly towards the hole each time, during the fourth stroke the ball would pass over the hole to its other side. However, it is possible to get the ball exactly to the hole in four strokes if we are smart and play some of the strokes sideways. If we assume that the tee is at (0,0) and the hole at (7,0), one way of playing this hole is to hit the ball from (0,0) to (1.5,sqrt(7/4)), from there to (3.5,sqrt(7/4)), from there to (5.5,sqrt(7/4)), and finally from that point to (7,0). We can easily verify that each of these four strokes moves the ball by exactly 2 meters.
470
{100, 400, 600}
{200, 500, 700}
Returns: 1
We can use the middle club to get a hole-in-one.
47
{5, 4, 2}
{5, 7, 10}
Returns: 5
Here we can play straight towards the hole. For example, we can use the third club to hit the ball 10 meters four times, and then the second club to hit it the last 7 meters. Alternately, we can use the third club five times, moving the ball 10, 10, 10, 9.1, and 7.9 meters towards the hole.
1
{1}
{1000}
Returns: 1
3
{7}
{100}
Returns: 2
441
{8, 6, 5}
{9, 10, 9}
Returns: 45
631
{6, 4, 1, 34}
{54, 85, 14, 62}
Returns: 8
940
{6, 4, 4, 6, 4}
{10, 7, 9, 9, 8}
Returns: 94
384
{705}
{734}
Returns: 2
351
{572, 201, 245}
{589, 781, 808}
Returns: 1
342
{2}
{6}
Returns: 57
521
{33, 13, 30, 28, 61}
{70, 84, 90, 43, 96}
Returns: 6
620
{46}
{87}
Returns: 8
829
{5, 6, 1}
{9, 9, 10}
Returns: 83
577
{51, 34, 29, 15}
{100, 94, 67, 78}
Returns: 6
498
{33, 20}
{78, 72}
Returns: 7
175
{2, 2, 9, 8}
{9, 5, 10, 9}
Returns: 18
941
{5, 34, 78, 67}
{98, 78, 83, 87}
Returns: 10
654
{818, 323, 23, 217}
{975, 850, 591, 249}
Returns: 1
982
{24, 23, 17}
{89, 61, 26}
Returns: 12
748
{6}
{10}
Returns: 75
111
{35, 1, 16, 9, 3}
{57, 84, 54, 48, 34}
Returns: 2
186
{8}
{9}
Returns: 21
541
{59, 2}
{73, 73}
Returns: 8
856
{3}
{9}
Returns: 96
888
{48, 241, 63}
{899, 637, 730}
Returns: 1
23
{2, 1, 4, 9}
{5, 9, 5, 10}
Returns: 3
594
{280, 634}
{781, 879}
Returns: 1
577
{6, 1, 2, 6, 5}
{8, 9, 7, 7, 10}
Returns: 58
144
{66, 120, 473, 669}
{995, 521, 925, 806}
Returns: 1
446
{9, 2, 8, 2}
{10, 5, 9, 4}
Returns: 45
171
{3, 13, 59}
{60, 76, 86}
Returns: 2
654
{70, 89, 4, 25}
{88, 89, 72, 87}
Returns: 8
791
{5, 7, 2}
{9, 8, 2}
Returns: 88
605
{489, 551, 371, 320, 422}
{614, 763, 810, 593, 789}
Returns: 1
648
{94, 106}
{962, 525}
Returns: 1
977
{43, 14, 12}
{69, 47, 80}
Returns: 13
52
{45, 8, 35, 27}
{75, 51, 82, 33}
Returns: 1
477
{5, 6, 1}
{8, 8, 3}
Returns: 60
1
{4, 59, 57, 33, 14}
{55, 67, 79, 38, 39}
Returns: 2
434
{6}
{8}
Returns: 55
516
{9, 5, 1, 7}
{10, 6, 9, 10}
Returns: 52
714
{610, 639, 473, 184, 699}
{707, 940, 632, 572, 719}
Returns: 1
186
{3, 2, 7, 1}
{10, 10, 8, 4}
Returns: 19
953
{7, 1, 2, 7}
{10, 10, 3, 9}
Returns: 96
512
{59}
{95}
Returns: 6
126
{411, 89, 431}
{524, 105, 809}
Returns: 2
107
{633, 180, 511, 450}
{873, 926, 682, 488}
Returns: 2
405
{9, 6, 4, 2, 3}
{9, 7, 6, 7, 8}
Returns: 45
665
{108, 498, 95}
{259, 810, 998}
Returns: 1
405
{2, 4, 4}
{10, 10, 9}
Returns: 41
731
{40, 65, 15, 8, 23}
{98, 78, 72, 37, 93}
Returns: 8
248
{415, 8, 604, 410}
{626, 486, 894, 624}
Returns: 1
984
{384, 807}
{568, 821}
Returns: 2
66
{21}
{76}
Returns: 1
865
{2}
{3}
Returns: 289
173
{170, 80}
{737, 95}
Returns: 1
404
{357, 125}
{883, 985}
Returns: 1
563
{29, 45, 12, 41}
{82, 87, 99, 83}
Returns: 6
207
{3}
{9}
Returns: 23
854
{6, 9, 6}
{7, 9, 10}
Returns: 86
436
{450, 447, 424, 24, 200}
{654, 693, 746, 503, 992}
Returns: 1
615
{2, 8, 2}
{7, 10, 2}
Returns: 62
757
{8, 24, 53}
{43, 97, 86}
Returns: 8
937
{531, 487, 123, 945}
{949, 710, 529, 955}
Returns: 1
643
{1, 6}
{9, 8}
Returns: 72
168
{297, 49}
{793, 75}
Returns: 2
46
{80, 1, 33, 25, 28}
{83, 86, 45, 72, 48}
Returns: 1
208
{8, 1, 5}
{10, 5, 10}
Returns: 21
433
{6, 5, 1, 4}
{7, 8, 10, 8}
Returns: 44
60
{4, 25, 47}
{51, 99, 54}
Returns: 1
354
{6, 2, 2, 2, 3}
{10, 8, 8, 5, 4}
Returns: 36
484
{26, 1}
{38, 15}
Returns: 13
835
{13, 219, 382, 483, 220}
{258, 547, 546, 939, 987}
Returns: 1
934
{5, 76, 42}
{87, 83, 54}
Returns: 11
7
{1 }
{1 }
Returns: 7
5
{2, 9 }
{3, 10 }
Returns: 2
8
{2, 9 }
{2, 10 }
Returns: 2
7
{2 }
{2 }
Returns: 4
10
{3, 2 }
{6, 5 }
Returns: 2
100
{1000 }
{1000 }
Returns: 2