Home I n t e r n e t   C o n t e s t i n t e r n e t c o n t e s t C E O I 2 0 0 0 Regulations Schedule OrganisingTeam Cluj&Romania Sponsors Secretariat Internet ContestLinks ___________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 ```