Problem Statement
Ronnie is playing a billiards exhibition. The table is a rectangle with dimensions tx by ty. Points on the table have coordinates (x, y) with 0 <= x <= tx and 0 <= y <= ty. There are no pockets on the table, its boundary is solid.
Ronnie currently has only the white cue ball on the table. It is currently located at (sx, sy). Ronnie would like to make a stroke after which the cue ball will finish at (fx, fy).
While the cue ball travels, it may bounce off the sides of the table. Ronnie would like to make a stroke that will result in exactly b bounces. (If the ball hits a corner of the table, it counts as two bounces - one with each of the sides that meet in that corner.)
There can be very many possibilities to make such a stroke. Among all of them, Ronnie is only interested in the shortest ones, i.e., the ones where the total distance traveled by the ball is as short as possible. These ways to make a stroke will be called valid. (Ronnie prefers the shorter travel distance because it makes it easier to control the stroke speed.)
Even with this additional requirement, there can still be multiple valid ways in which Ronnie can play his exhibition stroke.
For each side of the table separately, determine the maximum number of times the cue ball can bounce off this side during some valid exhibition stroke made by Ronnie.
This will give you four values.
Sort them into non-decreasing order and return them in a
Definition
- Class:
- BilliardsMaster
- Method:
- play
- Parameters:
- int, int, int, int, int, int, int
- Returns:
- int[]
- Method signature:
- int[] play(int tx, int ty, int sx, int sy, int fx, int fy, int b)
- (be sure your method is public)
Notes
- Assume that the cue ball is a point.
- The cue ball always travels along a straight line and bounces off the walls according to the laws of physics (i.e., the angle at which the ball hits the side of the rectangle is the same as the angle at which it bounces off).
Constraints
- tx and ty will each be between 2 and 100, inclusive.
- sx and fx will each be between 1 and tx-1, inclusive.
- sy and fy will each be between 1 and ty-1, inclusive.
- b will be between 0 and 100,000, inclusive.
Examples
4
4
2
2
2
2
0
Returns: {0, 0, 0, 0 }
A square table. The cue ball starts in the middle and it is supposed to end back in the middle after making 0 strokes. The only valid stroke is to touch the ball with no force at all, so that it does not move.
4
4
2
2
2
2
1
Returns: {1, 1, 1, 1 }
The same situation as above, but now we want to make exactly one bounce. There are four valid ways how to make such a stroke: play the cue ball straight onto any one of the four walls of the table.
4
4
2
2
2
2
2
Returns: {1, 1, 1, 1 }
Now there are again four valid ways to play the stroke: point the cue ball at one of the corners of the table. (This is shorter than e.g. bouncing off the top and then the bottom side of the table.) For each side of the table there is a valid stroke such that the cue ball touches the side once, but there is no valid stroke such that the ball touches the same side twice.
8
4
4
2
4
2
1
Returns: {0, 0, 1, 1 }
A rectangular table. Now there are only two valid ways to make the stroke: we must bounce the ball off one of the two longer sides.
3
3
1
1
2
2
1
Returns: {1, 1, 1, 1 }
3
3
1
2
2
1
1
Returns: {1, 1, 1, 1 }
100
3
47
1
48
2
8
Returns: {0, 0, 4, 4 }
Here, there is exactly one valid exhibition stroke.
4
2
2
1
3
1
4
Returns: {0, 1, 2, 2 }
6
5
4
1
4
1
1
Returns: {0, 0, 0, 1 }
2
4
1
3
1
2
9
Returns: {1, 1, 4, 4 }
5
3
2
2
4
1
0
Returns: {0, 0, 0, 0 }
Ronnie simply plays the cue ball from where it is directly to where it should finish, without touching the sides of the table.
6
4
3
3
3
3
9
Returns: {1, 1, 3, 4 }
8
3
2
1
2
2
1
Returns: {0, 0, 1, 1 }
4
6
2
5
3
3
1
Returns: {0, 0, 0, 1 }
7
8
2
6
3
2
7
Returns: {1, 2, 2, 2 }
7
2
4
1
6
1
3
Returns: {0, 1, 1, 1 }
8
6
3
3
5
5
0
Returns: {0, 0, 0, 0 }
5
4
4
2
2
3
1
Returns: {0, 0, 0, 1 }
7
8
2
4
4
3
9
Returns: {2, 2, 2, 3 }
6
3
4
1
2
1
1
Returns: {0, 0, 0, 1 }
4
6
3
5
2
4
5
Returns: {0, 1, 2, 2 }
8
2
5
1
6
1
10
Returns: {0, 1, 5, 5 }
8
4
7
1
5
1
3
Returns: {0, 1, 1, 1 }
4
5
3
2
1
4
3
Returns: {0, 1, 1, 1 }
3
2
1
1
2
1
4
Returns: {1, 1, 1, 1 }
5
2
1
1
1
1
0
Returns: {0, 0, 0, 0 }
4
2
1
1
3
1
3
Returns: {1, 1, 1, 1 }
8
8
7
4
5
4
9
Returns: {2, 2, 2, 3 }
6
2
1
1
2
1
10
Returns: {0, 1, 5, 5 }
8
2
5
1
6
1
6
Returns: {0, 1, 3, 3 }
2
2
1
1
1
1
3
Returns: {1, 1, 1, 1 }
6
7
5
2
5
5
4
Returns: {1, 1, 1, 2 }
6
8
5
1
5
4
5
Returns: {1, 1, 1, 2 }
6
2
1
1
4
1
4
Returns: {0, 1, 2, 2 }
6
8
4
5
2
1
8
Returns: {2, 2, 2, 2 }
2
5
1
1
1
1
4
Returns: {0, 1, 2, 2 }
8
7
4
5
1
2
5
Returns: {1, 1, 1, 2 }
8
4
2
2
1
3
12869
Returns: {1287, 1288, 5147, 5147 }
7
5
4
3
6
1
73426
Returns: {12403, 12403, 24310, 24310 }
3
8
2
1
2
5
63266
Returns: {3900, 3901, 27732, 27733 }
5
2
1
1
3
1
54014
Returns: {3725, 3725, 23282, 23282 }
8
7
2
6
6
1
13458
Returns: {2918, 2918, 3811, 3811 }
6
8
3
4
3
5
47201
Returns: {8496, 8496, 15105, 15105 }
8
2
7
1
7
1
47255
Returns: {1390, 1391, 22237, 22237 }
2
4
1
2
1
2
27605
Returns: {2761, 2761, 11042, 11042 }
4
3
2
2
2
2
41609
Returns: {7490, 7490, 13314, 13315 }
8
7
1
2
5
4
80
Returns: {17, 17, 23, 23 }
5
56
4
34
4
40
66890
Returns: {264, 265, 33180, 33181 }
39
15
20
2
11
7
72063
Returns: {4643, 4643, 31388, 31389 }
65
56
31
33
34
21
86358
Returns: {18395, 18395, 24784, 24784 }
4
79
3
49
3
76
95664
Returns: {122, 123, 47709, 47710 }
78
90
60
79
72
23
94730
Returns: {20316, 20317, 27048, 27049 }
91
50
6
12
79
12
90886
Returns: {10538, 10538, 34905, 34905 }
11
64
7
4
4
30
61528
Returns: {883, 883, 29881, 29881 }
78
52
1
40
18
48
54770
Returns: {8426, 8427, 18958, 18959 }
73
51
1
25
64
48
79826
Returns: {13091, 13091, 26822, 26822 }
82
49
16
33
52
7
55638
Returns: {7320, 7320, 20499, 20499 }
55
54
36
7
40
12
93589
Returns: {22968, 22968, 23826, 23827 }
65
62
57
39
12
26
84374
Returns: {20098, 20098, 22089, 22089 }
66
43
56
13
41
26
54888
Returns: {8178, 8179, 19265, 19266 }
18
93
16
43
4
33
81815
Returns: {1477, 1478, 39430, 39430 }
13
47
1
26
10
6
89423
Returns: {3177, 3178, 41534, 41534 }
30
68
21
27
17
33
96744
Returns: {7881, 7882, 40490, 40491 }
99
41
65
39
15
36
54092
Returns: {3959, 3960, 23086, 23087 }
38
94
12
63
16
52
90017
Returns: {6322, 6322, 38686, 38687 }
62
2
38
1
39
1
90980
Returns: {47, 48, 45443, 45443 }
72
49
14
22
9
11
88658
Returns: {14032, 14033, 30296, 30297 }
15
32
14
28
3
3
59287
Returns: {5340, 5340, 24303, 24304 }
67
23
22
3
12
5
88607
Returns: {4671, 4671, 39632, 39633 }
52
46
8
27
19
36
91978
Returns: {20189, 20190, 25799, 25800 }
30
88
12
12
21
41
56679
Returns: {2950, 2951, 25389, 25389 }
6
27
5
5
3
3
70927
Returns: {1669, 1670, 33794, 33794 }
100
93
85
55
65
70
87524
Returns: {20295, 20296, 23466, 23467 }
98
100
88
46
67
67
77885
Returns: {19078, 19078, 19864, 19865 }
83
58
56
44
53
47
82155
Returns: {13477, 13477, 27600, 27601 }
4
26
2
2
3
14
56626
Returns: {655, 655, 27658, 27658 }
58
100
38
16
7
43
78649
Returns: {9898, 9899, 29426, 29426 }
96
9
43
3
86
7
80723
Returns: {351, 352, 40010, 40010 }
96
68
61
67
16
30
63015
Returns: {10527, 10527, 20980, 20981 }
82
5
70
4
42
2
94262
Returns: {175, 175, 46956, 46956 }
22
39
3
4
20
20
52897
Returns: {6384, 6385, 20064, 20064 }
84
81
1
33
45
25
86405
Returns: {20816, 20816, 22386, 22387 }
29
49
12
9
7
29
90382
Returns: {11723, 11723, 33468, 33468 }
6
96
3
78
3
54
57261
Returns: {111, 112, 28519, 28519 }
56
55
23
49
32
17
52975
Returns: {13005, 13006, 13482, 13482 }
94
74
93
63
30
35
76576
Returns: {14650, 14650, 23638, 23638 }
9
5
7
2
7
3
84091
Returns: {9916, 9917, 32129, 32129 }
100
100
1
1
1
1
2
Returns: {0, 0, 1, 1 }
100
3
47
1
48
2
100000
Returns: {45, 45, 49955, 49955 }
100
100
33
44
55
67
100000
Returns: {25000, 25000, 25000, 25000 }
100
100
1
1
1
1
100000
Returns: {25000, 25000, 25001, 25001 }
57
43
1
2
1
2
1
Returns: {0, 0, 0, 1 }
100
100
50
1
50
1
1
Returns: {0, 0, 0, 1 }