Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb. First asked in IMPC14 Ind_02 Question by Faruk Bulut.
The Jumping Rabbit
The wise rabbit wants to cross the way by
jumping. The length of the way is L.
The rabbit starts to jump
from the start point 0, and reaches
exactly on the point L. It goes always
forward in the same direction. Its initial
velocity (speed) is 0. In each jumping, the
rabbit might increase its velocity 1 unit,
or might decrease 1 unit, or might
remain the same.
Question:
The velocity of the rabbit is equal to
the distance it crosses. The final velocity
is negligible when it reaches to the L point.
While jumping, the rabbit wants to overrun
the T traps placed on the
way. There is no trap on the first (1) and
last (L) point. Your mission is to execute
the minimum number of jumps in order to
reach to finish.
Example:
L = 18
T (Trap points) = 5, 10, 15
In this example, as it is seen from the
figure, the total number of jumps is 6.
Input specification
In the first line, there are two integers
L and T numbers. The following T numbers,
are the trap locations where 1 < T <
250 and 1 < L < 500.
Output specification
The output should be the minimum number of jumps
performed by the rabbit in order to reach the
final. If it cannot reach to the final, print -1.
Sample Input
18 3
5 10 15
|
Sample Output
6
|
Для отправки решений необходимо выполнить вход.
|