Regulations
Schedule
Organising Team
Cluj&Romania
Sponsors
Secretariat
Internet
Contest
Links
___________ Web design: Vivi

[ The rules  Read the problems  Submit solutions  Results  Downloads ] Day one problems are available here.
Day 2 [ Problem 4  Problem 5  Problem 6 ]
Problem 4 : Falling
Consider a game based on the device shown in the image below:
The device
consists in a set of horizontal platforms of various lengths, placed at
various heights. The lowest platform is the floor (it is placed at height
0 and has an infinite length).
From a given position, a ball is
released in free fall at moment 0. The ball falls at a constant speed of 1
meter per second. When the ball reaches a platform it starts rolling
towards one or the other of its edges, at the choice of the player, at the
same speed of one meter per second. When it reaches the edge of the
platform, it continues its vertical free fall. The ball is not allowed to
free fall for more then MAX meters at one time (between two platforms).
Task Write a program that finds a way to roll the ball
on the platforms so that it reaches the floor as soon as possible without
breaking.
Input File name: FALL.IN Line
1: N X Y MAX
Four integers, separated by a space: the number of platforms
(excluding the floor), the starting position of the ball (horizontal and
vertical coordinates), and the maximum allowed free fall distance; the
platforms are numbered from 1 through N. Lines 2..N+1:
X1_{i} X2_{i} H_{i}
Three integers, separated by spaces; the ith platform is
situated at height H_{i}, between horizontal coordinates
X1_{i} and X2_{i} inclusive (X1_{i} <
X2_{i}, i=1..N).
Remarks:
Ignore the ball diameter and platform thickness. If the ball falls
exactly on the edge of a platform, it is considered a fall onto that
platform.
No two platforms have points in common.
There will always be a solution for the test data.
All the dimensions are given in meters.
Output File
name: FALL.OUT Line 1: TIME
An integer: the time when the ball touches the floor, according to
your solution. The rest of the lines, to the end of the file:
P T D
Three integers, separated by spaces. The ball touches the platform P
at moment T and rolls in direction D (0 for left and 1 for right).
The impact with the floor must not appear in these lines.
The impacts must be output such that the successive values of T appear
in increasing order. Remark
If there are several solutions possible, only one is required
Limits
1 <= N <= 1000
20000 <= X1_{i}, X2_{i} <= 20000 ( i=1..N )
0 < H_{i} < Y <= 20000
Example FALL.IN FALL.OUT
3 8 17 20 23
0 10 8 2 4 1
0 10 13 1 11 1
4 14 3 3 16 1
