HAL's billiard pools P47298
HAL (the super-computer of ‘2001: A Space Odissey’ and the sequel ‘2010: The Year We Make Contact’) didn’t die after all. It reached a far galaxy and used its super-intelligence to build a big empire. HAL has now a planet-sized palace with a huge, thousands of kilometers long playing room.
Since HAL enjoys playing billiard, it has many billiard pools. Every pool has four holes, one at every corner: lower left, lower right, upper left and upper right. The width w of each pool is more or less normal: it can be at most 20 meters. The length ℓ of each pool is at least equal to w, but can be as enormous as 105 kilometers.
HAL always hits the ball (of diminishable size) from the left side, standing at a distance d (0 ≤ d ≤ w − 1) of the lower left corner, and in an upper-right direction of 45 degrees with respect to the left side, as can be seen in the example with ℓ = 6, w = 5 and d = 3.
Before hitting the ball, HAL wants to know if the ball will keep rebounding in the pool forever (assuming there is no resistance), or if it will eventually fall into some corner (and which one). Can you help HAL?
linecolor=lightgray linewidth=.4pt (1,1)0.5090 (1,1)(1.5,1)(1,1.5) (7,1)0.590180 (7,1)(6.5,1)(7,1.5) (1,6)0.5270360 (1,6)(1.5,6)(1,5.5) (7,6)0.5180270 (7,6)(6.5,6)(7,5.5)
linecolor=black linewidth=1pt (1,1)(7,1) (7,1)(7,6) (7,6)(1,6) (1,6)(1,1)
linewidth=.4pt [linestyle=dotted](1,2)(7,2) [linestyle=dotted](1,3)(7,3) [linestyle=dotted](1,4)(7,4) [linestyle=dotted](1,5)(7,5) [linestyle=dotted](2,1)(2,6) [linestyle=dotted](3,1)(3,6) [linestyle=dotted](4,1)(4,6) [linestyle=dotted](5,1)(5,6) [linestyle=dotted](6,1)(6,6) [linestyle=dashed,arrowscale=3]->(1,4)(3,6) [linestyle=dashed,arrowscale=3]->(3,6)(7,2) [linestyle=dashed,arrowscale=3]->(7,2)(6,1) [linestyle=dashed,arrowscale=3]->(6,1)(1,6)
Input
Input consists of several cases. Each case has three integers ℓ, w and d describing the length of the pool, the width of the pool and the initial location of the ball, respectively. Both ℓ and w are strictly positive. All the distances are given in meters.
Output
For each case, print a line with the corresponding answer: “never”, if the ball will never reach a corner; otherwise print “lower left”, “lower right”, “upper left” or “upper right” as required.
Input
6 5 3 4 4 0 1000 1 0
Output
upper left upper right lower right
- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++