시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB219872.727%

문제

상근이는 대서양 해안에 살고 있다. 어느 날 하늘을 쳐다보니 보름달이 떠 있었다. 보름달 일 때는 간만의 차가 커진다. 상근이는 비가 오지 않는 날을 선택해 해안선을 산책하려고 한다.

해안선을 산책하다가 밀물을 만나면 바닷물에 갇힐 수 있다. 따라서, 조류를 잘 살펴본 뒤에 산책 계획을 세워야 한다.

안전하게 산책을 하려면 간조일 때 산책을 하면 된다. 하지만, 문제는 이 해안이 돌로 이루어져 있다는 점이다. 돌에서 미끄러지면 다칠 수 있기 때문에, 상근이는 돌이 한 시간 전에 마른 상태가 되어야 돌 위로 올라갈 수 있다.

해변은 거의 대부분이 모래로 이루어져 있고, 그 위에 돌이 놓여져 있는 형태이다. 모든 구역은 마른 상태이거나 물에 잠겨있는 상태이다. 구역의 높이보다 물의 높이가 높아진 순간에 구역은 물에 잠기며, 인접한 구역의 높이와는 관계 없다.

해변은 10 × 10m 단위로 구역을 나눌 수 있고, 각 구역의 높이는 모두 알고 있다. 각 정사각형에 들어가려면, 인접한 네 정사각형에서 이동해야 한다. 또, 두 구역의 높이가 \(z_1\), \(z_2\)라고 할 때, 높이의 차이 \(\left| z_1 - z_2 \right| \)가 최대 1m인 경우에만 이동할 수 있다.

한 정사각형에서 다른 정사각형으로 갈 때, 걸리는 시간은 일정하며, 이 시간 동안 두 정사각형은 모두 마른 상태이어야 한다.

해수면의 높이는 여러 가지 요인에 의해 결정된다. 상근이는 물의 높이 \(v\)(미터)가 만조로 부터 지난 시간 \(t\)(시간)와 여러 가지 요인에 의해 결졍된 높이 \(a\)(미터)로 다음과 같이 나타낼 수 있다는 사실을 알게 되었다.

\[v=0.5a \cdot (\cos { (t \frac{2 \pi}{12}) } + 1 )\] 

상근이는 산책을 집에서 시작하고, 집에서 끝내려고 한다. 밀물이 몰려오기 전 까지 시간이 얼마 남지 않았기 때문에 0.0 ≤ t ≤ 12.0 시간 안에 산책을 마치려고 한다. 상근이는 얼마나 멀리 산책하러 나갈 수 있을까?

입력

첫째 줄에 두 실수 \(a\) (0.0 < \(a\) < 15.0) 과 한 정사각형을 지나가는데 걸리는 시간 \(m\) (0.1 ≤ \(m\) ≤ 60.0)이 주어진다. \(m\)의 단위는 초이다.

둘째 줄에는 네 정수  \(W\), \(H\), \(X\), \(Y\)이 주어진다. (1 ≤ \(W\),\(H\) ≤ 200, 0 ≤ \(X\) < \(W\), 0 ≤ \(Y\) < \(H\)) \(W\)와 \(H\)는 지도의 너비와 높이이고, \(X\)와 \(Y\)는 상근이의 집의 좌표 (\(X\),\(Y\)) 이다.

다음 \(H\)개 줄에는 \(W\)개의 정수가 공백으로 구분되어져서 주어진다. 각 정수는 각 10 × 10m 단위 정사각형의 높이이며, 가장 해수면의 높이가 낮았을 때가 기준이다. 단위는 밀리미터이다. 각 정사각형의 높이는 0보다 크며, 20,000을 넘지 않는다. 첫째 줄의 첫 번째 숫자가 (0,0)에 해당하며, 상근이의 집은 항상 마른 상태이다.

출력

첫째 줄에 상근이가 가장 멀리 갈 수 있는 곳과의 유클리드 거리를 출력한다. 두 정사각형 사이의 거리는 두 중심 사이의 거리로 계산할 수 있다. 상대/절대 오차가 10-6 이내인 경우에만 정답이다.

