시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 15 | 5 | 4 | 30.769% |
3133년에 우주 여행은 매우 흔한 일이 되었다. 차원 워프 드라이브를 이용하면 멀리 떨어져 있는 두 행성을 거의 즉시 이동할 수 있다.
차원 워프 드라이브는 상대 굴곡 양자화 우주(Relativistic Curved Quantized Space)의 법칙을 따른다. RCQS이론에 따르면 우주는 11차원으로 이루어져 있고, 각각은 자기 자신으로 굽어져 있다. 즉, 한 방향으로 계속해서 걸어간다면 출발한 지점으로 돌아올 수 있다.
이 이론에 의하면 우주는 양자화 되어져 있고, 각각의 차원에 대해서 가능한 위치는 총 11개가 있다. 0부터 10까지 있으며, 위치 11은 위치 0과 같다.
3075년에 첫 번째 워프 궤도가 발견되었다. 이러한 궤도를 이용하면 우주선은 현재 위치 좌표와 그 궤도의 좌표를 합한 좌표로 이동할 수 있다. (각각의 차원에 대해 적용) 한 번 발견된 워프 궤도는 여러 번 이용할 수 있다.
이후에 더 많은 워프 궤도가 발견되었고, 인간은 이 궤도를 이용해서 우주를 기하 급수적으로 식민지화 하기 시작했다.
현재 상근이의 위치와 가려고 하는 위치가 주어진다. 이때, 몇 년이 되면 그 곳으로 갈 수 있는지 구하는 프로그램을 작성하시오.
예를 들어, 상근이가 현재 (0,0,0,0,0,0,0,0,0,0,0)에 있고, 가려고 하는 곳의 좌표가 (0,0,3,0,0,3,0,0,3,0,0)이라고 하자. 워프 궤도는 3075년에 (0,0,1,0,0,1,0,0,1,0,0)가 발견되었고, 3082년에 (0,0,1,0,0,2,0,1,0,0,0)이 발견되었다고 하자. 그럼, 3075년에 발견된 워프 궤도를 3번 이용하면 바로 갈 수 있다.
첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 다음과 같이 이루어져 있다.
각 테스트 케이스에 대해서 몇 년이 되면 상근이가 워프 궤도를 이용해서 도착 지점에 갈 수 있는지 출력한다. 만약, 세월이 아무리 흘러도 갈 수 없다면 "unreachable"을 출력한다.
3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 3 0 0 3 0 0 0 0 1 0 0 1 0 0 1 0 0 3075 0 0 1 0 0 2 0 1 0 0 0 3082 2 0 0 0 0 0 0 0 9 0 0 0 0 0 4 0 0 6 0 0 2 0 0 0 0 1 0 0 1 0 0 1 0 0 3075 0 0 1 0 0 2 0 1 0 0 0 3082 3 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 6 0 0 3 0 0 0 0 1 0 0 1 0 0 1 0 0 3075 0 0 1 0 0 2 0 1 0 0 0 3082 1 2 3 4 5 6 7 5 4 3 2 3093
3075 3082 unreachable
ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2009 F번