시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 505 289 220 55.138%

문제

대학교를 졸업한 준규는 농부의 꿈을 이루기 위해서 가로 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+XHVjOTAwXHVhZGRjXHVjNjQwIFx1ZDU3NFx1YmU0OFx1Yzc3NFx1YjI5NCBcdWM5MDBcdWFkZGNcdWM3NTggXHViNTQ1XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YzIxOFx1ZDY1NVx1ZDU2MCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOVx1YzVkMFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YjljY1x1YjA5OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMwYWNcdWFjZmNcdWI5N2MgXHVjMjE4XHVkNjU1XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YzBhY1x1YWNmY1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YmE3MCwgXHVjNzc0XHViYmY4IFx1YzIxOFx1ZDY1NVx1Yzc0NCBcdWI5YzhcdWNlNWMgXHVjMGFjXHVhY2ZjIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzNjXHViODVjXHViMjk0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuIFx1YjYxMCwgXHViOWM4XHVjOWMwXHViOWM5XHVjNzQ0IFx1YzgxY1x1YzY3OFx1ZDU1OFx1YWNlMCBcdWFjMTlcdWM3NDAgXHVjZTc4XHVjNWQwXHVjMTFjIFx1YjljY1x1YjBhMCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBLXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBLICgwICZsZTsgSyAmbGU7Jm5ic3A7MjIsIEtcdWIyOTQgXHVjOWRkXHVjMjE4KVx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVhY2ZjIFx1YjA5OFx1YmIzNFx1YWMwMCBcdWM1YzZcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YzcwNFx1Y2U1OCAoaSxqKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYjM4XHVjODFjXHVjNWQwXHVjMTFjIFx1YzhmY1x1YzViNFx1YzljNCBcdWJjMjlcdWJjOTVcdWIzMDBcdWI4NWMgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWMyMThcdWQ2NTVcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMGMxXHVkNjY5XHVjNzQ0IFx1YWRmOFx1YjliY1x1YzczY1x1Yjg1YyBcdWFkZjhcdWI5YWNcdWJhNzQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC4gXHVjODEwKC4pXHVjNzQwIFx1YzBhY1x1YWNmYyBcdWIwOThcdWJiMzRcdWFjMDAgXHVjNzg4XHViMjk0IFx1Y2U3OCwgeFx1YjI5NCBcdWM1YzZcdWIyOTQgXHVjZTc4XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgalx1YjI5NCBcdWM5MDBcdWFkZGNcdWM3NTggXHVjNzA0XHVjZTU4LCBoXHViMjk0IFx1ZDU3NFx1YmU0OFx1Yzc3NFx1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbmogIC4gIC4gIC4gIC5cclxuXHJcbi4gIC4gIC4gIC4gIC5cclxuXHJcbnggIHggIHggIHggIC5cclxuXHJcbi4gIC4gIC4gIC4gIC5cclxuXHJcbi4gIC4gIC4gIC4gIGhcclxuPFwvcHJlPlxyXG5cclxuPHA+XHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWM5YzBcdWQwYTRcdWJhNzRcdWMxMWMgXHVjMGFjXHVhY2ZjXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWMyMThcdWQ2NTVcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1ZDU1Y1x1YWMwMFx1YzljMFx1Yzc3NFx1YmE3MCwgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuaiAgai0taiAgai0talxyXG58ICB8ICB8ICB8ICB8XHJcbmotLWogIGotLWogIGpcclxuICAgICAgICAgICAgfFxyXG54ICB4ICB4ICB4IGpcL2hcclxuICAgICAgICAgICAgfFxyXG5oLS1oLS1oLS1oLS1oXHJcbnxcclxuaC0taC0taC0taC0taFxyXG48XC9wcmU+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTkxMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdyYXppbmcgUGF0dGVybnMiLCJkZXNjcmlwdGlvbiI6IjxwPkR1ZSB0byByZWNlbnQgYnVkZ2V0IGN1dHMsIEZKIGhhcyBkb3duc2l6ZWQgaGlzIGZhcm0gc28gdGhhdCB0aGUgZ3JhemluZyBhcmVhIGZvciBoaXMgY293cyBpcyBvbmx5IGEgNSBtZXRlciBieSA1IG1ldGVyIHNxdWFyZSBmaWVsZCEgJm5ic3A7VGhlIGZpZWxkIGlzIGxhaWQgb3V0IGxpa2UgYSA1eDUgZ3JpZCBvZiAxIG1ldGVyIGJ5IDEgbWV0ZXIgc3F1YXJlcywgd2l0aCAoMSwxKSBiZWluZyB0aGUgbG9jYXRpb24gb2YgdGhlIHVwcGVyLWxlZnQgc3F1YXJlLCBhbmQgKDUsNSkgYmVpbmcgdGhlIGxvY2F0aW9uIG9mIHRoZSBsb3dlci1yaWdodCBzcXVhcmU6PFwvcD5cclxuXHJcbjxwcmU+XHJcbigxLDEpICgxLDIpICgxLDMpICgxLDQpICgxLDUpXHJcbigyLDEpICgyLDIpICgyLDMpICgyLDQpICgyLDUpXHJcbigzLDEpICgzLDIpICgzLDMpICgzLDQpICgzLDUpXHJcbig0LDEpICg0LDIpICg0LDMpICg0LDQpICg0LDUpXHJcbig1LDEpICg1LDIpICg1LDMpICg1LDQpICg1LDUpPFwvcHJlPlxyXG5cclxuPHA+RXZlcnkgc3F1YXJlIGluIHRoaXMgZ3JpZCBpcyBmaWxsZWQgd2l0aCBkZWxpY2lvdXMgZ3Jhc3MsIGV4Y2VwdCBmb3IgSyBiYXJyZW4gc3F1YXJlcyAoMCAmbHQ7PSBLICZsdDs9IDIyLCBLIGV2ZW4pLCB3aGljaCBoYXZlIG5vIGdyYXNzLiAmbmJzcDtCZXNzaWUgdGhlIGNvdyBzdGFydHMgZ3JhemluZyBpbiBzcXVhcmUgKDEsMSksIHdoaWNoIGlzIGFsd2F5cyBmaWxsZWQgd2l0aCBncmFzcywgYW5kIE1pbGRyZWQgdGhlIGNvdyBzdGFydHMgZ3JhemluZyBpbiBzcXVhcmUgKDUsNSksIHdoaWNoIGFsc28gaXMgYWx3YXlzIGZpbGxlZCB3aXRoIGdyYXNzLiAmbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBoYWxmLWhvdXIsIEJlc3NpZSBhbmQgTWlsZHJlZCBmaW5pc2ggZWF0aW5nIGFsbCB0aGUgZ3Jhc3MgaW4gdGhlaXIgcmVzcGVjdGl2ZSBzcXVhcmVzIGFuZCBlYWNoIGJvdGggbW92ZSB0byBhZGphY2VudCBncmFzc3kgc3F1YXJlcyAobm9ydGgsIHNvdXRoLCBlYXN0LCBvciB3ZXN0KS4gJm5ic3A7VGhleSB3YW50IHRvIGNvbnN1bWUgYWxsIHRoZSBncmFzc3kgc3F1YXJlcyBhbmQgZW5kIHVwIGluIGV4YWN0bHkgdGhlIHNhbWUgZmluYWwgbG9jYXRpb24uICZuYnNwO1BsZWFzZSBjb21wdXRlIHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHdheXMgdGhpcyBjYW4gaGFwcGVuLiAmbmJzcDtCZXNzaWUgYW5kIE1pbGRyZWQgYWx3YXlzIG1vdmUgb250byBncmFzc3kgc3F1YXJlcywgYW5kIHRoZXkgbmV2ZXIgYm90aCBtb3ZlIG9udG8gdGhlIHNhbWUgc3F1YXJlIHVubGVzcyB0aGF0IGlzIHRoZSB2ZXJ5IGxhc3QgZ3Jhc3N5IHNxdWFyZSByZW1haW5pbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVGhlIGludGVnZXIgSy48XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi4xK0s6IEVhY2ggbGluZSBjb250YWlucyB0aGUgbG9jYXRpb24gKGksaikgb2YgYSBub24tZ3Jhc3N5IHNxdWFyZSBieSBsaXN0aW5nIHRoZSB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIGkgYW5kIGouPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFRoZSBudW1iZXIgb2YgZGlmZmVyZW50IHBvc3NpYmxlIHdheXMgQmVzc2llIGFuZCBNaWxkcmVkIGNhbiB3YWxrIGFjcm9zcyB0aGUgZmllbGQgdG8gZWF0IGFsbCB0aGUgZ3Jhc3MgYW5kIGVuZCB1cCBpbiB0aGUgc2FtZSBmaW5hbCBsb2NhdGlvbi48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhlIGluaXRpYWwgZ3JpZCBsb29rcyBsaWtlIHRoaXMgKHdoZXJlIC4gZGVub3RlcyBhIGdyYXNzeSBzcXVhcmUsIHggZGVub3RlcyBhIG5vbi1ncmFzc3kgc3F1YXJlLCBiIGluZGljYXRlcyB0aGUgc3RhcnRpbmcgbG9jYXRpb24gb2YgQmVzc2llLCBhbmQgbSBpbmRpY2F0ZXMgdGhlIHN0YXJ0aW5nIGxvY2F0aW9uIG9mIE1pbGRyZWQpOjxcL3A+XHJcblxyXG48cHJlPlxyXG5qICAuICAuICAuICAuXHJcblxyXG4uICAuICAuICAuICAuXHJcblxyXG54ICB4ICB4ICB4ICAuXHJcblxyXG4uICAuICAuICAuICAuXHJcblxyXG4uICAuICAuICAuICBoXHJcbjxcL3ByZT5cclxuXHJcbjxwPlRoZXJlIGlzIG9ubHkgb25lIHBvc3NpYmxlIHNvbHV0aW9uLCB3aXRoIEJlc3NpZSBhbmQgTWlsZHJlZCBtZWV0aW5nIGF0IHNxdWFyZSAoMyw1KTo8XC9wPlxyXG5cclxuPHByZT5cclxuaiAgai0taiAgai0talxyXG58ICB8ICB8ICB8ICB8XHJcbmotLWogIGotLWogIGpcclxuICAgICAgICAgICAgfFxyXG54ICB4ICB4ICB4IGpcL2hcclxuICAgICAgICAgICAgfFxyXG5oLS1oLS1oLS1oLS1oXHJcbnxcclxuaC0taC0taC0taC0taDxmb250IGZhY2U9XCJzYW5zLXNlcmlmLCBBcmlhbCwgVmVyZGFuYSwgVHJlYnVjaGV0IE1TXCI+PHNwYW4gc3R5bGU9XCJ3aGl0ZS1zcGFjZTpub3JtYWxcIj5cclxuPFwvc3Bhbj48XC9mb250PjxcL3ByZT5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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