소수점 계산으로 생기는 오차를 막기 위해서 걷는 속도 \(0.999m\) < \(m' \) < \(1.001m\)인 \(m'\)인 경우에 정답과 같다.

예제 입력 1

2.0 10.0
3 3 0 0
2001 1000 100
1001 10000 200
100 0 0

예제 출력 1

20

예제 입력 2

4.0 30.0
6 2 2 0
73 1001 4001 1001 76 70
70 2001 3001 2001 72 71

예제 출력 2

22.36067977
W3sicHJvYmxlbV9pZCI6IjkyNDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDhcdWJjYmQgXHVhYzc3XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViMzAwXHVjMTFjXHVjNTkxIFx1ZDU3NFx1YzU0OFx1YzVkMCBcdWMwYjRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM1YjRcdWIyOTAgXHViMGEwIFx1ZDU1OFx1YjI5OFx1Yzc0NCBcdWNjZDBcdWIyZTRcdWJjZjRcdWIyYzggXHViY2Y0XHViOTg0XHViMmVjXHVjNzc0IFx1YjVhMCBcdWM3ODhcdWM1YzhcdWIyZTQuIFx1YmNmNFx1Yjk4NFx1YjJlYyBcdWM3N2MgXHViNTRjXHViMjk0IFx1YWMwNFx1YjljY1x1Yzc1OCBcdWNjMjhcdWFjMDAgXHVjZWU0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViZTQ0XHVhYzAwIFx1YzYyNFx1YzljMCBcdWM1NGFcdWIyOTQgXHViMGEwXHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU3NCBcdWQ1NzRcdWM1NDhcdWMxMjBcdWM3NDQgXHVjMGIwXHVjYzQ1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTc0XHVjNTQ4XHVjMTIwXHVjNzQ0IFx1YzBiMFx1Y2M0NVx1ZDU1OFx1YjJlNFx1YWMwMCBcdWJjMDBcdWJiM2NcdWM3NDQgXHViOWNjXHViMDk4XHViYTc0IFx1YmMxNFx1YjJmN1x1YmIzY1x1YzVkMCBcdWFjMDdcdWQ3OTAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWM4NzBcdWI5NThcdWI5N2MgXHVjNzk4IFx1YzBiNFx1ZDNiNFx1YmNmOCBcdWI0YTRcdWM1ZDAgXHVjMGIwXHVjYzQ1IFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWMxMzhcdWM2Y2NcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDhcdWM4MDRcdWQ1NThcdWFjOGMgXHVjMGIwXHVjYzQ1XHVjNzQ0IFx1ZDU1OFx1YjgyNFx1YmE3NCBcdWFjMDRcdWM4NzBcdWM3N2MgXHViNTRjIFx1YzBiMFx1Y2M0NVx1Yzc0NCBcdWQ1NThcdWJhNzQgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWM3NzQgXHVkNTc0XHVjNTQ4XHVjNzc0IFx1YjNjY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0XHViMjk0IFx1YzgxMFx1Yzc3NFx1YjJlNC4gXHViM2NjXHVjNWQwXHVjMTFjIFx1YmJmOFx1YjA0NFx1YjdlY1x1YzljMFx1YmE3NCBcdWIyZTRcdWNlNjAgXHVjMjE4IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIzY2NcdWM3NzQgXHVkNTVjIFx1YzJkY1x1YWMwNCBcdWM4MDRcdWM1ZDAgXHViOWM4XHViOTc4IFx1YzBjMVx1ZDBkY1x1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHViM2NjIFx1YzcwNFx1Yjg1YyBcdWM2MmNcdWI3N2NcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTc0XHViY2MwXHVjNzQwIFx1YWM3MFx1Yzc1OCBcdWIzMDBcdWJkODBcdWJkODRcdWM3NzQgXHViYWE4XHViNzk4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWRmOCBcdWM3MDRcdWM1ZDAgXHViM2NjXHVjNzc0IFx1YjE5M1x1YzVlY1x1YzgzOCBcdWM3ODhcdWIyOTQgXHVkNjE1XHVkMGRjXHVjNzc0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVhZDZjXHVjNWVkXHVjNzQwIFx1YjljOFx1Yjk3OCBcdWMwYzFcdWQwZGNcdWM3NzRcdWFjNzBcdWIwOTggXHViYjNjXHVjNWQwIFx1YzdhMFx1YWNhOFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQwZGNcdWM3NzRcdWIyZTQuIFx1YWQ2Y1x1YzVlZFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWJjZjRcdWIyZTQgXHViYjNjXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWIxOTJcdWM1NDRcdWM5YzQgXHVjMjFjXHVhYzA0XHVjNWQwIFx1YWQ2Y1x1YzVlZFx1Yzc0MCBcdWJiM2NcdWM1ZDAgXHVjN2EwXHVhZTMwXHViYTcwLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVhZDZjXHVjNWVkXHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YzY0MFx1YjI5NCBcdWFkMDBcdWFjYzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NzRcdWJjYzBcdWM3NDAgMTAgJnRpbWVzOyAxMG0gXHViMmU4XHVjNzA0XHViODVjIFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWIwOThcdWIyMGMgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YWQ2Y1x1YzVlZFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgXHViYWE4XHViNDUwIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHViODI0XHViYTc0LCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViMTI0IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzVkMFx1YzExYyBcdWM3NzRcdWIzZDlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWI2MTAsIFx1YjQ1MCBcdWFkNmNcdWM1ZWRcdWM3NTggXHViMTkyXHVjNzc0XHVhYzAwIFxcKHpfMVxcKSwgXFwoel8yXFwpXHViNzdjXHVhY2UwIFx1ZDU2MCBcdWI1NGMsIFx1YjE5Mlx1Yzc3NFx1Yzc1OCBcdWNjMjhcdWM3NzQgXFwoXFxsZWZ0fCB6XzEgLSB6XzIgXFxyaWdodHwgXFwpXHVhYzAwIFx1Y2Q1Y1x1YjMwMCAxbVx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1YyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM1ZDBcdWMxMWMgXHViMmU0XHViOTc4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YzczY1x1Yjg1YyBcdWFjMDggXHViNTRjLCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1Yzc3Y1x1YzgxNVx1ZDU1OFx1YmE3MCwgXHVjNzc0IFx1YzJkY1x1YWMwNCBcdWIzZDlcdWM1NDggXHViNDUwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWJhYThcdWI0NTAgXHViOWM4XHViOTc4IFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU3NFx1YzIxOFx1YmE3NFx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWM2OTRcdWM3NzhcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YWNiMFx1YzgxNVx1YjQxY1x1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmIzY1x1Yzc1OCBcdWIxOTJcdWM3NzQgXFwodlxcKShcdWJiZjhcdWQxMzApXHVhYzAwIFx1YjljY1x1Yzg3MFx1Yjg1YyBcdWJkODBcdWQxMzAgXHVjOWMwXHViMDljIFx1YzJkY1x1YWMwNCBcXCh0XFwpKFx1YzJkY1x1YWMwNClcdWM2NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWM2OTRcdWM3NzhcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YWNiMFx1Yzg0ZFx1YjQxYyBcdWIxOTJcdWM3NzQgXFwoYVxcKShcdWJiZjhcdWQxMzApXHViODVjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxcW3Y9MC41YSBcXGNkb3QgKFxcY29zIHsgKHQgXFxmcmFjezIgXFxwaX17MTJ9KSB9ICsgMSApXFxdJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMwYjBcdWNjNDVcdWM3NDQgXHVjOWQxXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWNlMCwgXHVjOWQxXHVjNWQwXHVjMTFjIFx1YjA1ZFx1YjBiNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmMwMFx1YmIzY1x1Yzc3NCBcdWJhYjBcdWI4MjRcdWM2MjRcdWFlMzAgXHVjODA0IFx1YWU0Y1x1YzljMCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjNWJjXHViOWM4IFx1YjBhOFx1YzljMCBcdWM1NGFcdWM1NThcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIDAuMCAmbGU7IHQgJmxlOyAxMi4wIFx1YzJkY1x1YWMwNCBcdWM1NDhcdWM1ZDAgXHVjMGIwXHVjYzQ1XHVjNzQ0IFx1YjljOFx1Y2U1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM1YmNcdWI5YzhcdWIwOTggXHViYTQwXHViOWFjIFx1YzBiMFx1Y2M0NVx1ZDU1OFx1YjdlYyBcdWIwOThcdWFjMDggXHVjMjE4IFx1Yzc4OFx1Yzc0NFx1YWU0Yz88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzJlNFx1YzIxOCBcXChhXFwpICgwLjAgJmx0OyBcXChhXFwpICZsdDsgMTUuMCkgXHVhY2ZjIFx1ZDU1YyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjOWMwXHViMDk4XHVhYzAwXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDQgXFwobVxcKSAoMC4xICZsZTsgXFwobVxcKSAmbGU7IDYwLjApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXFwobVxcKVx1Yzc1OCBcdWIyZThcdWM3MDRcdWIyOTQgXHVjZDA4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjEyNCBcdWM4MTVcdWMyMTggJm5ic3A7XFwoV1xcKSwgXFwoSFxcKSwgXFwoWFxcKSwgXFwoWVxcKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgXFwoV1xcKSxcXChIXFwpICZsZTsgMjAwLCAwICZsZTsgXFwoWFxcKSAmbHQ7IFxcKFdcXCksIDAgJmxlOyBcXChZXFwpICZsdDsgXFwoSFxcKSkgXFwoV1xcKVx1YzY0MCBcXChIXFwpXHViMjk0IFx1YzljMFx1YjNjNFx1Yzc1OCBcdWIxMDhcdWJlNDRcdWM2NDAgXHViMTkyXHVjNzc0XHVjNzc0XHVhY2UwLCBcXChYXFwpXHVjNjQwIFxcKFlcXClcdWIyOTQgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc1OCBcdWM4OGNcdWQ0NWMgKFxcKFhcXCksXFwoWVxcKSkgXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgXFwoSFxcKVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXFwoV1xcKVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWFjMDAgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOFx1YzExYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWM4MTVcdWMyMThcdWIyOTQgXHVhYzAxIDEwICZ0aW1lczsgMTBtIFx1YjJlOFx1YzcwNCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTkyXHVjNzc0XHVjNzc0XHViYTcwLCBcdWFjMDBcdWM3YTUgXHVkNTc0XHVjMjE4XHViYTc0XHVjNzU4IFx1YjE5Mlx1Yzc3NFx1YWMwMCBcdWIwYWVcdWM1NThcdWM3NDQgXHViNTRjXHVhYzAwIFx1YWUzMFx1YzkwMFx1Yzc3NFx1YjJlNC4gXHViMmU4XHVjNzA0XHViMjk0IFx1YmMwMFx1YjlhY1x1YmJmOFx1ZDEzMFx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxOTJcdWM3NzRcdWIyOTQgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWJhNzAsIDIwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LiBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHVhYzAwICgwLDApXHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YmE3MCwgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzlkMVx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHViOWM4XHViOTc4IFx1YzBjMVx1ZDBkY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWFjMDBcdWM3YTUgXHViYTQwXHViOWFjIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWNmM1x1YWNmY1x1Yzc1OCBcdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVhYzcwXHViOWFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViNDUwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1YjQ1MCBcdWM5MTFcdWMyZWMgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjg1YyBcdWFjYzRcdWMwYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMGMxXHViMzAwXC9cdWM4MDhcdWIzMDAgXHVjNjI0XHVjYzI4XHVhYzAwIDEwLTYgXHVjNzc0XHViMGI0XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjljYyBcdWM4MTVcdWIyZjVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE4Y1x1YzIxOFx1YzgxMCBcdWFjYzRcdWMwYjBcdWM3M2NcdWI4NWMgXHVjMGRkXHVhZTMwXHViMjk0IFx1YzYyNFx1Y2MyOFx1Yjk3YyBcdWI5YzlcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YWM3N1x1YjI5NCBcdWMxOGRcdWIzYzQgXFwoMC45OTltXFwpICZsdDsgXFwobSYjMzk7IFxcKSAmbHQ7IFxcKDEuMDAxbVxcKVx1Yzc3OCBcXChtJiMzOTtcXClcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1YzgxNVx1YjJmNVx1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiOTI0NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNsaWZmIFdhbGsiLCJkZXNjcmlwdGlvbiI6IjxwPk9uZSBtb3JuaW5nIGxhc3Qgc3VtbWVyLCBDaGFybG90dGUgd2FzIHdhdGNoaW5nIHRoZSBtb29uIGFuZCB0aGUgc3VuIGFuZCBvYnNlcnZlZCB0aGF0IHRoZSBtb29uIHdhcyBmdWxsLiBBcyBzaGUgbGl2ZXMgYWxvbmcgdGhlIEF0bGFudGljIGNvYXN0IHNoZSBrbm93cyB0aGF0IHRoaXMgbWVhbnMgYSBsYXJnZXIgdmFyaWF0aW9uIGluIHRoZSB0aWRlIGNvbXBhcmVkIHRvIFx1ZmIwMXJzdCBhbmQgbGFzdCBxdWFydGVyLiBXaXRoIG5vIHJhaW4gaW4gdGhlIGFpciwgaXQgc2VlbWVkIGxpa2UgYSBwZXJmZWN0IHdlZWsgZm9yIHdhbGtzIGF0IHRoZSBiZWFjaCBieSB0aGUgY2xpZmZzLjxcL3A+XHJcblxyXG48cD5UaGUgdGlkZSBpcyBkYW5nZXJvdXMgd2hlbiB3YWxraW5nIGF0IHRoZSBiZWFjaCBiZXR3ZWVuIHRoZSBzZWEgYW5kIHRoZSBjbGlmZiB3YWxsLiBBcyB0aGUgd2F0ZXIgcmlzZXMsIHlvdSBtYXkgZ2V0IHRyYXBwZWQuIFRoZXJlZm9yZSBpdCBpcyBpbXBvcnRhbnQgdG8gcGxhbiB0aGUgd2FsayBhY2NvcmRpbmcgdG8gdGhlIGJlaGF2aW91ciBvZiB0aGUgdGlkZS48XC9wPlxyXG5cclxuPHA+T25lIHNpbXBsZSB3YXkgb2YgY2xpZmYgd2FsayBwbGFubmluZyBpcyBqdXN0IHRvIHN0YXJ0IHdhbGtpbmcgYW5kIHR1cm4gYXJvdW5kIGF0IGxvdyB0aWRlLiBUaGUgcHJvYmxlbSBpcyB0aGF0IG9uIGEgcm9ja3kgYmVhY2gsIHlvdSB3YW50IHRoZSByb2NrcyB0byBkcnkgZm9yIG9uZSBob3VyIGJlZm9yZSBlbnRlcmluZyB0aGVtLiBJdCBjb3VsZCB0aGVyZWZvcmUgYWN0dWFsbHkgYmUgc2FmZSB0byBjb250aW51ZSB0aGUgd2FsayBhIGJpdCBmdXJ0aGVyIGV2ZW4gYWZ0ZXIgbG93IHRpZGUuIE5vdGUgdGhhdCB0aGUgYmVhY2ggaXMgbW9zdGx5IG1hZGUgb2Ygc2FuZCBhbmQgdGhlIHJvY2tzIGhhdmUgbWFueSBjcmFja3MgaW4gdGhlbSwgc28gd2UgYXNzdW1lIHRoYXQgYWxsIGFyZWFzIGFyZSBcdWZiMDJvb2RlZCBvciBkcmFpbmVkIGF0IHRoZSBleGFjdCBtb21lbnQgd2hlbiB0aGUgdGlkZSByZWFjaGVzIHRoZWlyIGhlaWdodCwgaXJyZXNwZWN0aXZlIG9mIHRoZSBoZWlnaHRzIG9mIHRoZSBuZWlnaGJvdXJpbmcgYXJlYXMuPFwvcD5cclxuXHJcbjxwPlRoZSBiZWFjaCBoYXMgYmVlbiBzdXJ2ZXllZCBhbmQgYSBtYXAgaXMgYXZhaWxhYmxlIHdoZXJlIGVhY2ggMTAgJnRpbWVzOyAxMG0gc3F1YXJlIGhhcyBhIGNlcnRhaW4gaGVpZ2h0LiBFYWNoIHNxdWFyZSBjYW4gb25seSBiZSBlbnRlcmVkIGZyb20gdGhlIGZvdXIgbmVpZ2hib3VyaW5nIHNxdWFyZXMgdG8gdGhlIG5vcnRoLCBzb3V0aCwgZWFzdCBhbmQgd2VzdC4gSXQgaXMgb25seSBwb3NzaWJsZSB0byBwYXNzIGJldHdlZW4gdHdvIHNxdWFyZXMgb2YgaGVpZ2h0IFxcKHpfMVxcKSwgXFwoel8yXFwpIGlmIHRoZSBhYnNvbHV0ZSBoZWlnaHQgZGlmZmVyZW5jZSBcXChcXGxlZnR8IHpfMSAtIHpfMiBcXHJpZ2h0fCBcXCkgaXMgYXQgbW9zdCAxIG1ldGVyLiBDaGFybG90dGUgd2Fsa3MgaW4gc3VjaCBhIHdheSB0aGF0IGl0IHRha2VzIGEgY29uc3RhbnQgYW1vdW50IG9mIHRpbWUgdG8gcGFzcyBmcm9tIG9uZSBzcXVhcmUgdG8gYW5vdGhlciBhbmQgZHVyaW5nIHRoZSB3aG9sZSB0aW1lIHBlcmlvZCBib3RoIHNxdWFyZXMgbXVzdCBiZSBkcnkuIENoYXJsb3R0ZSBjYW4gYWxzbyBkZWNpZGUgdG8gc3RheSBhdCBhIHNxdWFyZSBmb3IgYW55IGFtb3VudCBvZiB0aW1lLjxcL3A+XHJcblxyXG48cD5UaGUgdGlkZSBiZWhhdmVzIGRpZmZlcmVudGx5IGF0IGRpZmZlcmVudCBwbGFjZXMgb24gdGhlIEVhcnRoIGRlcGVuZGluZyBvbiB0aGUgc2VhIGJvdHRvbSwgY29hc3QgbGluZSBldGMuIENoYXJsb3R0ZSBrbm93cyB0aGF0IGl0IGlzIHBvc3NpYmxlIHRvIGFwcHJveGltYXRlIHRoZSB0aWRlJnJzcXVvO3Mgd2F0ZXIgbGV2ZWwgXFwodlxcKSBpbiBtZXRlcnMgYXMgXFwodj0wLjVhIFxcY2RvdCAoXFxjb3MgeyAodCBcXGZyYWN7MiBcXHBpfXsxMn0pIH0gKyAxIClcXCksIHdoZXJlIFxcKHRcXCkgaXMgdGltZSBpbiBob3VycyBzaW5jZSB0aGUgbGFzdCBoaWdoIHRpZGUgYW5kIFxcKGFcXCkgaXMgaGVpZ2h0IGluIG1ldGVycyBkZXBlbmRpbmcgb24gdGhlIGxvY2F0aW9uLCB0aW1lIG9mIHRoZSB5ZWFyLCBldGMuPFwvcD5cclxuXHJcbjxwPkNoYXJsb3R0ZSB3aWxsIHN0YXJ0IGFuZCBcdWZiMDFuaXNoIGhlciB3YWxrIGF0IGhlciBob21lLiBTaGUgbGltaXRzIGhlciB0aW1lIGF3YXkgZnJvbSBob21lIHRvIG9ubHkgb25lIHRpZGUgaW50ZXJ2YWwsIHNvIHlvdSBtYXkgYXNzdW1lIHRoYXQgMC4wICZsZTsgXFwodFxcKSAmbGU7IDEyLjAuIEhvdyBmYXIgZnJvbSBob21lIGlzIHNoZSBhYmxlIHRvIGdldCBhbmQgc3RpbGwgcmV0dXJuIHNhZmVseSBiYWNrPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIHR3byBmbG9hdGluZyBwb2ludCBudW1iZXJzIFxcKGFcXCksIDAuMCAmbHQ7IFxcKGFcXCkgJmx0OyAxNS4wLCBhbmQgXFwobVxcKSwgMC4xICZsZTsgXFwobVxcKSAmbGU7IDYwLjAsIHRoZSBudW1iZXIgb2Ygc2Vjb25kcyBpdCB0YWtlcyB0byBwYXNzIG9uZSBzcXVhcmUgb24gdGhlIG1hcC4gVGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIGZvdXIgaW50ZWdlcnMgXFwoV1xcKSwgXFwoSFxcKSwgXFwoWFxcKSBhbmQgXFwoWVxcKSB3aGVyZSAxICZsZTsgXFwoV1xcKSxcXChIXFwpICZsZTsgMjAwLCAwICZsZTsgXFwoWFxcKSAmbHQ7IFxcKFdcXCkgYW5kIDAgJmxlOyBcXChZXFwpICZsdDsgXFwoSFxcKS4gXFwoV1xcKSBhbmQgXFwoSFxcKSBhcmUgdGhlIHdpZHRoIGFuZCBoZWlnaHQgb2YgdGhlIG1hcCBvZiB0aGUgY29hc3QsIFxcKFhcXCkgYW5kIFxcKFlcXCkgZGVzY3JpYmVzIHRoZSBjb29yZGluYXRlIChcXChYXFwpLFxcKFlcXCkpIG9mIENoYXJsb3R0ZSYjMzk7cyBob21lLjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93IFxcKEhcXCkgbGluZXMgZWFjaCBjb250YWluaW5nIFxcKFdcXCkgc3BhY2Ugc2VwYXJhdGVkIGludGVnZXJzLCBkZXNjcmliaW5nIHRoZSBoZWlnaHQgaW4gbWlsbGltZXRyZXMgb2YgZWFjaCAxMCAmdGltZXM7IDEwbSBzdXJ2ZXllZCBzcXVhcmUgY29tcGFyZWQgdG8gZXh0cmVtZSBsb3cgdGlkZS4gWW91IGNhbiBhc3N1bWUgdGhhdCB0aGUgaGVpZ2h0IG9mIGVhY2ggc3F1YXJlIHdpbGwgYmUgYXQgbGVhc3QgMCBhbmQgYXQgbW9zdCAyMCAwMDAgbWlsaW1ldHJlcy4gVGhlIFx1ZmIwMXJzdCBudW1iZXIgb24gdGhlIFx1ZmIwMXJzdCBsaW5lIGNvcnJlc3BvbmRzIHRvIGNvb3JkaW5hdGUgKDAsIDApLiBDaGFybG90dGUmcnNxdW87cyBob21lIHdpbGwgYWx3YXlzIGJlIGRyeS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGxpbmUgd2l0aCB0aGUgbWF4aW11bSBFdWNsaWRlYW4gZGlzdGFuY2UgdGhhdCBDaGFybG90dGUgY2FuIGdldCBmcm9tIGhvbWUuIFRoZSBkaXN0YW5jZSBiZXR3ZWVuIHR3byBzcXVhcmVzIHNob3VsZCBiZSBtZWFzdXJlZCBiZXR3ZWVuIHRoZWlyIGNlbnRlcnMuIFRoZSBhbnN3ZXIgaXMgY29uc2lkZXJlZCBjb3JyZWN0IGlmIGl0IGhhcyBhbiBhYnNvbHV0ZSBvciByZWxhdGl2ZSBlcnJvciBvZiBhdCBtb3N0IDEwPHN1cD4tNjxcL3N1cD4uPFwvcD5cclxuXHJcbjxwPlRvIGF2b2lkIHByb2JsZW1zIHdpdGggXHVmYjAyb2F0aW5nIHBvaW50IG51bWJlcnMsIHRoZSByZXN1bHQgaXMgZ3VhcmFudGVlZCB0byBiZSB0aGUgc2FtZSBmb3IgYWxsIHdhbGtpbmcgc3BlZWRzIFxcKG0mIzM5O1xcKSB3aGVyZSBcXCgwLjk5OW1cXCkgJmx0OyBcXChtJiMzOTsmbmJzcDtcXCkgJmx0OyBcXCgxLjAwMW1cXCkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Nordic Collegiate Programming Contest > NCPC 2013 K번

  • 문제를 번역한 사람: baekjoon
  • 문제를 만든 사람: Fredrik Svensson