HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50678 - The Jumping Rabbit

Guest
• Review clarifications (1)

Section problems

• 50672 - Math and Soldiers
• 50671 - Phalanx
• 50842 - Minimum Sum Triangle - DP
• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 51149 - One Piece Arena
• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing
• 50997 - Dynamic Knights

Feedback

If you notice incorrect translations in Contester, please let author know.

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



Для отправки решений необходимо выполнить вход.

www.contester.ru