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

2 0 0 0







Internet Contest


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).

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.

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).

  • 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.

    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.
  • If there are several solutions possible, only one is required

  • 1 <= N <= 1000
  • -20000 <= X1i, X2i <= 20000 ( i=1..N )
  • 0 < Hi < Y <= 20000

    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