시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 69 21 14 35.000%

문제

용감한 로빈 경은 악마들의 왕에 의해 던전에 던져졌다. 던전은 거대한 바위벽들로 둘러쌓인 큐브모양으로 이루어져 있다. 던전 전제 방들은 통로로 연결되어있어서 위에서 본다면 나선형으로 생겼다. 방들의 번호는 다음과 같다.

거대한 지진 이후 몇개의 벽들이 무너졌고 새로운  통로들이 인접한 방들사이에 생성이 되었다.

로빈 경은 처음에 1번 방에 있다. 로빈경은 던전의 출구가 N방에 있다는 것을 알고 있고, 모두가 지진으로 산만해진 틈을 타서 탈출하고 싶어한다. 악룡이 던전을 지키고 있기 때문에 로빈 경은 가장 빠른 길을 통해서 던전을 탈출하고 싶어한다.

출구 N과 새로운 통로의 목록이 나열되면 로빈경이 가장 빠른 길로 던전을 탈출 하기 위해서 반드시 거쳐야 하는 통로의 수를 출력하는 프로그램을 만들어라

입력

첫번째 줄에는 출구 번호 정수 N (1 ≤ N ≤ 1015)이 주어진다.

두번째 줄에는 새로 생긴 통로인 정수 K (1 ≤ K ≤ 100,000)가 주어진다.

다음 K의 줄에는 하나의 정수 B (4 ≤ B ≤ 1015)가 주어지는데, 이는 새로운 통로가 인접한 A, B(A<B일 경우) 방을 잇는다는 것을 의미한다.

A는 명확하게 주어지지 않지만, 이는 B와 유일하게 이어질 수 있다. (예를 들어 B가 20이면, A는 7이 되어야만 한다). 또한 다른 방들은 절대로 B가 될 수 없다(2,3,5,7,10,13 등)

출력

로빈경이 던전을 탈출하기 위해 지나야 하는 통토의 수를 출력한다.

예제 입력

31
9
15
25
30
6
9
19
24
27
4

예제 출력

6

힌트

이 그림은 지진 이후의 던전의 모습을 나타낸 것이다.

미르코는 1-4-15-14-13-30-31의 6개의 경로를 이용하여 던전을 탈출 할 수 있다.

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2008 > Croatian Olympiad in Informatics 2008 3번

  • 문제를 번역한 사람: kdy312
  • 잘못된 조건을 찾은 사람: ntopia
  • 문제의 오타를 찾은 사람: whdgnsdl887