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:
X1i X2i Hi
Three integers, separated by spaces; the i-th platform is
situated at height Hi, between horizontal coordinates
X1i and X2i inclusive (X1i <
X2i, 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 <= X1i, X2i <= 20000 ( i=1..N )
0 < Hi < 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
|