시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 268 132 118 50.000%

문제

다른 소들과 마찬가지로 베시는 십자말풀이 퍼즐을 푸는 것을 좋아한다. 하지만 그녀의 누나 엘시는 베시의 십자말풀이 퍼즐책에 우유를 쏟아 글자들을 더럽혀 베시가 각 힌트가 어디서 시작하는지 알기 힘들게 만들어 놓았다. 베시를 도와 각 힌트의 번호를 알아내자!

아무런 표기가 되어있지 않은 N X M 격자의 십자말풀이가 주어질 것이다(3 <= N <= 50, 3 <= M <= 50). 어떤 칸들은 비어 있을 것이고(하얗게 칠해진) 그리고 어떤 칸들은 막혀있을 것이다(검정색으로 칠해진). 이런 격자에서 힌트의 번호를 알아내는 것은 다음과 같은 두 가지 간단한 단계를 거친다.

단계 1: 우리는 먼저 각 칸이 세로로 이어지는 단서의 시작점인지 가로로 이어지는 단서의 시작점인지 알아낼 것이다. 만약 그 칸이 가로로 이어지는 단서의 시작점이면 그 칸은 비어있으면서 왼쪽 칸이 막혀있거나 격자 밖이어야 하고, 오른쪽에 있는 두 개 이상의 칸은 비어있어야한다(가로로 이어지는 말은 3글자 이상이라는 것을 알 수 있다). 만약 그 칸이 세로로 이어지는 단서의 시작점일 경우에도 비슷하다 : 그 칸은 비어있으면서 그 위의 칸은 막혀있거나 격자의 바깥이며, 아래로 두 개이상의 칸은 비어있어야 한다.

단계 2 : 이제 단서의 시작점에 해당하는 칸마다 번호를 매길 것이다. 번호는 책을 읽는 순서와 동일하게 왼쪽 위부터 오른쪽 아래까지 행 우선으로 순서대로 매긴다.

...
#..
...
..#
.##

어떤 단서의 시작이 되는 칸은 !로 되어있다.

!!!
#..
!..
..#
.##

여기에다 숫자를 매기게되면 다음과 같아진다.

123
#..
4..
..#
.##

아래에 나오는 입력은 보통 출판되는 십자말풀이 퍼즐의 규칙을 따르지 않는다는 것을 기억해둬라. 예를 들어 어떤 비어있는 칸들은 어떠한 단서들에도 포함 안될 수도 있다.

입력

첫줄의 입력은 N과 M이 공백을 두고 주어진다.

다음 N줄에는 격자의 각 행들의 입력이 이루어진다. 각 행은 M개의 문자를 포함하고 있으며 각 문자는 '.'(비어있는 칸)이거나 '#'(막혀있는 칸)이다.

출력

출력의 첫 줄에는 단서들의 수를 출력한다.

다른 줄에는 각 힌트들의 시작 위치의 칸을 (행,열)의 꼴로 출력한다. 맨위 왼쪽칸은 (1,1)이고 맨 아래 오른쪽 칸은 (N,M)이다.

출력하는 순서는 위에서 설명한대로 번호를 매긴 순서로 한다.

예제 입력 1

5 3
...
#..
...
..#
.##

예제 출력 1

