Schematic path of the bird passing through the sequence of "gates"
It happened back in 2013/14 - the game Flappy Bird - experienced
sudden surge of popularity despite being extremely simple in graphics, trivial in mechanics - and insanely
difficult to play. It led to multiple reviews about unpredictability of audience behavior.
The game consists of eponymous character - small round bird, flying with constant horizontal speed from left to right (actually it is rather background scrolling in opposite direction, but it doesn't matter).
Bird is to pass an endless sequence of obstacles, reprsented by a pair of green pipes - one sticking from the "floor", another from the "ceiling" - with small gap between them.
The bird's vertical coordinate is affected by gravity - i.e. generally bird is in "free fall" mode. However when the user taps on the screen (no matter where), bird gets momentary upwards thrust. And that's all about the controls.
Game is notoriously hard to play because gaps are narrow, pipes are wide, scrolling speed (i.e. flight speed) is relatively high in relation to screen width. You can find various implementations online and try yourself.
Problem
This task wants you to calculate at which moments user should tap the screen so that bird successfully passes a number of gates. Our game is simpler - obstacles are "zero width" and you get the whole knowledge of their positions before start.
Game physics
The bird starts at X=0 and Y=1, i.e. already flying say 1 metre above ground. It's horizontal speed is
Vx=2 and remains constant. Vertical speed also is Vy=2 at the moment of start. However it diminishes
(and goes to negative) due to constant vertical acceleration (gravity force) Ay=-2. Calculations are
performed with time stamp dt=1/32 and we regard only first 30 seconds of the flight. On every "jump"
the bird's vertical speed is immediately changed to Vx=2 again. Thus main loop of simulation is like this:
T = 0
while T < 30:
# first coordinates are updated
Y = Y + Vy * dt
X = X + Vx * dt
# now vertical speed is updated either decreasing with gravity or restored by jump
if not jump(X):
Vy = Vy + Ay * dt
else:
Vy = 2
Here jump is supposed to be a function, deciding, whether bird should jump at this point (like if user taps
the screen) or not.
Input data give us a total count G of obstacles (gates) in the first line.
Next G lines contain 3 values each - X, Low and High coordinates - meaning that at the point X
there is a vertical wall with a gate allowing to fly with Y anywhere between Low and High. Actually
all gates are 0.5 meters high (i.e. High = Low + 0.5).
Answer should give a sequence of X coordinates where the bird should make jump. It should be in strictly
increasing order, normally first value is above 0 and last below 60 - i.e. no need to mention initial
jump at start.
Example
input:
9
6 2.4 2.9
14 0.93 1.43
19 2.79 3.29
25 0.85 1.35
32 1.64 2.14
37 2.39 2.89
41 0.71 1.21
46 0.33 0.83
54 2.14 2.64
answer:
2 5.75 8.5 14.25 16 16.25 19 19.375 25 29.5 30 33 33.375 39 41.5 46 49 50.25 55
Please also note as the game calculations are discrete in nature, coordinates in answer should match some of
real X positions calculated during the flight, i.e. matching Vx * dt = 2 * 1/32 = 1/16 = 0.0625 steps.