시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 98 | 24 | 18 | 26.866% |
원철이는 지금 사람의 외로움이 어떤 효과를 가져오는지에 대해 실험하는, 일명 ALPS(Algorithm of Lonely Person Simulation) 실험에 피실험자로 참여하였다.
실험장은 2차원 격자로 이루어져있고, 원철이는 지금 (XM, YM) 에서 위쪽을 향해서 서있다. 전지적 작가시점으로 실험장을 보고있는 甲은 원철이에게 몇 가지 명령을 내릴 것이다. 명령은 0~7 사이의 숫자로 주어지며, 명령 k가 들어오면 원철이는 45 * k 도 만큼 반시계방향으로 돈 뒤 눈앞에 있는 정수격자로 점프를 할 것이다.
이 ALPS 실험에서 특이한 점은 (XB, YB) 좌표에 아름다운 여자가 한 명 서있다는 점이다. 원철이는 본능적으로 이 여자와 친해지고 싶어했고, 따라서 원철이는 실험이 끝났을 때 원철이가 서있는 위치가 최대한 여자와 가까워지길 바라고있다.
이번 실험에 사용될 N개의 명령을 사전에 입수한 원철이는, 주어진 명령대로 실험을 진행했다간 여자랑 거리가 더 멀어질 것 같음을 느꼈고, 이에 원철이는 최대 한번 甲의 명령이 아닌 다른 명령을 수행하기로 결심했다. (이런 갑작스런 반역행위도 외로움으로 부터 나타나는 현상이기 때문에 ALPS 실험에 지장이 안생긴다고 한다.)
굳은 결심을 했지만, 실험 종료 후 여자와 얼마나 가까워질 수 있는지 까지는 알아내지 못했다고 한다. 우리 원철이가 여자와 친해질 수 있도록 도와주자.
위의 이미지는 15102 명령을 수행한 모습이다. 원철이는 마지막으로 (1,4) 에 도착하고, 이 경우 여자와 원철이 사이의 거리는 1.41421356 정도 된다.
위 이미지는 원철이가 4번째 명령을 무시하고 0대신 7을 수행한 모습이다. 원철이는 (2,3)에 도착하게 되고, 이 경우 여자와 원철이 사이의 거리가 0으로 가장 짧다.
첫째 줄에는 원철이의 좌표와 여자의 좌표를 나타내는 숫자 XM, YM, XB, YB (0 ≤ XM, YM, XB, YB ≤ 1,000,000) 가 주어진다.
다음 줄에는 실험에 사용되는 명령의 개수 N( 1 ≤ N ≤ 100,000) 이 주어진다.
마지막 줄에는 명령을 나타내는 0~7 사이의 정수 N개가 순서대로 주어진다.
실험을 모두 마친 뒤의 원철이와 여자 사이의 거리의 최솟값을 출력한다. 정답과의 오차는 ±0.001 까지 허용한다.
0 0 2 3 5 15102
0.000000
5 5 10 5 3 000
2.000000
0 0 10 10 9 700003000
1.414214
Olympiad > Croatian Highschool Competitions in Informatics > 2008 > National Competition #1 - Seniors 2번