The jumping rabbit

THE JUMPING RABBIT

{Faruk BULUT}

The wise rabbit wants to cross a path of length L by jumping. The rabbit starts at point 0 and needs to reach exactly point L. It always jumps forward in the same direction, starting with an initial velocity (speed) of 0. With each jump, the rabbit can increase its velocity by 1 unit, decrease it by 1 unit, or keep it the same.

The velocity of the rabbit determines the distance it jumps. The final velocity is negligible when it reaches point L.

Along the path, there are T traps placed at various points, but there are no traps at the starting point (0) or the endpoint (L). Your task is to calculate the minimum number of jumps required for the rabbit to reach the finish while avoiding all traps.

Write a function to determine this minimum number of jumps.

Example

L = 18

T (Trap points) = 5, 10, 15

In this example, as it is seen above the total number of jumps is 6 (omit the last x sign).

Input

In the first line of the jump.in file, there are L and T numbers. In the following T lines, there are the trap locations.

Output

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.

Input and Output Files

jump.in

18 3

5

10

15

jump.out

6

Limits

1 < L < 500

1 < T < 250

The C code:

#include<stdio.h>

#include<limits.h>

#define YER bulundugumyer

FILE *oku,*yaz;

int min=INT_MAX,N,tuzaksayisi,son=1;

int tuzakyr[100000000];

void Oku(){

int i,a;

fscanf(oku,"%d %d",&N,&tuzaksayisi);

for(i=1;i<=tuzaksayisi;i++)

{

fscanf(oku,"%d ",&a);

tuzakyr[a]=-1;

}

}

void Yap(int YER,int hiz,int adim){

tuzakyr[YER]=adim;

if(YER == N) return;

if(YER+hiz+1 <= N &&(( tuzakyr[YER+hiz+1] > tuzakyr[YER]+1) || tuzakyr[YER+hiz+1]==0 )&& tuzakyr[YER+1+hiz]!=-1)

Yap(YER+hiz+1,hiz+1,adim+1);

if(hiz!=0 && YER+hiz <= N &&(( tuzakyr[YER+hiz] > tuzakyr[YER]+1) || tuzakyr[YER+hiz]==0) && tuzakyr[YER+hiz]!=-1)

Yap(YER+hiz,hiz,adim+1);

if(hiz!=0 && YER+hiz-1 <=N &&(( tuzakyr[YER+hiz-1] >tuzakyr[YER]+1 ) || tuzakyr[YER+hiz-1]==0)&& tuzakyr[YER+hiz-1]!=-1)

Yap(YER+hiz-1,hiz-1,adim+1);

}

void Yaz(){

fprintf(yaz,"%d\n",tuzakyr[N]-1);

return;

}

int main(){

yaz=fopen("jump1.out","w");

oku=fopen("jump1.in","r");

Oku();

Yap(0,0,1);

Yaz();

}