시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 25 15 8 61.538%

문제

유명한 마이크로프로세서 회사 letnI는 컴퓨터용 칩 위에 몇 개의 교체 가능한 부품(위젯)을 배치하는 일을 위해 당신의 도움을 필요로 한다. 각 칩은 NxN개의 정사각형 슬롯으로  이루어져 있다. 하나의 슬롯에는 하나의 위젯을 끼워 넣을 수 있으며, 최대한 많은 위젯을 끼워넣는 것이 목표이다.

최근의 프로세서 디자인들은 매우 복잡하기 때문에 당신은 운 나쁘게도 아래와 같은 제한들을 지켜야 한다.

  • 어떤 슬롯들은 사용할 수 없다.
  • 어떤 슬롯들은 다른 부품에 의해 이미 사용되고 있는 중이라서 새로운 위젯을 끼울 수 없다.
  • 칩의 수평한 변과 수직한 변을 연결하는 형제 메모리 버스가 있기 때문에 그들의 대역폭을 같게 만들어야 한다. 그러기 위해서는 i 번째 행에 있는 부품의 개수와 i 번째 열에 있는 부품의 개수가 같으면 되며, 부품의 개수는 이미 사용되고 있는 부품의 수와 새로 추가한 위젯의 수를 포함해서 세어야 한다.
  • 또한 비슷하게, 전원 공급기가 각 행과 열의 끝에 연결될 것이다. 과열을 막기 위해서는 어떤 행이나 열에 있는 부품의 개수와 전체 칩 위에 있는 부품의 개수의 비율이 A/B 초과가 되면 안 된다. (A와 B는 각 칩에 대해 주어진다)

하나의 칩은 N개의 문자로 이루어진 N개의 줄로 주어질 것이다. '.'은 열려있는(아직 사용되지 않은)슬롯이고, '/'은 사용할 수 없는 슬롯, 그리고 'C'는 이미 다른 부품에 의해 사용되고 있는 슬롯이다. 예를 들어 다음과 같은 칩을 생각해보자.

CC/..
././/
..C.C
/.C..
/./C/

만약 한 행이나 열에 3/10이상의 부품이 있어서는 안 된다고 하면, 이 칩 위에 최대한으로 추가할 수 있는 위젯의 개수는 7개가 된다. 가능한 배치는 아래에 있으며 'W'는 열려있는 슬롯에 추가된 위젯을 나타낸다.

CC/W.
W/W//
W.C.C
/.CWW
/W/C/

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스의 시작하는 줄은 세가지 정수로 이루어져 있다: 칩의 크기 N (1 ≤ N ≤ 40), 그리고 위에서 설명한 비율을 의미하는 A와 B(1 ≤ B ≤ 1000, 0 ≤ A ≤ B). 그리고 다음 N개의 줄은 슬롯의 상태를 나타내며 각 줄마다 N개의 문자가 주어진다. 각 문자는 '.','/' 또는 'C'이며 이는 위에서 설명한 대로이다.

마지막 테스트 케이스는 0 세 개로 이루어져 있다.

출력

각 테스트 케이스에 대해 각 줄은 테스트 케이스의 숫자로 시작한다. 만약 가능한 위젯 배치가 있다면 칩 위에 추가할 수 있는 위젯의 최대 개수를 출력한다. 가능한 배치가 없다면 "impossible"을 출력하면 된다.

예제 출력을 따라서 하면 된다.

예제 입력 1

2 1 1
/.
//
2 50 100
/.
C/
2 100 100
./
C.
5 3 10
CC/..
././/
..C.C
/.C..
/./C/
5 2 10
CC/..
././/
..C.C
/.C..
/./C/
0 0 0

예제 출력 1

