시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 522 304 230 55.825%

문제

대학교를 졸업한 준규는 농부의 꿈을 이루기 위해서 가로 5m, 세로 5m 크기의 땅을 구입했다. 준규는 땅을 가로 1m, 세로 1m 크기로 구역을 나누었다. 가장 왼쪽 위 칸은 (1,1)이고 가장 오른쪽 아래 칸은 (5,5)이다. 준규의 땅을 아래 그림과 같이 나타낼 수 있다.

(1,1) (1,2) (1,3) (1,4) (1,5)
(2,1) (2,2) (2,3) (2,4) (2,5)
(3,1) (3,2) (3,3) (3,4) (3,5)
(4,1) (4,2) (4,3) (4,4) (4,5)
(5,1) (5,2) (5,3) (5,4) (5,5)

구역 K개를 제외한 각각의 구역에는 사과 나무가 하나씩 심어져 있다. K개 구역에는 거대한 돌이 있기 때문에 사과 나무가 심어져 있지 않다.

사과를 수확하는 일은 매우 귀찮은 일이다. 따라서, 준규는 친구 해빈이와 함께 재밌는 방법으로 수확을 하려고 한다.

준규는 (1,1)에서 사과를 수확하기 시작하고, 해빈이는 (5,5)에서 시작한다. (1,1)과 (5,5)에는 항상 사과 나무가 심어져 있다.

사과 나무 하나에 있는 모든 사과를 수확하는데 걸리는 시간은 항상 30분이다. 준규와 해빈이가 현재 있는 칸의 사과 나무에서 사과를 모두 수확하면, 인접한 칸 중 사과 나무가 있는 칸으로 이동한다. 이동하는데 걸리는 시간도 30분이다.

준규와 해빈이는 준규의 땅에 있는 모든 사과를 수확할 것이고, 마지막에는 같은 칸에서 만나려고 한다. 이때, 이렇게 사과를 수확하는 방법의 수를 구하는 프로그램을 작성하시오.

두 사람은 항상 사과가 있는 칸으로만 이동하며, 이미 수확을 마친 사과 나무가 있는 칸으로는 이동하지 않는다. 또, 마지막을 제외하고 같은 칸에서 만날 수는 없다.

입력

첫째 줄에 K가 주어진다. 둘째 줄부터 K (0 ≤ K ≤ 22, K는 짝수)개 줄에는 사과 나무가 없는 칸의 위치 (i,j)가 주어진다.

출력

문제에서 주어진 방법대로 사과를 모두 수확하는 방법의 수를 출력한다.

예제 입력 1

4
3 2
3 3
3 4
3 1

예제 출력 1

1

힌트

입력으로 주어진 상황을 그림으로 그리면 아래와 같다. 점(.)은 사과 나무가 있는 칸, x는 없는 칸을 나타내며, j는 준규의 위치, h는 해빈이의 위치이다.

j  .  .  .  .

.  .  .  .  .

x  x  x  x  .

.  .  .  .  .

.  .  .  .  h

문제의 조건을 지키면서 사과를 모두 수확하는 방법은 한가지이며, 아래와 같다.

j  j--j  j--j
|  |  |  |  |
j--j  j--j  j
            |
x  x  x  x j/h
            |
