시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB120459744748.324%

문제

당신은 세계적인 인간대포 서커스 공연자이다. 즉, 당신은 거대한 가짜 대포 안으로 기어올라가 먼 거리를 발사되며 사람들에게 기쁨을 주는 사람인 것이다. 오늘, 당신은 혼자가 아니다. 당신은 국제 인간대포 회의 겸 전시장에 와 있으며 이 곳에서는 수백명의 인간대포 전문가들이 서로의 경험을 공유하고 기술을 연마한다. 보통 당신의 서커스에서 당신은 한 대포만을 가지고 공연하는데 반해 이곳에서는 사용할 수 있는 수많은 대포가 있다.

여러 대포를 사용하면 회의장을 좀 더 편리하게 돌아다닐 수 있다. 만약 당신이 a장소에서 b장소까지 이동하려 한다면 a 부터 b까지 직선으로 걸어갈 수도 있고, 주변의 대포에 탑승해서 어딘가 다른 곳으로 발사되어 이동할 수도 있다. 발사되고 나면 내린 위치에서 도착점을 향해서 걸어갈 수도 있고, 다시 한 번 또 다른 대포를 이용하여 목적지에 더 빠르게 도착할 수도 있다. 그림 E.1처럼 배치된 지도에서 당신은 a에서 b로 이동하기 위하여 그림 E.2와 같은 경로로 걷거나 대포를 이용하여 움직일 수 있다. 화살표는 당신이 대포에서 발사되어 떨어진 점을 의미하며 직선은 당신이 달린 경로를 나타낸다.

그림 E.1

그림 E.2

당신은 5m/s의 속도로 달린다. 모든 대포는 당신을 당신이 원하는 임의의 방향으로 50m 날려줄 수 있다. 대포에 올라타고 발사되고 착륙하기까지는 정확히 2초가 걸린다. 대포는 장애물이 아니기 때문에 당신이 뛰는 도중에 대포가 있다면 점프해서 넘어가 마치 직선과 같이 움직일 수 있다. 당신의 현재 위치와 목적지의 위치, 그리고 대포들의 위치가 주어질 때 당신은 목적지에 가장 빨리가기 위한 경로를 알고 싶다.

입력

입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대포의 숫자 정수 n이 주어진다. 남은 n줄에는 한 줄에 대포 하나의 위치 정보가 주어지며, 이는 실수로 주어지는 X, Y 좌표이다. 모든 좌표는 미터로 측정되었으며 n의 값은 0 이상 100 이하이다. 입력으로 주어지는 모든 X, Y좌표는 0 이상 500 이하의 실수이고, 소수점 아래로 최대 두 자리까지만 주어진다.

출력

한 줄에 걸쳐 목적지에 다다르기 위해 가장 빠른 시간을 출력하라. 실제 답과 0.001초 미만의 차이는 정답으로 인정한다.

예제 입력 1

25.0 100.0
190.0 57.5
4
125.0 67.5
75.0 125.0
45.0 72.5
185.0 102.5

예제 출력 1