4
1 1
1 2
1 3
3 1
W3sicHJvYmxlbV9pZCI6IjEwNjU2IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMmVkXHVjNzkwXHViOWQwXHVkNDgwXHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWIyZTRcdWI5NzggXHVjMThjXHViNGU0XHVhY2ZjIFx1YjljOFx1Y2MyY1x1YWMwMFx1YzljMFx1Yjg1YyBcdWJjYTBcdWMyZGNcdWIyOTQgXHVjMmVkXHVjNzkwXHViOWQwXHVkNDgwXHVjNzc0IFx1ZDM3Y1x1Yzk5MFx1Yzc0NCBcdWQ0NzhcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1YWRmOFx1YjE0MFx1Yzc1OCBcdWIyMDRcdWIwOTggXHVjNWQ4XHVjMmRjXHViMjk0IFx1YmNhMFx1YzJkY1x1Yzc1OCBcdWMyZWRcdWM3OTBcdWI5ZDBcdWQ0ODBcdWM3NzQgXHVkMzdjXHVjOTkwXHVjYzQ1XHVjNWQwIFx1YzZiMFx1YzcyMFx1Yjk3YyBcdWMzZGZcdWM1NDQgXHVhZTAwXHVjNzkwXHViNGU0XHVjNzQ0IFx1YjM1NFx1YjdmZFx1ZDYwMCZuYnNwO1x1YmNhMFx1YzJkY1x1YWMwMCBcdWFjMDEgXHVkNzhjXHVkMmI4XHVhYzAwIFx1YzViNFx1YjUxNFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTRcdWM5YzAgXHVjNTRjXHVhZTMwIFx1ZDc5OFx1YjRlNFx1YWM4YyBcdWI5Y2NcdWI0ZTRcdWM1YjQgXHViMTkzXHVjNTU4XHViMmU0LiBcdWJjYTBcdWMyZGNcdWI5N2MgXHViM2M0XHVjNjQwIFx1YWMwMSBcdWQ3OGNcdWQyYjhcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1Yzc5MCE8XC9wPlxyXG5cclxuPHA+XHVjNTQ0XHViYjM0XHViN2YwJm5ic3A7XHVkNDVjXHVhZTMwXHVhYzAwIFx1YjQxOFx1YzViNFx1Yzc4OFx1YzljMCBcdWM1NGFcdWM3NDAgTiBYIE0gXHVhY2E5XHVjNzkwXHVjNzU4IFx1YzJlZFx1Yzc5MFx1YjlkMFx1ZDQ4MFx1Yzc3NFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHVhYzgzXHVjNzc0XHViMmU0KDMgJmx0Oz0gTiAmbHQ7PSA1MCwgMyAmbHQ7PSBNICZsdDs9IDUwKS4gXHVjNWI0XHViNWE0IFx1Y2U3OFx1YjRlNFx1Yzc0MCZuYnNwO1x1YmU0NFx1YzViNCZuYnNwO1x1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWFjZTAoXHVkNTU4XHVjNTk3XHVhYzhjIFx1Y2U2MFx1ZDU3NFx1YzljNCkgXHVhZGY4XHViOWFjXHVhY2UwIFx1YzViNFx1YjVhNCBcdWNlNzhcdWI0ZTRcdWM3NDAgXHViOWM5XHVkNjAwXHVjNzg4XHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNChcdWFjODBcdWM4MTVcdWMwYzlcdWM3M2NcdWI4NWMgXHVjZTYwXHVkNTc0XHVjOWM0KS4gXHVjNzc0XHViN2YwIFx1YWNhOVx1Yzc5MFx1YzVkMFx1YzExYyBcdWQ3OGNcdWQyYjhcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YzU0Y1x1YzU0NFx1YjBiNFx1YjI5NCBcdWFjODNcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWI0NTAmbmJzcDtcdWFjMDBcdWM5YzAgXHVhYzA0XHViMmU4XHVkNTVjIFx1YjJlOFx1YWNjNFx1Yjk3YyBcdWFjNzBcdWNlNWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YWNjNCAxOiBcdWM2YjBcdWI5YWNcdWIyOTQgXHViYTNjXHVjODAwIFx1YWMwMSBcdWNlNzhcdWM3NzQmbmJzcDtcdWMxMzhcdWI4NWNcdWI4NWMgXHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IFx1YjJlOFx1YzExY1x1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3NzhcdWM5YzAmbmJzcDtcdWFjMDBcdWI4NWNcdWI4NWMgXHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IFx1YjJlOFx1YzExY1x1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3NzhcdWM5YzAmbmJzcDtcdWM1NGNcdWM1NDRcdWIwYmMgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhZGY4IFx1Y2U3OFx1Yzc3NCBcdWFjMDBcdWI4NWNcdWI4NWMgXHVjNzc0XHVjNWI0XHVjOWMwXHViMjk0IFx1YjJlOFx1YzExY1x1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM3NzRcdWJhNzQmbmJzcDtcdWFkZjggXHVjZTc4XHVjNzQwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YzczY1x1YmE3NFx1YzExYyZuYnNwO1x1YzY3Y1x1Y2FiZCBcdWNlNzhcdWM3NzQgXHViOWM5XHVkNjAwXHVjNzg4XHVhYzcwXHViMDk4IFx1YWNhOVx1Yzc5MCBcdWJjMTZcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxXHVjNzU4IFx1Y2U3OFx1Yzc0MCBcdWJlNDRcdWM1YjRcdWM3ODhcdWM1YjRcdWM1N2NcdWQ1NWNcdWIyZTQoXHVhYzAwXHViODVjXHViODVjIFx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBcdWI5ZDBcdWM3NDAgM1x1YWUwMFx1Yzc5MCBcdWM3NzRcdWMwYzFcdWM3NzRcdWI3N2NcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0KS4gXHViOWNjXHVjNTdkIFx1YWRmOCBcdWNlNzhcdWM3NzQgXHVjMTM4XHViODVjXHViODVjIFx1Yzc3NFx1YzViNFx1YzljMFx1YjI5NCBcdWIyZThcdWMxMWNcdWM3NTggXHVjMmRjXHVjNzkxXHVjODEwXHVjNzdjIFx1YWNiZFx1YzZiMFx1YzVkMFx1YjNjNCBcdWJlNDRcdWMyYjdcdWQ1NThcdWIyZTQgOiBcdWFkZjggXHVjZTc4XHVjNzQwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YzczY1x1YmE3NFx1YzExYyBcdWFkZjggXHVjNzA0XHVjNzU4IFx1Y2U3OFx1Yzc0MCBcdWI5YzlcdWQ2MDBcdWM3ODhcdWFjNzBcdWIwOTggXHVhY2E5XHVjNzkwXHVjNzU4IFx1YmMxNFx1YWU2NVx1Yzc3NFx1YmE3MCwgXHVjNTQ0XHViNzk4XHViODVjIFx1YjQ1MCBcdWFjMWNcdWM3NzRcdWMwYzFcdWM3NTggXHVjZTc4XHVjNzQwIFx1YmU0NFx1YzViNFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlOFx1YWNjNCAyIDogXHVjNzc0XHVjODFjIFx1YjJlOFx1YzExY1x1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM1ZDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1Y2U3OFx1YjljOFx1YjJlNCBcdWJjODhcdWQ2MzhcdWI5N2MgXHViOWU0XHVhZTM4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViYzg4XHVkNjM4XHViMjk0IFx1Y2M0NVx1Yzc0NCBcdWM3N2RcdWIyOTQgXHVjMjFjXHVjMTFjXHVjNjQwIFx1YjNkOVx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWM2N2NcdWNhYmQgXHVjNzA0XHViZDgwXHVkMTMwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OThcdWFlNGNcdWM5YzAgXHVkNTg5IFx1YzZiMFx1YzEyMFx1YzczY1x1Yjg1YyBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViOWU0XHVhZTM0XHViMmU0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4uLi5cclxuIy4uXHJcbi4uLlxyXG4uLiNcclxuLiMjPFwvcHJlPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YjJlOFx1YzExY1x1Yzc1OCBcdWMyZGNcdWM3OTFcdWM3NzQgXHViNDE4XHViMjk0IFx1Y2U3OFx1Yzc0MCAhXHViODVjIFx1YjQxOFx1YzViNFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuISEhXHJcbiMuLlxyXG4hLi5cclxuLi4jXHJcbi4jIzxcL3ByZT5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzVkMFx1YjJlNCBcdWMyMmJcdWM3OTBcdWI5N2MgXHViOWU0XHVhZTMwXHVhYzhjXHViNDE4XHViYTc0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM1NDRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbjEyM1xyXG4jLi5cclxuNC4uXHJcbi4uI1xyXG4uIyM8XC9wcmU+XHJcblxyXG48cD5cdWM1NDRcdWI3OThcdWM1ZDAgXHViMDk4XHVjNjI0XHViMjk0IFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWJjZjRcdWQxYjUgXHVjZDljXHVkMzEwXHViNDE4XHViMjk0IFx1YzJlZFx1Yzc5MFx1YjlkMFx1ZDQ4MFx1Yzc3NCBcdWQzN2NcdWM5OTBcdWM3NTggXHVhZGRjXHVjZTU5XHVjNzQ0IFx1YjUzMFx1Yjk3NFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWUzMFx1YzViNVx1ZDU3NFx1YjQ2Y1x1Yjc3Yy4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM1YjRcdWI1YTQgXHViZTQ0XHVjNWI0XHVjNzg4XHViMjk0IFx1Y2U3OFx1YjRlNFx1Yzc0MCBcdWM1YjRcdWI1YTBcdWQ1NWMgXHViMmU4XHVjMTFjXHViNGU0XHVjNWQwXHViM2M0IFx1ZDNlY1x1ZDU2OCBcdWM1NDhcdWI0MjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzkwNFx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NDAgTlx1YWNmYyBNXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjYTlcdWM3OTBcdWM3NTggXHVhYzAxIFx1ZDU4OVx1YjRlNFx1Yzc1OCBcdWM3ODVcdWI4MjVcdWM3NzQgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkNTg5XHVjNzQwIE1cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViOTdjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzAgXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YjI5NCAmIzM5Oy4mIzM5OyhcdWJlNDRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjZTc4KVx1Yzc3NFx1YWM3MFx1YjA5OCAmIzM5OyMmIzM5OyhcdWI5YzlcdWQ2MDBcdWM3ODhcdWIyOTQgXHVjZTc4KVx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIyZThcdWMxMWNcdWI0ZTRcdWM3NTggXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHViOTc4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkNzhjXHVkMmI4XHViNGU0XHVjNzU4IFx1YzJkY1x1Yzc5MSBcdWM3MDRcdWNlNThcdWM3NTggXHVjZTc4XHVjNzQ0Jm5ic3A7KFx1ZDU4OSxcdWM1ZjQpXHVjNzU4IFx1YWYzNFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjllOFx1YzcwNCBcdWM2N2NcdWNhYmRcdWNlNzhcdWM3NDAgKDEsMSlcdWM3NzRcdWFjZTAgXHViOWU4IFx1YzU0NFx1Yjc5OCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjZTc4XHVjNzQwIChOLE0pXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMjk0IFx1YzcwNFx1YzVkMFx1YzExYyBcdWMxMjRcdWJhODVcdWQ1NWNcdWIzMDBcdWI4NWMgXHViYzg4XHVkNjM4XHViOTdjIFx1YjllNFx1YWUzNCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTA2NTYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDcm9zc3dvcmRzIiwiZGVzY3JpcHRpb24iOiI8cD5MaWtlIGFsbCBjb3dzLCBCZXNzaWUgdGhlIGNvdyBsaWtlcyB0byBzb2x2ZSBjcm9zc3dvcmQgcHV6emxlcy4gVW5mb3J0dW5hdGVseSwgaGVyIHNpc3RlciBFbHNpZSBoYXMgc3BpbGxlZCBtaWxrIGFsbCBvdmVyIGhlciBib29rIG9mIGNyb3Nzd29yZHMsIHNtZWFyaW5nIHRoZSB0ZXh0IGFuZCBtYWtpbmcgaXQgZGlmZmljdWx0IGZvciBoZXIgdG8gc2VlIHdoZXJlIGVhY2ggY2x1ZSBiZWdpbnMuICZuYnNwO0l0JiMzOTtzIHlvdXIgam9iIHRvIGhlbHAgQmVzc2llIG91dCBhbmQgcmVjb3ZlciB0aGUgY2x1ZSBudW1iZXJpbmchPFwvcD5cclxuXHJcbjxwPkFuIHVubGFiZWxlZCBjcm9zc3dvcmQgaXMgZ2l2ZW4gdG8geW91IGFzIGFuIE4gYnkgTSBncmlkICgzICZsdDs9IE4gJmx0Oz0gNTAsIDMgJmx0Oz0gTSAmbHQ7PSA1MCkuICZuYnNwO1NvbWUgY2VsbHMgd2lsbCBiZSBjbGVhciAodHlwaWNhbGx5IGNvbG9yZWQgd2hpdGUpIGFuZCBzb21lIGNlbGxzIHdpbGwgYmUgYmxvY2tlZCAodHlwaWNhbGx5IGNvbG9yZWQgYmxhY2spLiBHaXZlbiB0aGlzIGxheW91dCwgY2x1ZSBudW1iZXJpbmcgaXMgYSBzaW1wbGUgcHJvY2VzcyB3aGljaCBmb2xsb3dzIHR3byBsb2dpY2FsIHN0ZXBzOjxcL3A+XHJcblxyXG48cD5TdGVwIDE6IFdlIGRldGVybWluZSBpZiBhIGVhY2ggY2VsbCBiZWdpbnMgYSBob3Jpem9udGFsIG9yIHZlcnRpY2FsIGNsdWUuICZuYnNwO0lmIGEgY2VsbCBiZWdpbnMgYSBob3Jpem9udGFsIGNsdWUsIGl0IG11c3QgYmUgY2xlYXIsIGl0cyBuZWlnaGJvcmluZyBjZWxsIHRvIHRoZSBsZWZ0IG11c3QgYmUgYmxvY2tlZCBvciBvdXRzaWRlIHRoZSBjcm9zc3dvcmQgZ3JpZCwgYW5kIHRoZSB0d28gY2VsbHMgb24gaXRzIHJpZ2h0IG11c3QgYmUgY2xlYXIgKHRoYXQgaXMsIGEgaG9yaXpvbnRhbCBjbHVlIGNhbiBvbmx5IHJlcHJlc2VudCBhIHdvcmQgb2YgMyBvciBtb3JlIGNoYXJhY3RlcnMpLlRoZSBydWxlcyBmb3IgYSBjZWxsIGJlZ2lubmluZyBhIHZlcnRpY2FsIGNsdWUgYXJlIGFuYWxvZ291czogdGhlIGNlbGwgYWJvdmUgbXVzdCBiZSBibG9ja2VkIG9yIG91dHNpZGUgdGhlIGdyaWQsIGFuZCB0aGUgdHdvIGNlbGxzIGJlbG93IG11c3QgYmUgY2xlYXIuPFwvcD5cclxuXHJcbjxwPlN0ZXAgMjogV2UgYXNzaWduIGEgbnVtYmVyIHRvIGVhY2ggY2VsbCB0aGF0IGJlZ2lucyBhIGNsdWUuICZuYnNwO0NlbGxzIGFyZSBhc3NpZ25lZCBudW1iZXJzIHNlcXVlbnRpYWxseSBzdGFydGluZyB3aXRoIDEgaW4gdGhlIHNhbWUgb3JkZXIgdGhhdCB5b3Ugd291bGQgcmVhZCBhIGJvb2s7IGNlbGxzIGluIHRoZSB0b3Agcm93IGFyZSBhc3NpZ25lZCBudW1iZXJzIGZyb20gbGVmdCB0byByaWdodCwgdGhlbiB0aGUgc2Vjb25kIHJvdywgZXRjLiAmbmJzcDtPbmx5IGNlbGxzIGJlZ2lubmluZyBhIGNsdWUgYXJlIGFzc2lnbmVkIG51bWJlcnMuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBjb25zaWRlciB0aGUgZ3JpZCwgd2hlcmUgJiMzOTsuJiMzOTsgaW5kaWNhdGVzIGEgY2xlYXIgY2VsbCBhbmQgJiMzOTsjJiMzOTsgYSBibG9ja2VkIGNlbGwuPFwvcD5cclxuXHJcbjxwcmU+XHJcbi4uLlxyXG4jLi5cclxuLi4uXHJcbi4uI1xyXG4uIyM8XC9wcmU+XHJcblxyXG48cD5DZWxscyB0aGF0IGNhbiBiZWdpbiBhIGhvcml6b250YWwgb3IgdmVydGljYWwgY2x1ZSBhcmUgbWFya2VkIHdpdGggISBiZWxvdzo8XC9wPlxyXG5cclxuPHByZT5cclxuISEhXHJcbiMuLlxyXG4hLi5cclxuLi4jXHJcbi4jIzxcL3ByZT5cclxuXHJcbjxwPklmIHdlIGFzc2lnbiBudW1iZXJzIHRvIHRoZXNlIGNlbGxzLCB3ZSBnZXQgdGhlIGZvbGxvd2luZzs8XC9wPlxyXG5cclxuPHByZT5cclxuMTIzXHJcbiMuLlxyXG40Li5cclxuLi4jXHJcbi4jIzxcL3ByZT5cclxuXHJcbjxwPk5vdGUgdGhhdCBjcm9zc3dvcmQgZGVzY3JpYmVkIGluIHRoZSBpbnB1dCBkYXRhIG1heSBub3Qgc2F0aXNmeSBjb25zdHJhaW50cyB0eXBpY2FsbHkgc2VlbiBpbiBwdWJsaXNoZWQgY3Jvc3N3b3Jkcy4gJm5ic3A7Rm9yIGV4YW1wbGUsIHNvbWUgY2xlYXIgY2VsbHMgbWF5IG5vdCBiZSBwYXJ0IG9mIGFueSBjbHVlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgTiBhbmQgTSBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG5cclxuPHA+VGhlIG5leHQgTiBsaW5lcyBvZiBpbnB1dCBlYWNoIGRlc2NyaWJlIGEgcm93IG9mIHRoZSBncmlkLiAmbmJzcDtFYWNoIGNvbnRhaW5zIE0gY2hhcmFjdGVycywgd2hpY2ggYXJlIGVpdGhlciAmIzM5Oy4mIzM5OyAoYSBjbGVhciBjZWxsKSBvciAmIzM5OyMmIzM5OyAoYSBibG9ja2VkIGNlbGwpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uIHRoZSBmaXJzdCBsaW5lIG9mIG91dHB1dCwgcHJpbnQgdGhlIG51bWJlciBvZiBjbHVlcy48XC9wPlxyXG5cclxuPHA+T24gdGhlIGVhY2ggcmVtYWluaW5nIGxpbmUsIHByaW50IHRoZSByb3cgYW5kIGNvbHVtbiBnaXZpbmcgdGhlIHBvc2l0aW9uIG9mIGEgc2luZ2xlIGNsdWUgKG9yZGVyZWQgYXMgZGVzY3JpYmVkIGFib3ZlKS4gJm5ic3A7VGhlIHRvcCBsZWZ0IGNlbGwgaGFzIHBvc2l0aW9uICgxLCAxKS4gJm5ic3A7VGhlIGJvdHRvbSByaWdodCBjZWxsIGhhcyBwb3NpdGlvbiAoTiwgTSkuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2014-2015 Season > USACO December 2014 Contest > Bronze 2번

  • 빠진 조건을 찾은 사람: Green55
  • 문제를 번역한 사람: shhj1998