Le Tour de France P64361


Statement
 

pdf   zip

html

The organizers of Le Tour de France (the country where a Big Mac is Le Big Mac) are determined to put an end to the continuous cases of doping in the race. They have recently received the results of a detailed study, carried out by the French National Center for Scientific Research (CNRS), which will help them to determine if a cyclist taking part in the race has been using illegal substances or not.

This study draws a series of surprising conclusions:

  • The energy that cyclists use when riding comes from a substance that flows through their bodies, called cycling mana (vélo mana in French).
  • Each cyclist has a fixed amount of cycling mana M at the beginning of a stage, which depends on his personal characteristics, and which is measured with a high-precision CNRS-patented vélo-mana-mètre®.
  • Because of team orders and something that may be called cycling mana inertia, cyclists choose a certain speed at the start of each kilometer of the race, and then hold the same speed for the whole kilometer.
  • When riding downhill or in flat terrain, all cyclists ride at the same horizontal speed of 60km/h, and they use no cycling mana.
  • When riding uphill, each cyclist chooses a certain cycling mana flow x ∈ [0, 1] for the next horizontal kilometer. The time in minutes he takes to ride it is t = 6 − 5x.
  • The amount of cycling mana used is proportional to x and to the tangent of the angle α of the road during this kilometer. The exact value is Δ M = φ · x · tanα, where the magical cycling mana flow constant φ was empirically found to be, surprisingly (oh!), exactly 1.
  • No runner can spend more cycling mana during a stage than the mana remaining at the beginning of that stage. The only way to achieve it would be through doping substances (which, by the way, have been found to be against cycling universal karma).

The organizers of Le Tour are considering to implement an automatic device to shoot to kill with a sniper riffle any cyclist crossing the finish line in a time judged impossible according to the stage profile and the measured starting amount of cycling mana. Please help Le Tour to get rid of those cheaters.

Input

Input starts with the number of points 2 ≤ n ≤ 1000 of the description of the stage profile. Follow n pairs of natural numbers 0 ≤ di, hi ≤ 10000. They give, for the i-th control point, the horizontal distance in kilometers from the start of the stage, and the height above the sea level in meters, respectively. The pairs are strictly sorted by distance. The first pair corresponds to the starting line and hence has d1 = 0, whereas the last pair corresponds to the finish line. The angle of the road between two contiguous control points is constant.

After the profile description comes 0 ≤ c ≤ 50000, the number of cyclists taking part in the race. Follow c lines with a real number Mj and three natural numbers hj, mj, sj giving, for the j-th cyclist, his starting amount of cycling mana 0 ≤ Mj ≤ 200 and his time to finish the stage, decomposed in hours, minutes and seconds. Assume 0 ≤ hj ≤ 1000 and 0 ≤ mj, sj < 60.

Output

For every cyclist, print “SHOOT” or “PASS” according to whether the cyclist should be shoot for using doping substances or not. The cases have no precision issues.

Public test cases
  • Input

    2
    0 0
    10 1000
    4
    0 0 59 59
    0 1 0 1
    200 0 10 1
    200 0 9 59
    

    Output

    SHOOT
    PASS
    PASS
    SHOOT
    
  • Input

    5
    0    100
    50  3100
    150  100
    200 1100
    250 3100
    5
    0.0 12 30  0
    0.5 10  0 45
    1.5 14 20 20
    3.5  6 55 35
    7.5  5 10 15
    

    Output

    SHOOT
    SHOOT
    PASS
    SHOOT
    PASS
    
  • Information
    Author
    Edgar Gonzàlez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Setè Concurs de Programacio de la UPC - Final
    Date
    2009-09-16