Case 1: 0
Case 2: 1
Case 3: impossible
Case 4: 7
Case 5: impossible
W3sicHJvYmxlbV9pZCI6IjQyMTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNjkgXHVjMTI0XHVhY2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3MjBcdWJhODVcdWQ1NWMgXHViOWM4XHVjNzc0XHVkMDZjXHViODVjXHVkNTA0XHViODVjXHVjMTM4XHVjMTFjIFx1ZDY4Y1x1YzBhYyBsZXRuSVx1YjI5NCBcdWNlZjRcdWQ0ZThcdWQxMzBcdWM2YTkgXHVjZTY5IFx1YzcwNFx1YzVkMCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YWQ1MFx1Y2NiNCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViZDgwXHVkNDg4KFx1YzcwNFx1YzgyZilcdWM3NDQgXHViYzMwXHVjZTU4XHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc0NCBcdWM3MDRcdWQ1NzQgXHViMmY5XHVjMmUwXHVjNzU4IFx1YjNjNFx1YzZjMFx1Yzc0NCBcdWQ1NDRcdWM2OTRcdWI4NWMgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHVjZTY5XHVjNzQwIE54Tlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjMmFjXHViODZmXHVjNzNjXHViODVjICZuYnNwO1x1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWMyYWNcdWI4NmZcdWM1ZDBcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzcwNFx1YzgyZlx1Yzc0NCBcdWIwN2NcdWM2Y2MgXHViMTIzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHVjNzA0XHVjODJmXHVjNzQ0IFx1YjA3Y1x1YzZjY1x1YjEyM1x1YjI5NCBcdWFjODNcdWM3NzQgXHViYWE5XHVkNDVjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWFkZmNcdWM3NTggXHVkNTA0XHViODVjXHVjMTM4XHVjMTFjIFx1YjUxNFx1Yzc5MFx1Yzc3OFx1YjRlNFx1Yzc0MCBcdWI5ZTRcdWM2YjAgXHViY2Y1XHVjN2ExXHVkNTU4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWIyZjlcdWMyZTBcdWM3NDAgXHVjNmI0IFx1YjA5OFx1YzA1OFx1YWM4Y1x1YjNjNCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzgxY1x1ZDU1Y1x1YjRlNFx1Yzc0NCBcdWM5YzBcdWNmMWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1YzViNFx1YjVhNCBcdWMyYWNcdWI4NmZcdWI0ZTRcdWM3NDAgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzViNFx1YjVhNCBcdWMyYWNcdWI4NmZcdWI0ZTRcdWM3NDAgXHViMmU0XHViOTc4IFx1YmQ4MFx1ZDQ4OFx1YzVkMCBcdWM3NThcdWQ1NzQgXHVjNzc0XHViYmY4IFx1YzBhY1x1YzZhOVx1YjQxOFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjOTExXHVjNzc0XHViNzdjXHVjMTFjIFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWM3MDRcdWM4MmZcdWM3NDQgXHViMDdjXHVjNmI4IFx1YzIxOCBcdWM1YzZcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1Y2U2OVx1Yzc1OCBcdWMyMThcdWQzYzlcdWQ1NWMgXHViY2MwXHVhY2ZjIFx1YzIxOFx1YzljMVx1ZDU1YyBcdWJjYzBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1ZDYxNVx1YzgxYyBcdWJhNTRcdWJhYThcdWI5YWMgXHViYzg0XHVjMmE0XHVhYzAwIFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhZGY4XHViNGU0XHVjNzU4IFx1YjMwMFx1YzVlZFx1ZDNlZFx1Yzc0NCBcdWFjMTlcdWFjOGMgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViN2VjXHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExY1x1YjI5NCBpIFx1YmM4OFx1YzlmOCBcdWQ1ODlcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgaSBcdWJjODhcdWM5ZjggXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YWMxOVx1YzczY1x1YmE3NCBcdWI0MThcdWJhNzAsIFx1YmQ4MFx1ZDQ4OFx1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHVjNzc0XHViYmY4IFx1YzBhY1x1YzZhOVx1YjQxOFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViZDgwXHVkNDg4XHVjNzU4IFx1YzIxOFx1YzY0MCBcdWMwYzhcdWI4NWMgXHVjZDk0XHVhYzAwXHVkNTVjIFx1YzcwNFx1YzgyZlx1Yzc1OCBcdWMyMThcdWI5N2MgXHVkM2VjXHVkNTY4XHVkNTc0XHVjMTFjIFx1YzEzOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjYxMFx1ZDU1YyBcdWJlNDRcdWMyYjdcdWQ1NThcdWFjOGMsIFx1YzgwNFx1YzZkMCBcdWFjZjVcdWFlMDlcdWFlMzBcdWFjMDAgXHVhYzAxIFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM3NTggXHViMDVkXHVjNWQwIFx1YzVmMFx1YWNiMFx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWNmY1x1YzVmNFx1Yzc0NCBcdWI5YzlcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YzViNFx1YjVhNCBcdWQ1ODlcdWM3NzRcdWIwOTggXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YzgwNFx1Y2NiNCBcdWNlNjkgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzU4IFx1YmU0NFx1YzcyOFx1Yzc3NCBBXC9CIFx1Y2QwOFx1YWNmY1x1YWMwMCBcdWI0MThcdWJhNzQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gKEFcdWM2NDAgQlx1YjI5NCBcdWFjMDEgXHVjZTY5XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQpPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVkNTU4XHViMDk4XHVjNzU4IFx1Y2U2OVx1Yzc0MCBOXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YWM4M1x1Yzc3NFx1YjJlNC4gJiMzOTsuJiMzOTtcdWM3NDAgXHVjNWY0XHViODI0XHVjNzg4XHViMjk0KFx1YzU0NFx1YzljMSBcdWMwYWNcdWM2YTlcdWI0MThcdWM5YzAgXHVjNTRhXHVjNzQwKVx1YzJhY1x1Yjg2Zlx1Yzc3NFx1YWNlMCwgJiMzOTtcLyYjMzk7XHVjNzQwIFx1YzBhY1x1YzZhOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YzJhY1x1Yjg2ZiwgXHVhZGY4XHViOWFjXHVhY2UwICYjMzk7QyYjMzk7XHViMjk0IFx1Yzc3NFx1YmJmOCBcdWIyZTRcdWI5NzggXHViZDgwXHVkNDg4XHVjNWQwIFx1Yzc1OFx1ZDU3NCBcdWMwYWNcdWM2YTlcdWI0MThcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzJhY1x1Yjg2Zlx1Yzc3NFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1Y2U2OVx1Yzc0NCBcdWMwZGRcdWFjMDFcdWQ1NzRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkNDXC8uLlxyXG4uXC8uXC9cL1xyXG4uLkMuQ1xyXG5cLy5DLi5cclxuXC8uXC9DXC9cclxuPFwvcHJlPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkIFx1ZDU1YyBcdWQ1ODlcdWM3NzRcdWIwOTggXHVjNWY0XHVjNWQwIDNcLzEwXHVjNzc0XHVjMGMxXHVjNzU4IFx1YmQ4MFx1ZDQ4OFx1Yzc3NCBcdWM3ODhcdWM1YjRcdWMxMWNcdWIyOTQgXHVjNTQ4IFx1YjQxY1x1YjJlNFx1YWNlMCBcdWQ1NThcdWJhNzQsIFx1Yzc3NCBcdWNlNjkgXHVjNzA0XHVjNWQwIFx1Y2Q1Y1x1YjMwMFx1ZDU1Y1x1YzczY1x1Yjg1YyBcdWNkOTRcdWFjMDBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWM4MmZcdWM3NTggXHVhYzFjXHVjMjE4XHViMjk0IDdcdWFjMWNcdWFjMDAgXHViNDFjXHViMmU0LiBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzMwXHVjZTU4XHViMjk0IFx1YzU0NFx1Yjc5OFx1YzVkMCBcdWM3ODhcdWM3M2NcdWJhNzAgJiMzOTtXJiMzOTtcdWIyOTQgXHVjNWY0XHViODI0XHVjNzg4XHViMjk0IFx1YzJhY1x1Yjg2Zlx1YzVkMCBcdWNkOTRcdWFjMDBcdWI0MWMgXHVjNzA0XHVjODJmXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHByZT5cclxuQ0NcL1cuXHJcbldcL1dcL1wvXHJcblcuQy5DXHJcblwvLkNXV1xyXG5cL1dcL0NcL1xyXG48XC9wcmU+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWM5MDRcdWM3NDAgXHVjMTM4XHVhYzAwXHVjOWMwIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0OiBcdWNlNjlcdWM3NTggXHVkMDZjXHVhZTMwJm5ic3A7TiAoMSAmbGU7IE4gJmxlOyA0MCksIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIFx1YmU0NFx1YzcyOFx1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NThcdWIyOTQgQVx1YzY0MCBCKDEgJmxlOyBCICZsZTsgMTAwMCwgMCAmbGU7IEEgJmxlOyBCKS4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yzc0MCBcdWMyYWNcdWI4NmZcdWM3NTggXHVjMGMxXHVkMGRjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCBcdWFjMDEgXHVjOTA0XHViOWM4XHViMmU0IE5cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YmIzOFx1Yzc5MFx1YjI5NCAmIzM5Oy4mIzM5OywmIzM5O1wvJiMzOTsgXHViNjEwXHViMjk0ICYjMzk7QyYjMzk7XHVjNzc0XHViYTcwIFx1Yzc3NFx1YjI5NCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjMTI0XHViYTg1XHVkNTVjIFx1YjMwMFx1Yjg1Y1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjOWMwXHViOWM5IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgMCBcdWMxMzggXHVhYzFjXHViODVjJm5ic3A7XHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzA0XHVjODJmIFx1YmMzMFx1Y2U1OFx1YWMwMCBcdWM3ODhcdWIyZTRcdWJhNzQgXHVjZTY5IFx1YzcwNFx1YzVkMCBcdWNkOTRcdWFjMDBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWM3MDRcdWM4MmZcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJjMzBcdWNlNThcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0ICZxdW90O2ltcG9zc2libGUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHVjODFjIFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQyMTgiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDaGlwcyBDaGFsbGVuZ2UiLCJkZXNjcmlwdGlvbiI6IjxwPkEgcHJvbWluZW50IG1pY3JvcHJvY2Vzc29yIGNvbXBhbnkgaGFzIGVubGlzdGVkIHlvdXIgaGVscCB0byBsYXkgb3V0IHNvbWUgaW50ZXJjaGFuZ2VhYmxlIGNvbXBvbmVudHMgKHdpZGdldHMpIG9uIHNvbWUgb2YgdGhlaXIgY29tcHV0ZXIgY2hpcHMuIEVhY2ggY2hpcCZyc3F1bztzIGRlc2lnbiBpcyBhbiBOJnRpbWVzO04gc3F1YXJlIG9mIHNsb3RzLiBPbmUgc2xvdCBjYW4gaG9sZCBhIHNpbmdsZSBjb21wb25lbnQsIGFuZCB5b3UgYXJlIHRvIHRyeSB0byBcdWZiMDF0IGluIGFzIG1hbnkgd2lkZ2V0cyBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+TW9kZXJuIHByb2Nlc3NvciBkZXNpZ25zIGFyZSBjb21wbGV4LCBvZiBjb3Vyc2UuIFlvdSB1bmZvcnR1bmF0ZWx5IGhhdmUgc2V2ZXJhbCByZXN0cmljdGlvbnM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U29tZSBvZiB0aGUgc2xvdHMgYXJlIGRpc2FibGVkLjxcL2xpPlxyXG5cdDxsaT5Tb21lIG9mIHRoZSBzbG90cyBhcmUgYWxyZWFkeSBvY2N1cGllZCBieSBvdGhlciBjb21wb25lbnRzIGFuZCBjYW5ub3QgYmUgdXNlZCBmb3Igd2lkZ2V0cy48XC9saT5cclxuXHQ8bGk+VGhlcmUgYXJlIHNpYmxpbmcgbWVtb3J5IGJ1c2VzIGNvbm5lY3RlZCB0byB0aGUgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgZWRnZXMgb2YgdGhlIGNoaXAgYW5kIHRoZWlyIGJhbmR3aWR0aCBsb2FkcyBuZWVkIHRvIG1hdGNoLiBBcyBzdWNoLCB0aGVyZSBtdXN0IGJlIGV4YWN0bHkgYXMgbWFueSBjb21wb25lbnRzIGluIHRoZSBcdWZiMDFyc3Qgcm93IGFzIGluIHRoZSBcdWZiMDFyc3QgY29sdW1uLCBleGFjdGx5IGFzIG1hbnkgaW4gdGhlIHNlY29uZCByb3cgYXMgaW4gdGhlIHNlY29uZCBjb2x1bW4sIGFuZCBzbyBvbi4gQ29tcG9uZW50IGNvdW50cyBpbmNsdWRlIGJvdGggdGhlIGNvbXBvbmVudHMgYWxyZWFkeSBzcGVjaVx1ZmIwMWVkIG9uIHRoZSBjaGlwIGFuZCB0aGUgYWRkZWQgd2lkZ2V0cy48XC9saT5cclxuXHQ8bGk+U2ltaWxhcmx5LCB0aGUgcG93ZXIgc3VwcGx5IGlzIGNvbm5lY3RlZCBhdCB0aGUgZW5kIG9mIGVhY2ggcm93IGFuZCBjb2x1bW4uIFRvIGF2b2lkIGhvdCBzcG90cywgYW55IGdpdmVuIHJvdyBvciBjb2x1bW4gbXVzdCBoYXZlIG5vIG1vcmUgdGhhbiBBXC9CIG9mIHRoZSB0b3RhbCBjb21wb25lbnRzIG9uIHRoZSBjaGlwIGZvciBhIGdpdmVuIEEgYW5kIEIuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+QSBzcGVjaVx1ZmIwMWNhdGlvbiBmb3IgYSBjaGlwIGlzIE4gbGluZXMgb2YgTiBjaGFyYWN0ZXJzLCB3aGVyZSAmbHNxdW87LiZyc3F1bzsgaW5kaWNhdGVzIGFuIG9wZW4gc2xvdCwgJmxzcXVvO1wvJnJzcXVvOyBpbmRpY2F0ZXMgYSBkaXNhYmxlZCBzbG90LCBhbmQgJmxzcXVvO0MmcnNxdW87IGluZGljYXRlcyBhIHNsb3QgYWxyZWFkeSBvY2N1cGllZCBieSBhIGNvbXBvbmVudC4gRm9yIGV4YW1wbGU6PFwvcD5cclxuXHJcbjxwcmU+XHJcbkNDXC8uLlxyXG4uXC8uXC9cL1xyXG4uLkMuQ1xyXG5cLy5DLi5cclxuXC8uXC9DXC88XC9wcmU+XHJcblxyXG48cD5JZiBubyBtb3JlIHRoYW4gM1wvMTAgb2YgdGhlIGNvbXBvbmVudHMgbWF5IGJlIGluIGFueSBvbmUgcm93IG9yIGNvbHVtbiwgdGhlIG1heGltdW0gbnVtYmVyIG9mIHdpZGdldHMgdGhhdCBjYW4gYmUgYWRkZWQgdG8gdGhpcyA1JnRpbWVzOzUgY2hpcCBpcyA3LiBBIHBvc3NpYmxlIGFycmFuZ2VtZW50IGlzIGJlbG93LCB3aGVyZSAmbHNxdW87VyZyc3F1bzsgaW5kaWNhdGVzIGEgd2lkZ2V0IGFkZGVkIGluIGFuIG9wZW4gc2xvdC48XC9wPlxyXG5cclxuPHByZT5cclxuQ0NcL1cuXHJcbldcL1dcL1wvXHJcblcuQy5DXHJcblwvLkNXV1xyXG5cL1dcL0NcLzxcL3ByZT5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2Ygc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIGNhc2Ugc3RhcnRzIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdGhyZWUgaW50ZWdlcnM6IFRoZSBzaXplIG9mIHRoZSBjaGlwIE4gKDEgJmxlOyBOICZsZTsgNDApLCBhbmQgQSBhbmQgQiAoMSAmbGU7IEIgJmxlOyAxMDAwLCAwICZsZTsgQSAmbGU7IEIpIGFzIGRlc2NyaWJlZCBhYm92ZS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgTiBjaGFyYWN0ZXJzIGRlc2NyaWJpbmcgdGhlIHNsb3RzLCBvbmUgb2YgJmxzcXVvOy4mcnNxdW87LCAmbHNxdW87XC8mcnNxdW87IG9yICZsc3F1bztDJnJzcXVvOywgYXMgZGVzY3JpYmVkIGFib3ZlLjxcL3A+XHJcblxyXG48cD5UaGUgbGFzdCB0ZXN0IGNhc2UgaXMgZm9sbG93ZWQgYnkgYSBsaW5lIGNvbnRhaW5pbmcgdGhyZWUgemVyb3MuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBkaXNwbGF5IGEgc2luZ2xlIGxpbmUgYmVnaW5uaW5nIHdpdGggdGhlIGNhc2UgbnVtYmVyLiBJZiB0aGVyZSBpcyBhIHNvbHV0aW9uLCBkaXNwbGF5IHRoZSBtYXhpbXVtIG51bWJlciBvZiB3aWRnZXRzIHRoYXQgY2FuIGJlIGFkZGVkIHRvIHRoZSBjaGlwLiBEaXNwbGF5ICZsZHF1bztpbXBvc3NpYmxlJnJkcXVvOyBpZiB0aGVyZSBpcyBubyBzb2x1dGlvbi48XC9wPlxyXG5cclxuPHA+Rm9sbG93IHRoZSBmb3JtYXQgb2YgdGhlIHNhbXBsZSBvdXRwdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ICPC > World Finals > 2011 World Finals D번

  • 문제를 번역한 사람: august14
  • 잘못된 조건을 찾은 사람: koosaga