19.984901
W3sicHJvYmxlbV9pZCI6IjEwNDczIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNzc4XHVhYzA0IFx1YjMwMFx1ZDNlYyIsImRlc2NyaXB0aW9uIjoiPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YzEzOFx1YWNjNFx1YzgwMVx1Yzc3OCBcdWM3NzhcdWFjMDRcdWIzMDBcdWQzZWMgXHVjMTFjXHVjZWU0XHVjMmE0IFx1YWNmNVx1YzVmMFx1Yzc5MFx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWIyZjlcdWMyZTBcdWM3NDAgXHVhYzcwXHViMzAwXHVkNTVjIFx1YWMwMFx1YzlkYyBcdWIzMDBcdWQzZWMgXHVjNTQ4XHVjNzNjXHViODVjIFx1YWUzMFx1YzViNFx1YzYyY1x1Yjc3Y1x1YWMwMCBcdWJhM2MgXHVhYzcwXHViOWFjXHViOTdjIFx1YmMxY1x1YzBhY1x1YjQxOFx1YmE3MCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHVhZTMwXHVjMDY4XHVjNzQ0IFx1YzhmY1x1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NzggXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM2MjRcdWIyOTgsIFx1YjJmOVx1YzJlMFx1Yzc0MCBcdWQ2M2NcdWM3OTBcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NDAgXHVhZDZkXHVjODFjIFx1Yzc3OFx1YWMwNFx1YjMwMFx1ZDNlYyBcdWQ2OGNcdWM3NTggXHVhY2I4IFx1YzgwNFx1YzJkY1x1YzdhNVx1YzVkMCBcdWM2NDAgXHVjNzg4XHVjNzNjXHViYTcwIFx1Yzc3NCBcdWFjZjNcdWM1ZDBcdWMxMWNcdWIyOTQgXHVjMjE4XHViYzMxXHViYTg1XHVjNzU4IFx1Yzc3OFx1YWMwNFx1YjMwMFx1ZDNlYyBcdWM4MDRcdWJiMzhcdWFjMDBcdWI0ZTRcdWM3NzQgXHVjMTFjXHViODVjXHVjNzU4IFx1YWNiZFx1ZDVkOFx1Yzc0NCBcdWFjZjVcdWM3MjBcdWQ1NThcdWFjZTAgXHVhZTMwXHVjMjIwXHVjNzQ0IFx1YzVmMFx1YjljOFx1ZDU1Y1x1YjJlNC4gXHViY2Y0XHVkMWI1IFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWMxMWNcdWNlZTRcdWMyYTRcdWM1ZDBcdWMxMWMgXHViMmY5XHVjMmUwXHVjNzQwIFx1ZDU1YyBcdWIzMDBcdWQzZWNcdWI5Y2NcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YWNmNVx1YzVmMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWJjMThcdWQ1NzQgXHVjNzc0XHVhY2YzXHVjNWQwXHVjMTFjXHViMjk0IFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzIxOFx1YjljZVx1Yzc0MCBcdWIzMDBcdWQzZWNcdWFjMDAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1ZWNcdWI3ZWMgXHViMzAwXHVkM2VjXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1OFx1YmE3NCBcdWQ2OGNcdWM3NThcdWM3YTVcdWM3NDQgXHVjODgwIFx1YjM1NCBcdWQzYjhcdWI5YWNcdWQ1NThcdWFjOGMgXHViM2NjXHVjNTQ0XHViMmU0XHViMmQwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWIyZjlcdWMyZTBcdWM3NzQgYVx1YzdhNVx1YzE4Y1x1YzVkMFx1YzExYyBiXHVjN2E1XHVjMThjXHVhZTRjXHVjOWMwIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTRcdWJhNzQgYSBcdWJkODBcdWQxMzAgYlx1YWU0Y1x1YzljMCBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVhYzc4XHVjNWI0XHVhYzA4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YzhmY1x1YmNjMFx1Yzc1OCBcdWIzMDBcdWQzZWNcdWM1ZDAgXHVkMGQxXHVjMmI5XHVkNTc0XHVjMTFjIFx1YzViNFx1YjUxOFx1YWMwMCBcdWIyZTRcdWI5NzggXHVhY2YzXHVjNzNjXHViODVjIFx1YmMxY1x1YzBhY1x1YjQxOFx1YzViNCBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHViYzFjXHVjMGFjXHViNDE4XHVhY2UwIFx1YjA5OFx1YmE3NCBcdWIwYjRcdWI5YjAgXHVjNzA0XHVjZTU4XHVjNWQwXHVjMTFjIFx1YjNjNFx1Y2MyOVx1YzgxMFx1Yzc0NCBcdWQ1YTVcdWQ1NzRcdWMxMWMgXHVhYzc4XHVjNWI0XHVhYzA4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWFjZTAsIFx1YjJlNFx1YzJkYyBcdWQ1NWMgXHViYzg4IFx1YjYxMCBcdWIyZTRcdWI5NzggXHViMzAwXHVkM2VjXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1OFx1YzVlYyBcdWJhYTlcdWM4MDFcdWM5YzBcdWM1ZDAgXHViMzU0IFx1YmU2MFx1Yjk3NFx1YWM4YyBcdWIzYzRcdWNjMjlcdWQ1NjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViOWJjIEUuMVx1Y2M5OFx1YjdmYyBcdWJjMzBcdWNlNThcdWI0MWMgXHVjOWMwXHViM2M0XHVjNWQwXHVjMTFjIFx1YjJmOVx1YzJlMFx1Yzc0MCBhXHVjNWQwXHVjMTFjIGJcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1OFx1YzVlYyBcdWFkZjhcdWI5YmMgRS4yXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWI4NWNcdWI4NWMgXHVhYzc3XHVhYzcwXHViMDk4IFx1YjMwMFx1ZDNlY1x1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1ZDY1NFx1YzBiNFx1ZDQ1Y1x1YjI5NCBcdWIyZjlcdWMyZTBcdWM3NzQgXHViMzAwXHVkM2VjXHVjNWQwXHVjMTFjIFx1YmMxY1x1YzBhY1x1YjQxOFx1YzViNCBcdWI1YThcdWM1YjRcdWM5YzQgXHVjODEwXHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1OFx1YmE3MCBcdWM5YzFcdWMxMjBcdWM3NDAgXHViMmY5XHVjMmUwXHVjNzc0IFx1YjJlY1x1YjliMCBcdWFjYmRcdWI4NWNcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvdXBsb2FkXC9pbWFnZXMyXC9odW1hbjEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTk5cHg7IHdpZHRoOjMwNXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5cdWFkZjhcdWI5YmMgRS4xPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91cGxvYWRcL2ltYWdlczJcL2h1bWFuMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDBweDsgd2lkdGg6Mjk5cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPlx1YWRmOFx1YjliYyBFLjI8XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIDVtXC9zXHVjNzU4IFx1YzE4ZFx1YjNjNFx1Yjg1YyBcdWIyZWNcdWI5YjBcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWIzMDBcdWQzZWNcdWIyOTQgXHViMmY5XHVjMmUwXHVjNzQ0IFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyA1MG0gXHViMGEwXHViODI0XHVjOTA0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjMwMFx1ZDNlY1x1YzVkMCBcdWM2MmNcdWI3N2NcdWQwYzBcdWFjZTAgXHViYzFjXHVjMGFjXHViNDE4XHVhY2UwIFx1Y2MyOVx1Yjk1OVx1ZDU1OFx1YWUzMFx1YWU0Y1x1YzljMFx1YjI5NCBcdWM4MTVcdWQ2NTVcdWQ3ODggMlx1Y2QwOFx1YWMwMCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1YjMwMFx1ZDNlY1x1YjI5NCBcdWM3YTVcdWM1NjBcdWJiM2NcdWM3NzQgXHVjNTQ0XHViMmM4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIyZjlcdWMyZTBcdWM3NzQgXHViNmYwXHViMjk0IFx1YjNjNFx1YzkxMVx1YzVkMCBcdWIzMDBcdWQzZWNcdWFjMDAgXHVjNzg4XHViMmU0XHViYTc0IFx1YzgxMFx1ZDUwNFx1ZDU3NFx1YzExYyBcdWIxMThcdWM1YjRcdWFjMDAgXHViOWM4XHVjZTU4IFx1YzljMVx1YzEyMFx1YWNmYyBcdWFjMTlcdWM3NzQgXHVjNmMwXHVjOWMxXHVjNzdjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjJmOVx1YzJlMFx1Yzc1OCBcdWQ2MDRcdWM3YWMgXHVjNzA0XHVjZTU4XHVjNjQwIFx1YmFhOVx1YzgwMVx1YzljMFx1Yzc1OCBcdWM3MDRcdWNlNTgsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIzMDBcdWQzZWNcdWI0ZTRcdWM3NTggXHVjNzA0XHVjZTU4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgXHViMmY5XHVjMmUwXHVjNzQwIFx1YmFhOVx1YzgwMVx1YzljMFx1YzVkMCBcdWFjMDBcdWM3YTUgXHViZTY4XHViOWFjXHVhYzAwXHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjNTRjXHVhY2UwIFx1YzJmNlx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWQ1NWMgXHVhYzFjXHVjNzU4IFx1YWUzOFx1Y2MzZVx1YWUzMCBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDVjXHVkNjA0XHVkNTVjXHViMmU0LiBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjMmU0XHVjMjE4XHVhYzAwIFx1Yzc4NVx1YjgyNVx1YjQxOFx1YmE3MCBcdWFjMDFcdWFjMDFcdWM3NDAgXHViMmY5XHVjMmUwXHVjNzc0IFx1ZDYwNFx1YzdhYyBcdWM3MDRcdWNlNThcdWQ1NWMgWCwgWVx1Yzg4Y1x1ZDQ1Y1x1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViYWE5XHVjODAxXHVjOWMwXHVjNzU4IFgsIFlcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjMmU0XHVjMjE4XHViODVjIFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gXHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIzMDBcdWQzZWNcdWM3NTggXHVjMjJiXHVjNzkwIFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMGE4XHVjNzQwIG5cdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQzZWMgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzcwNFx1Y2U1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzRcdWIyOTQgXHVjMmU0XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBYLCBZIFx1Yzg4Y1x1ZDQ1Y1x1Yzc3NFx1YjJlNC4gXHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWJiZjhcdWQxMzBcdWI4NWMgXHVjZTIxXHVjODE1XHViNDE4XHVjNWM4XHVjNzNjXHViYTcwIG5cdWM3NTggXHVhYzEyXHVjNzQwIDAgXHVjNzc0XHVjMGMxIDEwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuJm5ic3A7XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCZuYnNwO1x1YmFhOFx1YjRlMCBYLCBZXHVjODhjXHVkNDVjXHViMjk0IDAgXHVjNzc0XHVjMGMxIDUwMCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjMmU0XHVjMjE4XHVjNzc0XHVhY2UwLCZuYnNwO1x1YzE4Y1x1YzIxOFx1YzgxMCBcdWM1NDRcdWI3OThcdWI4NWMgXHVjZDVjXHViMzAwIFx1YjQ1MCBcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzBcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YmFhOVx1YzgwMVx1YzljMFx1YzVkMCBcdWIyZTRcdWIyZTRcdWI5NzRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy4gXHVjMmU0XHVjODFjIFx1YjJmNVx1YWNmYyAwLjAwMVx1Y2QwOCBcdWJiZjhcdWI5Y2NcdWM3NTggXHVjYzI4XHVjNzc0XHViMjk0IFx1YzgxNVx1YjJmNVx1YzczY1x1Yjg1YyBcdWM3NzhcdWM4MTVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTA0NzMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIdW1hbiBDYW5ub25iYWxsIFJ1biIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBhIHdvcmxkLWZhbW91cyBjaXJjdXMgcGVyZm9ybWVyLCBhIGh1bWFuIGNhbm5vbmJhbGwuIFRoaXMgbWVhbnMgdGhhdCB5b3UgY2xpbWIgaW50byBhIGJpZywgZmFrZSBjYW5ub24gYW5kIGxhdW5jaCB5b3Vyc2VsZiBncmVhdCBkaXN0YW5jZXMgdG8gZGVsaWdodCB5b3VuZyBhbmQgb2xkIGFsaWtlLiBUb2RheSwgeW91JnJzcXVvO3JlIG5vdCBhbG9uZS4gWW91IGFyZSBhdCB0aGUgaW50ZXJuYXRpb25hbCBodW1hbiBjYW5ub25iYWxsIGNvbmZlcmVuY2UgYW5kIGV4cG9zaXRpb24sIHdoZXJlIGh1bmRyZWRzIG9mIHNpbWlsYXIgY2lyY3VzIHBlcmZvcm1lcnMgaGF2ZSBnYXRoZXJlZCB0b2dldGhlciB0byBzaGFyZSB0aGVpciBleHBlcmllbmNlcyBhbmQgcHJhY3RpY2UgdGhlaXIgY3JhZnQuIFdoaWxlIHlvdSBub3JtYWxseSBoYXZlIGp1c3Qgb25lIGNhbm5vbiB0byB3b3JrIHdpdGgsIGF0IHRoZSBjb25mZXJlbmNlIHRoZXJlIGFyZSB1c3VhbGx5IGxvdHMgb2YgY2Fubm9ucyB0byBleGFtaW5lIGFuZCB0cnkgb3V0LjxcL3A+XHJcblxyXG48cD5UaGUgYXZhaWxhYmlsaXR5IG9mIHNldmVyYWwgY2Fubm9ucyBjcmVhdGVzIHNvbWUgaW50ZXJlc3Rpbmcgb3Bwb3J0dW5pdGllcyBmb3IgbmF2aWdhdGluZyB0aGUgY29uZmVyZW5jZS4gSWYgeW91IHdhbnQgdG8gdHJhdmVsIHF1aWNrbHkgZnJvbSBwb2ludCBhIHRvIHBvaW50IGIsIHlvdSBjb3VsZCBqdXN0IHJ1biBzdHJhaWdodCBmcm9tIGEgdG8gYiwgb3IsIHlvdSBjb3VsZCBydW4gdG8gYSBuZWFyYnkgY2Fubm9uIGFuZCBsYXVuY2ggeW91cnNlbGYgc29tZXdoZXJlIGVsc2UuIEZyb20gdGhlcmUsIHlvdSBjYW4gY29udGludWUgdG8gcnVuIHRvd2FyZCB5b3VyIGRlc3RpbmF0aW9uIG9yIHlvdSBjYW4gY29udGludWUgdG8gdXNlIGNhbm5vbnMgaW4gYW4gZWZmb3J0IHRvIGdldCB0byB5b3VyIGRlc3RpbmF0aW9uIG1vcmUgcXVpY2tseS4gV2l0aCBjYW5ub25zIHBvc2l0aW9uZWQgbGlrZSBGaWd1cmUgRS4xLCB5b3UgY291bGQgZm9sbG93IGEgcGF0aCBsaWtlIHRoZSBvbmUgaW4gRmlndXJlIEUuMiB0byBnZXQgZnJvbSBhIHRvIGIuIFRoZSBhcnJvd3Mgc2hvdyBwbGFjZXMgd2hlcmUgeW91IGxhdW5jaGVkIHlvdXJzZWxmIG91dCBvZiBhIGNhbm5vbiwgYW5kIHRoZSBsaW5lcyBzaG93IHdoZXJlIHlvdSByYW4gdG8gdGhlIG5leHQgY2Fubm9uIG9yIHRvIHlvdXIgZGVzdGluYXRpb24uPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2h1bWFuMS5wbmdcIiBzdHlsZT1cImhlaWdodDoxOTlweDsgd2lkdGg6MzA1cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlIEUuMTogSWxsdXN0cmF0aW9uIG9mIHRoZSBzYW1wbGUgaW5wdXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2h1bWFuMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDBweDsgd2lkdGg6Mjk5cHhcIiBcLz48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+RmlndXJlIEUuMjogQSBzdWJvcHRpbWFsIHNvbHV0aW9uLjxcL3A+XHJcblxyXG48cD5Zb3UgcnVuIGF0IGEgcmF0ZSBvZiA1IG1ldGVycyBwZXIgc2Vjb25kLiBBbGwgY2Fubm9ucyBsYXVuY2ggeW91IGEgZGlzdGFuY2Ugb2YgNTAgbWV0ZXJzLCBpbiBhbnkgZGlyZWN0aW9uIHlvdSZyc3F1bztkIGxpa2UuIENsaW1iaW5nIGludG8gYSBjYW5ub24sIGxhdW5jaGluZyB5b3Vyc2VsZiBhbmQgbGFuZGluZyB0YWtlcyBhIHRvdGFsIG9mIDIgc2Vjb25kcy4gQ2Fubm9ucyBhcmUgbm90IG9ic3RhY2xlczsgaWYgYSBjYW5ub24gaXMgaW4geW91ciB3YXksIHlvdSBjYW4ganVtcCBvdmVyIG9yIHJ1biBhcm91bmQgaXQgd2l0aG91dCBpdCBzbG93aW5nIHlvdSBkb3duLiBHaXZlbiB5b3VyIGN1cnJlbnQgbG9jYXRpb24sIGEgZGVzaXJlZCBkZXN0aW5hdGlvbiBhbmQgdGhlIHBvc2l0aW9ucyBvZiBhdmFpbGFibGUgY2Fubm9ucywgeW91IHdhbnQgdG8gcGxhbiBob3cgdG8gZ2V0IHRvIHRoZSBkZXN0aW5hdGlvbiBhcyBxdWlja2x5IGFzIHBvc3NpYmxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGRlc2NyaWJlcyBhIHNpbmdsZSBuYXZpZ2F0aW9uIHByb2JsZW0uIFRoZSBmaXJzdCBsaW5lIGdpdmVzIGEgcGFpciBvZiByZWFsIG51bWJlcnMsIHRoZSBYIGFuZCBZIGNvb3JkaW5hdGVzIHdoZXJlIHlvdSZyc3F1bztyZSBjdXJyZW50bHkgbG9jYXRlZC4gVGhlIG5leHQgbGluZSBnaXZlIHRoZSByZWFsLXZhbHVlZCBYIGFuZCBZIGNvb3JkaW5hdGVzIG9mIHRoZSBsb2NhdGlvbiB5b3UmcnNxdW87ZCBsaWtlIHRvIHJlYWNoLiBUaGlzIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSB3aXRoIGFuIGludGVnZXIsIG4sIHRoZSBudW1iZXIgb2YgY2Fubm9ucyBhdmFpbGFibGUuIFRoZSByZW1haW5pbmcgbiBpbnB1dCBsaW5lcyBlYWNoIGNvbnRhaW4gYSBwYWlyIG9mIHJlYWwgdmFsdWVzIGdpdmluZyB0aGUgWCBhbmQgWSBjb29yZGluYXRlcyBmb3IgYSBjYW5ub24uIEFsbCBjb29yZGluYXRlcyBhcmUgbWVhc3VyZWQgaW4gbWV0ZXJzLCBhbmQgdGhlIHZhbHVlIG9mIG4gd2lsbCBiZSBiZXR3ZWVuIDAgYW5kIDEwMCwgaW5jbHVzaXZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IGEgc2luZ2xlIGxpbmUgb2Ygb3V0cHV0LCB0aGUgdG90YWwgbnVtYmVyIG9mIHNlY29uZHMgcmVxdWlyZWQgdG8gcmVhY2ggeW91ciBkZXN0aW5hdGlvbiBhcyBxdWlja2x5IGFzIHBvc3NpYmxlLiBZb3VyIGFuc3dlciBtdXN0IGJlIGFjY3VyYXRlIHRvIHdpdGhpbiAwLjAwMSBzZWNvbmRzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2014 E번

  • 문제를 번역한 사람: tae
  • 문제를 만든 사람: David Sturgill