Problemas
Jack과 Jill은 우물가에서 'Leap Frog'라는 매 턴마다 서로를 뛰어 넘는 게임을 하고 있다.편의상 우물가는 1차원평면이라 가정하자.
Jack과 Jill이 한 번에 뛸 수 있는 최대의 수평 길이는 10 이다.
우물가에는 n개의 조약돌이 있으며, 각 위치는 x1 , x2 , ..., xn 이다.
처음에 Jill은 x1의 위치에 서있으며, Jack은 x2의 위치에 서있다.
x1은 맨 왼쪽에 있는 조약돌이며, xn은 맨 오른쪽에 있는 조약돌이다.
게임은 둘 중에 하나가 xn에 최소 턴을 이용해 도달하는 것이 목적이다.
Jill 과 Jack은 매번 턴을 번갈아 가며 점프를 하게 되고, 반드시 상대방을 넘어서 점프를 해야 한다.
점프는 반드시 오른쪽 방향으로 해야 하며 그리고 점프를 했을 때, 반드시 조약돌에 이르러야 한다.
조약돌의 위치가 주어졌을 때 xn에 다다르는 최소 회수를 출력하라. 당연하지만 Jill이 처음에 턴을 가진다.
Entrada
입력의 첫 번째 줄에는 테스트 케이스의 개수 T 가 입력된다.
테스트 케이스의 첫 번째 줄에는 조약돌의 개수n(2≤n≤100,000)이 입력된다.
그다음 줄에는 조약돌의 위치 x1, x2, ..., xn (0≤x1, x2 ,..., xn≤1,000,000) 가 입력된다.
Salida
각 테스트 케이스에 대해 한 줄에 xn에 다다르는 경우가 존재할 경우 최소 횟수를 출력하고 그렇지 않을 경우 −1을 출력한다.
Ejemplo
2
6
3 5 9 12 15 17
6
3 5 9 12 30 40
3
-1
Fuente
Stanford Local ACM Programming Contest 2009 D번
Debes iniciar sesión para escribir código.