HAL's billiard pools P47298


pdf   zip


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 ≤ dw − 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?

(0.45, 0.2)(6.45,5.2) unit=0.8cm

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 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.


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.

Public test cases
  • Input

    6 5 3
    4 4 0
    1000 1 0


    upper left
    upper right
    lower right
  • Information
    Salvador Roura
    Official solutions
    User solutions
    Primer Concurs de Programació de la UPC - Final