The game of trains P41202


pdf   zip


Juan has a new game of trains. This one has varios straight stretches that can be joined to form longer tracks. Those ones will be joined always in a way that the track is continuous and all the stretches form a straight line with different difference of level (the game does not have curved stretches, these one come with the exapansion). The game also has carriages that Juan can launch from a point of the rail with the speed that he wants. Maria, the sister of Juan, has placed the stretches forming a rail and dares Juan to launch a carriage from the beginning of the rail so that it arrives to the position with the minimal speed.

Juan has observed that for each centimetre that the carriages go up, those ones loose A mm/s of speed for the gravity, while that for each centimetre that they go down, those ones win A mm/s of speed. Moreover, for each metre of covered track, caused by the friction of the track, those ones loose B mm/s of speed. Juan wants that the carriage stops in the position indicated by Maria, that is in a distance of X cm in horizontal from the beginning of the rail. Juan wants to know the minimal speed he has to launch the carriage with in order to it arrives to the point indicated by Maria.


The input will consist of various test data. The first line will contain a number that will indicate the number of test data to solve. Each test data will start with 4 numbers A, B, X and N, in this order, in a line, where N will be the number of stretches of the track and will be integer. The following N+1 lines will contain N+1 pairs of points (xi,yi) with xi and yi measured in milimitres and being integers, where (0,0) will be the first point and xi will be stricly increasing, that is, xi < xi+1. These points represent a track of N straight stretches joined. It is known that N ≤ 1000 and that |yi| ≤ 100.


For each case, your program must print in a line the ceiling of the minimal speed in mm/s that the carriage must be launched with to reach the point indicated by Maria.

Pista: Consider that, the faster you launch the carriage from the origen, the farther it will arrive. Therefore, it can be known that if the carriage does not reach the position P with a determinated speed, it must be launched with more speed.

Author: Ricardo Martín

The solution can be found iterating though the track until arriving to the position X.

PROBLEMAS DOUBLE En caso de llegar a un pico con velocidad 0, como decidimos si sigue hacia abajo o no?? Solucion = no puede haber picos... si os parece..

Omer Giménez
Carlos Molina
Original language
Other languages
Official solutions
User solutions