Statistics

Problem Statement for "NCushion"

Problem Statement

Note to plugin users: There are images in this problem statement, please use the applet to view them

Three cushion billiards is a form of Carombole, a French game of billiards. The game is played on a standard billiard table with no pockets, and with three balls: two white cue balls and one red ball. Each player must hit his/her own cue ball such that it hits at least three cushions (or sides), the opponent's cue ball, and the red ball. The cue ball can hit the cushions and the other two balls in any order, but it must hit the cushions before the last ball is hit. These cushions need not be different. For example, you could hit one cushion, then the opposite, then hit the first cushion again, and this counts as 3 cushions.

We're going to invent a new game called N-Cushion billiards, where you only have to hit your opponent's cue ball (there is no red ball), but the number of cushions you must hit before hitting the opponent's ball can be up to 500. In the original game, you could hit more than three cushions, but in this game, you must hit the specified number of cushions exactly.

When a ball bounces off a cushion, the path the ball takes is very similar to light reflecting off a mirror. The image below shows a ball (in red) "reflecting" off a cushion. Notice how the angle of incidence (designated by the α symbol) is the same on both sides of the reflection.

When a ball goes exactly into a corner, the ball hits both cushions simultaneously (this counts as hitting two cushions), and reflects back exactly in the opposite direction.

Our coordinate system is going to be in millimeters, and points will be written as (X,Y). The table is 2 meters by 1 meter, with the long side lying on the X-axis. The lower left corner is given the coordinate (0,0) and the upper right corner is given the coordinate (2000,1000). You will be given two coordinates in a int[] cue representing your ball, and a int[] opponent representing your opponent's ball. Each int[] will contain exactly 2 elements, the first being the X position, and the second being the Y position. Finally, you will be given an int N, which is the number of cushions your ball must hit before htting the opponent's ball. Your method must return the number of different directions in which you can hit your ball so that it hits the given number of cushions and finally hits the opponent's ball. For the purposes of this problem, assume the balls have no physical size, but are just points in space -- this means your ball must hit the other ball dead on in order to hit it. Remember that your ball cannot pass through the other ball in order to hit the correct number of cushions (see Example 1).

Definition

Class:
NCushion
Method:
numShots
Parameters:
int[], int[], int
Returns:
int
Method signature:
int numShots(int[] cue, int[] opponent, int N)
(be sure your method is public)

Notes

  • Assume there is no spin possible, and you cannot jump the ball.
  • Assume there is no friction, so your ball does not slow down, and can always hit the required number of cushions.

Constraints

  • cue will contain exactly two elements.
  • opponent will contain exactly two elements.
  • cue[0] and opponent[0] will be between 1 and 1999, inclusive.
  • cue[1] and opponent[1] will be between 1 and 999, inclusive.
  • cue and opponent will not contain the exact same coordinates.
  • N will be between 0 and 500, inclusive.