h--h--h--h--h
|
h--h--h--h--h
W3sicHJvYmxlbV9pZCI6IjU5MTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5MDBcdWFkZGNcdWM2NDAgXHVjMGFjXHVhY2ZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzMDBcdWQ1NTlcdWFkNTBcdWI5N2MgXHVjODc4XHVjNWM1XHVkNTVjIFx1YzkwMFx1YWRkY1x1YjI5NCBcdWIxOGRcdWJkODBcdWM3NTggXHVhZmM4XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVhYzAwXHViODVjIDVtLCBcdWMxMzhcdWI4NWMgNW0gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YjU0NVx1Yzc0NCBcdWFkNmNcdWM3ODVcdWQ1ODhcdWIyZTQuIFx1YzkwMFx1YWRkY1x1YjI5NCBcdWI1NDVcdWM3NDQgXHVhYzAwXHViODVjIDFtLCBcdWMxMzhcdWI4NWMgMW0gXHVkMDZjXHVhZTMwXHViODVjIFx1YWQ2Y1x1YzVlZFx1Yzc0NCBcdWIwOThcdWIyMDRcdWM1YzhcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0IFx1Y2U3OFx1Yzc0MCAoMSwxKVx1Yzc3NFx1YWNlMCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzU0NFx1Yjc5OCBcdWNlNzhcdWM3NDAgKDUsNSlcdWM3NzRcdWIyZTQuIFx1YzkwMFx1YWRkY1x1Yzc1OCBcdWI1NDVcdWM3NDQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbigxLDEpICgxLDIpICgxLDMpICgxLDQpICgxLDUpXHJcbigyLDEpICgyLDIpICgyLDMpICgyLDQpICgyLDUpXHJcbigzLDEpICgzLDIpICgzLDMpICgzLDQpICgzLDUpXHJcbig0LDEpICg0LDIpICg0LDMpICg0LDQpICg0LDUpXHJcbig1LDEpICg1LDIpICg1LDMpICg1LDQpICg1LDUpPFwvcHJlPlxyXG5cclxuPHA+XHVhZDZjXHVjNWVkIEtcdWFjMWNcdWI5N2MgXHVjODFjXHVjNjc4XHVkNTVjIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVhY2ZjIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjMmVjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gS1x1YWMxYyBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWIyOTQgXHVhYzcwXHViMzAwXHVkNTVjIFx1YjNjY1x1Yzc3NCBcdWM3ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzBhY1x1YWNmYyBcdWIwOThcdWJiMzRcdWFjMDAgXHVjMmVjXHVjNWI0XHVjODM4IFx1Yzc4OFx1YzljMCBcdWM1NGFcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YWNmY1x1Yjk3YyBcdWMyMThcdWQ2NTVcdWQ1NThcdWIyOTQgXHVjNzdjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWFkYzBcdWNjMmVcdWM3NDAgXHVjNzdjXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzkwMFx1YWRkY1x1YjI5NCBcdWNlNWNcdWFkNmMgXHVkNTc0XHViZTQ4XHVjNzc0XHVjNjQwIFx1ZDU2OFx1YWVkOCBcdWM3YWNcdWJjMGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzIxOFx1ZDY1NVx1Yzc0NCBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5MDBcdWFkZGNcdWIyOTQgKDEsMSlcdWM1ZDBcdWMxMWMgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YzIxOFx1ZDY1NVx1ZDU1OFx1YWUzMCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFjZTAsIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCAoNSw1KVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuICgxLDEpXHVhY2ZjICg1LDUpXHVjNWQwXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWMwYWNcdWFjZmMgXHViMDk4XHViYjM0XHVhYzAwIFx1YzJlY1x1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBhY1x1YWNmYyBcdWIwOThcdWJiMzQgXHVkNTU4XHViMDk4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YzIxOFx1ZDY1NVx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIFx1ZDU2ZFx1YzBjMSAzMFx1YmQ4NFx1Yzc3NFx1YjJlNC4gXHVjOTAwXHVhZGRjXHVjNjQwIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YWMwMCBcdWQ2MDRcdWM3YWMgXHVjNzg4XHViMjk0IFx1Y2U3OFx1Yzc1OCBcdWMwYWNcdWFjZmMgXHViMDk4XHViYjM0XHVjNWQwXHVjMTFjIFx1YzBhY1x1YWNmY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHVjMjE4XHVkNjU1XHVkNTU4XHViYTc0LCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjZTc4IFx1YzkxMSBcdWMwYWNcdWFjZmMgXHViMDk4XHViYjM0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjXHViMmU0LiBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1YjNjNCAzMFx1YmQ4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTAwXHVhZGRjXHVjNjQwIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWM5MDBcdWFkZGNcdWM3NTggXHViNTQ1XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YzIxOFx1ZDY1NVx1ZDU2MCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOVx1YzVkMFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YjljY1x1YjA5OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVjNzc0XHViODA3XHVhYzhjIFx1YzBhY1x1YWNmY1x1Yjk3YyBcdWMyMThcdWQ2NTVcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzBhY1x1Yjc4Y1x1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjMGFjXHVhY2ZjXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTU4XHViYTcwLCBcdWM3NzRcdWJiZjggXHVjMjE4XHVkNjU1XHVjNzQ0IFx1YjljOFx1Y2U1YyBcdWMwYWNcdWFjZmMgXHViMDk4XHViYjM0XHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3M2NcdWI4NWNcdWIyOTQgXHVjNzc0XHViM2Q5XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHViNjEwLCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3NDQgXHVjODFjXHVjNjc4XHVkNTU4XHVhY2UwIFx1YWMxOVx1Yzc0MCBcdWNlNzhcdWM1ZDBcdWMxMWMgXHViOWNjXHViMGEwIFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIEsgKDAgJmxlOyBLICZsZTsmbmJzcDsyMiwgS1x1YjI5NCBcdWM5ZGRcdWMyMTgpXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYWNcdWFjZmMgXHViMDk4XHViYjM0XHVhYzAwIFx1YzVjNlx1YjI5NCBcdWNlNzhcdWM3NTggXHVjNzA0XHVjZTU4IChpLGopXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YmMyOVx1YmM5NVx1YjMwMFx1Yjg1YyBcdWMwYWNcdWFjZmNcdWI5N2MgXHViYWE4XHViNDUwIFx1YzIxOFx1ZDY1NVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWMwYzFcdWQ2NjlcdWM3NDQgXHVhZGY4XHViOWJjXHVjNzNjXHViODVjIFx1YWRmOFx1YjlhY1x1YmE3NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LiBcdWM4MTAoLilcdWM3NDAgXHVjMGFjXHVhY2ZjIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjZTc4LCB4XHViMjk0IFx1YzVjNlx1YjI5NCBcdWNlNzhcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViYTcwLCBqXHViMjk0IFx1YzkwMFx1YWRkY1x1Yzc1OCBcdWM3MDRcdWNlNTgsIGhcdWIyOTQgXHVkNTc0XHViZTQ4XHVjNzc0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuaiAgLiAgLiAgLiAgLlxyXG5cclxuLiAgLiAgLiAgLiAgLlxyXG5cclxueCAgeCAgeCAgeCAgLlxyXG5cclxuLiAgLiAgLiAgLiAgLlxyXG5cclxuLiAgLiAgLiAgLiAgaFxyXG48XC9wcmU+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YzljMFx1ZDBhNFx1YmE3NFx1YzExYyBcdWMwYWNcdWFjZmNcdWI5N2MgXHViYWE4XHViNDUwIFx1YzIxOFx1ZDY1NVx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVkNTVjXHVhYzAwXHVjOWMwXHVjNzc0XHViYTcwLCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG5qICBqLS1qICBqLS1qXHJcbnwgIHwgIHwgIHwgIHxcclxuai0taiAgai0taiAgalxyXG4gICAgICAgICAgICB8XHJcbnggIHggIHggIHggalwvaFxyXG4gICAgICAgICAgICB8XHJcbmgtLWgtLWgtLWgtLWhcclxufFxyXG5oLS1oLS1oLS1oLS1oXHJcbjxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1OTEzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR3JhemluZyBQYXR0ZXJucyIsImRlc2NyaXB0aW9uIjoiPHA+RHVlIHRvIHJlY2VudCBidWRnZXQgY3V0cywgRkogaGFzIGRvd25zaXplZCBoaXMgZmFybSBzbyB0aGF0IHRoZSBncmF6aW5nIGFyZWEgZm9yIGhpcyBjb3dzIGlzIG9ubHkgYSA1IG1ldGVyIGJ5IDUgbWV0ZXIgc3F1YXJlIGZpZWxkISAmbmJzcDtUaGUgZmllbGQgaXMgbGFpZCBvdXQgbGlrZSBhIDV4NSBncmlkIG9mIDEgbWV0ZXIgYnkgMSBtZXRlciBzcXVhcmVzLCB3aXRoICgxLDEpIGJlaW5nIHRoZSBsb2NhdGlvbiBvZiB0aGUgdXBwZXItbGVmdCBzcXVhcmUsIGFuZCAoNSw1KSBiZWluZyB0aGUgbG9jYXRpb24gb2YgdGhlIGxvd2VyLXJpZ2h0IHNxdWFyZTo8XC9wPlxyXG5cclxuPHByZT5cclxuKDEsMSkgKDEsMikgKDEsMykgKDEsNCkgKDEsNSlcclxuKDIsMSkgKDIsMikgKDIsMykgKDIsNCkgKDIsNSlcclxuKDMsMSkgKDMsMikgKDMsMykgKDMsNCkgKDMsNSlcclxuKDQsMSkgKDQsMikgKDQsMykgKDQsNCkgKDQsNSlcclxuKDUsMSkgKDUsMikgKDUsMykgKDUsNCkgKDUsNSk8XC9wcmU+XHJcblxyXG48cD5FdmVyeSBzcXVhcmUgaW4gdGhpcyBncmlkIGlzIGZpbGxlZCB3aXRoIGRlbGljaW91cyBncmFzcywgZXhjZXB0IGZvciBLIGJhcnJlbiBzcXVhcmVzICgwICZsdDs9IEsgJmx0Oz0gMjIsIEsgZXZlbiksIHdoaWNoIGhhdmUgbm8gZ3Jhc3MuICZuYnNwO0Jlc3NpZSB0aGUgY293IHN0YXJ0cyBncmF6aW5nIGluIHNxdWFyZSAoMSwxKSwgd2hpY2ggaXMgYWx3YXlzIGZpbGxlZCB3aXRoIGdyYXNzLCBhbmQgTWlsZHJlZCB0aGUgY293IHN0YXJ0cyBncmF6aW5nIGluIHNxdWFyZSAoNSw1KSwgd2hpY2ggYWxzbyBpcyBhbHdheXMgZmlsbGVkIHdpdGggZ3Jhc3MuICZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGhhbGYtaG91ciwgQmVzc2llIGFuZCBNaWxkcmVkIGZpbmlzaCBlYXRpbmcgYWxsIHRoZSBncmFzcyBpbiB0aGVpciByZXNwZWN0aXZlIHNxdWFyZXMgYW5kIGVhY2ggYm90aCBtb3ZlIHRvIGFkamFjZW50IGdyYXNzeSBzcXVhcmVzIChub3J0aCwgc291dGgsIGVhc3QsIG9yIHdlc3QpLiAmbmJzcDtUaGV5IHdhbnQgdG8gY29uc3VtZSBhbGwgdGhlIGdyYXNzeSBzcXVhcmVzIGFuZCBlbmQgdXAgaW4gZXhhY3RseSB0aGUgc2FtZSBmaW5hbCBsb2NhdGlvbi4gJm5ic3A7UGxlYXNlIGNvbXB1dGUgdGhlIG51bWJlciBvZiBkaWZmZXJlbnQgd2F5cyB0aGlzIGNhbiBoYXBwZW4uICZuYnNwO0Jlc3NpZSBhbmQgTWlsZHJlZCBhbHdheXMgbW92ZSBvbnRvIGdyYXNzeSBzcXVhcmVzLCBhbmQgdGhleSBuZXZlciBib3RoIG1vdmUgb250byB0aGUgc2FtZSBzcXVhcmUgdW5sZXNzIHRoYXQgaXMgdGhlIHZlcnkgbGFzdCBncmFzc3kgc3F1YXJlIHJlbWFpbmluZy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUaGUgaW50ZWdlciBLLjxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLjErSzogRWFjaCBsaW5lIGNvbnRhaW5zIHRoZSBsb2NhdGlvbiAoaSxqKSBvZiBhIG5vbi1ncmFzc3kgc3F1YXJlIGJ5IGxpc3RpbmcgdGhlIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgaSBhbmQgai48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogVGhlIG51bWJlciBvZiBkaWZmZXJlbnQgcG9zc2libGUgd2F5cyBCZXNzaWUgYW5kIE1pbGRyZWQgY2FuIHdhbGsgYWNyb3NzIHRoZSBmaWVsZCB0byBlYXQgYWxsIHRoZSBncmFzcyBhbmQgZW5kIHVwIGluIHRoZSBzYW1lIGZpbmFsIGxvY2F0aW9uLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGUgaW5pdGlhbCBncmlkIGxvb2tzIGxpa2UgdGhpcyAod2hlcmUgLiBkZW5vdGVzIGEgZ3Jhc3N5IHNxdWFyZSwgeCBkZW5vdGVzIGEgbm9uLWdyYXNzeSBzcXVhcmUsIGIgaW5kaWNhdGVzIHRoZSBzdGFydGluZyBsb2NhdGlvbiBvZiBCZXNzaWUsIGFuZCBtIGluZGljYXRlcyB0aGUgc3RhcnRpbmcgbG9jYXRpb24gb2YgTWlsZHJlZCk6PFwvcD5cclxuXHJcbjxwcmU+XHJcbmogIC4gIC4gIC4gIC5cclxuXHJcbi4gIC4gIC4gIC4gIC5cclxuXHJcbnggIHggIHggIHggIC5cclxuXHJcbi4gIC4gIC4gIC4gIC5cclxuXHJcbi4gIC4gIC4gIC4gIGhcclxuPFwvcHJlPlxyXG5cclxuPHA+VGhlcmUgaXMgb25seSBvbmUgcG9zc2libGUgc29sdXRpb24sIHdpdGggQmVzc2llIGFuZCBNaWxkcmVkIG1lZXRpbmcgYXQgc3F1YXJlICgzLDUpOjxcL3A+XHJcblxyXG48cHJlPlxyXG5qICBqLS1qICBqLS1qXHJcbnwgIHwgIHwgIHwgIHxcclxuai0taiAgai0taiAgalxyXG4gICAgICAgICAgICB8XHJcbnggIHggIHggIHggalwvaFxyXG4gICAgICAgICAgICB8XHJcbmgtLWgtLWgtLWgtLWhcclxufFxyXG5oLS1oLS1oLS1oLS1oPGZvbnQgZmFjZT1cInNhbnMtc2VyaWYsIEFyaWFsLCBWZXJkYW5hLCBUcmVidWNoZXQgTVNcIj48c3BhbiBzdHlsZT1cIndoaXRlLXNwYWNlOm5vcm1hbFwiPlxyXG48XC9zcGFuPjxcL2ZvbnQ+PFwvcHJlPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2011-2012 Season > USACO January 2012 Contest > Bronze 3번