Examples

  1. {100,100}

    {1900,900}

    1

    Returns: 4

    It is possible to hit the opponent's ball by bouncing yours off any of the four cushions first.

  2. {100,100}

    {1900,100}

    1

    Returns: 3

    It is possible to bounce your ball off the left, bottom, or top cushions, but in order to bounce it off of the right cushion, you would have to hit the ball through the opponent's ball.

  3. {500,500}

    {1500,500}

    2

    Returns: 6

    The 6 different shots are shown below. The black filled circle is your ball's starting position, the white filled circle is the opponent's ball, and each colored line is a shot which bounces off of two cushions before hitting the other ball.

  4. {1222,440}

    {276,566}

    445

    Returns: 1779

    A reasonably large example.

  5. {500,500}

    {1500,500}

    500

    Returns: 1484

  6. {20,25}

    {40,50}

    2

    Returns: 8

    Don't forget the case where you hit the ball directly into the corner, that counts as hitting two cushions.

  7. {5,15}

    {1922,670}

    0

    Returns: 1

  8. {1864,973}

    {1136,27}

    500

    Returns: 1790

    **** Added by vorthys: A large number of steps for my soln. ****

  9. {1838,906}

    {878,906}

    500

    Returns: 1956

    **** Added by vorthys: A large number of steps for my soln. ****

  10. {288,486}

    {1712,14}

    500

    Returns: 1788

    **** Added by vorthys: A large number of steps for my soln. ****

  11. {479,953}

    {1279,553}

    500

    Returns: 1924

    **** Added by vorthys: A large number of steps for my soln. ****

  12. {575,552}

    {1053,523}

    500

    Returns: 2000

    **** Added by vorthys: Is 2000 the max output? ****

  13. {801, 1}

    {1, 1}

    404

    Returns: 1614

  14. {1001, 1}

    {1, 1}

    296

    Returns: 1182

  15. {1201, 1}

    {1, 1}

    411

    Returns: 1642

  16. {1998, 1}

    {1, 1}

    462

    Returns: 1846

  17. {802, 1}

    {2, 1}

    364

    Returns: 1412

  18. {1002, 1}

    {2, 1}

    337

    Returns: 1346

  19. {1202, 1}

    {2, 1}

    179

    Returns: 714

  20. {1330, 1}

    {2, 1}

    423

    Returns: 1689

  21. {1996, 1}

    {2, 1}

    103

    Returns: 409

  22. {803, 1}

    {3, 1}

    7

    Returns: 26

  23. {1003, 1}

    {3, 1}

    104

    Returns: 388

  24. {1203, 1}

    {3, 1}

    86

    Returns: 342

  25. {1994, 1}

    {3, 1}

    88

    Returns: 322

  26. {804, 1}

    {4, 1}

    362

    Returns: 1338

  27. {1004, 1}

    {4, 1}

    451

    Returns: 1802

  28. {1204, 1}

    {4, 1}

    221

    Returns: 882

  29. {1992, 1}

    {4, 1}

    415

    Returns: 1658

  30. {793, 1}

    {5, 1}

    245

    Returns: 978

  31. {805, 1}

    {5, 1}

    65

    Returns: 258

  32. {1005, 1}

    {5, 1}

    276

    Returns: 1040

  33. {1205, 1}

    {5, 1}

    99

    Returns: 394

  34. {1325, 1}

    {5, 1}

    312

    Returns: 1246

  35. {1990, 1}

    {5, 1}

    352

    Returns: 1289

  36. {806, 1}

    {6, 1}

    242

    Returns: 924

  37. {1006, 1}

    {6, 1}

    483

    Returns: 1930

  38. {1206, 1}

    {6, 1}

    263

    Returns: 1049

  39. {1988, 1}

    {6, 1}

    66

    Returns: 261

  40. {807, 1}

    {7, 1}

    284

    Returns: 1102

  41. {1007, 1}

    {7, 1}

    145

    Returns: 578

  42. {1207, 1}

    {7, 1}

    102

    Returns: 394

  43. {1892, 438}

    {992, 738}

    332

    Returns: 1318

  44. {577, 867}

    {753, 999}

    240

    Returns: 958

  45. {38, 216}

    {836, 221}

    50

    Returns: 197

  46. {1122, 994}

    {1934, 274}

    375

    Returns: 1495

  47. {1215, 334}

    {1377, 994}

    234

    Returns: 931

  48. {206, 757}

    {1646, 207}

    324

    Returns: 1291

  49. {718, 465}

    {1746, 949}

    441

    Returns: 1759

  50. {1060, 903}

    {644, 147}

    491

    Returns: 1959

  51. {69, 439}

    {113, 439}

    147

    Returns: 582

  52. {1968, 581}

    {1792, 389}

    294

    Returns: 1171

  53. {953, 198}

    {173, 250}

    476

    Returns: 1899

  54. {1968, 940}

    {424, 276}

    409

    Returns: 1631

  55. {611, 103}

    {157, 71}

    197

    Returns: 783

  56. {1526, 993}

    {1654, 641}

    156

    Returns: 619

  57. { 1861, 971 }

    { 1139, 29 }

    500

    Returns: 1789

  58. { 1873, 975 }

    { 1127, 25 }

    500

    Returns: 1788

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: