시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 47 19 8 27.586%

문제

유명한 마이크로프로세서 회사 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+XHVjNjA4XHVjODFjIFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWI1MzBcdWI3N2NcdWMxMWMgXHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MjE4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2hpcHMgQ2hhbGxlbmdlIiwiZGVzY3JpcHRpb24iOiI8cD5BIHByb21pbmVudCBtaWNyb3Byb2Nlc3NvciBjb21wYW55IGhhcyBlbmxpc3RlZCB5b3VyIGhlbHAgdG8gbGF5IG91dCBzb21lIGludGVyY2hhbmdlYWJsZSBjb21wb25lbnRzICh3aWRnZXRzKSBvbiBzb21lIG9mIHRoZWlyIGNvbXB1dGVyIGNoaXBzLiBFYWNoIGNoaXAmcnNxdW87cyBkZXNpZ24gaXMgYW4gTiZ0aW1lcztOIHNxdWFyZSBvZiBzbG90cy4gT25lIHNsb3QgY2FuIGhvbGQgYSBzaW5nbGUgY29tcG9uZW50LCBhbmQgeW91IGFyZSB0byB0cnkgdG8gXHVmYjAxdCBpbiBhcyBtYW55IHdpZGdldHMgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPk1vZGVybiBwcm9jZXNzb3IgZGVzaWducyBhcmUgY29tcGxleCwgb2YgY291cnNlLiBZb3UgdW5mb3J0dW5hdGVseSBoYXZlIHNldmVyYWwgcmVzdHJpY3Rpb25zOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlNvbWUgb2YgdGhlIHNsb3RzIGFyZSBkaXNhYmxlZC48XC9saT5cclxuXHQ8bGk+U29tZSBvZiB0aGUgc2xvdHMgYXJlIGFscmVhZHkgb2NjdXBpZWQgYnkgb3RoZXIgY29tcG9uZW50cyBhbmQgY2Fubm90IGJlIHVzZWQgZm9yIHdpZGdldHMuPFwvbGk+XHJcblx0PGxpPlRoZXJlIGFyZSBzaWJsaW5nIG1lbW9yeSBidXNlcyBjb25uZWN0ZWQgdG8gdGhlIGhvcml6b250YWwgYW5kIHZlcnRpY2FsIGVkZ2VzIG9mIHRoZSBjaGlwIGFuZCB0aGVpciBiYW5kd2lkdGggbG9hZHMgbmVlZCB0byBtYXRjaC4gQXMgc3VjaCwgdGhlcmUgbXVzdCBiZSBleGFjdGx5IGFzIG1hbnkgY29tcG9uZW50cyBpbiB0aGUgXHVmYjAxcnN0IHJvdyBhcyBpbiB0aGUgXHVmYjAxcnN0IGNvbHVtbiwgZXhhY3RseSBhcyBtYW55IGluIHRoZSBzZWNvbmQgcm93IGFzIGluIHRoZSBzZWNvbmQgY29sdW1uLCBhbmQgc28gb24uIENvbXBvbmVudCBjb3VudHMgaW5jbHVkZSBib3RoIHRoZSBjb21wb25lbnRzIGFscmVhZHkgc3BlY2lcdWZiMDFlZCBvbiB0aGUgY2hpcCBhbmQgdGhlIGFkZGVkIHdpZGdldHMuPFwvbGk+XHJcblx0PGxpPlNpbWlsYXJseSwgdGhlIHBvd2VyIHN1cHBseSBpcyBjb25uZWN0ZWQgYXQgdGhlIGVuZCBvZiBlYWNoIHJvdyBhbmQgY29sdW1uLiBUbyBhdm9pZCBob3Qgc3BvdHMsIGFueSBnaXZlbiByb3cgb3IgY29sdW1uIG11c3QgaGF2ZSBubyBtb3JlIHRoYW4gQVwvQiBvZiB0aGUgdG90YWwgY29tcG9uZW50cyBvbiB0aGUgY2hpcCBmb3IgYSBnaXZlbiBBIGFuZCBCLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkEgc3BlY2lcdWZiMDFjYXRpb24gZm9yIGEgY2hpcCBpcyBOIGxpbmVzIG9mIE4gY2hhcmFjdGVycywgd2hlcmUgJmxzcXVvOy4mcnNxdW87IGluZGljYXRlcyBhbiBvcGVuIHNsb3QsICZsc3F1bztcLyZyc3F1bzsgaW5kaWNhdGVzIGEgZGlzYWJsZWQgc2xvdCwgYW5kICZsc3F1bztDJnJzcXVvOyBpbmRpY2F0ZXMgYSBzbG90IGFscmVhZHkgb2NjdXBpZWQgYnkgYSBjb21wb25lbnQuIEZvciBleGFtcGxlOjxcL3A+XHJcblxyXG48cHJlPlxyXG5DQ1wvLi5cclxuLlwvLlwvXC9cclxuLi5DLkNcclxuXC8uQy4uXHJcblwvLlwvQ1wvPFwvcHJlPlxyXG5cclxuPHA+SWYgbm8gbW9yZSB0aGFuIDNcLzEwIG9mIHRoZSBjb21wb25lbnRzIG1heSBiZSBpbiBhbnkgb25lIHJvdyBvciBjb2x1bW4sIHRoZSBtYXhpbXVtIG51bWJlciBvZiB3aWRnZXRzIHRoYXQgY2FuIGJlIGFkZGVkIHRvIHRoaXMgNSZ0aW1lczs1IGNoaXAgaXMgNy4gQSBwb3NzaWJsZSBhcnJhbmdlbWVudCBpcyBiZWxvdywgd2hlcmUgJmxzcXVvO1cmcnNxdW87IGluZGljYXRlcyBhIHdpZGdldCBhZGRlZCBpbiBhbiBvcGVuIHNsb3QuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkNDXC9XLlxyXG5XXC9XXC9cL1xyXG5XLkMuQ1xyXG5cLy5DV1dcclxuXC9XXC9DXC88XC9wcmU+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIHNldmVyYWwgdGVzdCBjYXNlcy4gRWFjaCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIHRocmVlIGludGVnZXJzOiBUaGUgc2l6ZSBvZiB0aGUgY2hpcCBOICgxICZsZTsgTiAmbGU7IDQwKSwgYW5kIEEgYW5kIEIgKDEgJmxlOyBCICZsZTsgMTAwMCwgMCAmbGU7IEEgJmxlOyBCKSBhcyBkZXNjcmliZWQgYWJvdmUuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIE4gY2hhcmFjdGVycyBkZXNjcmliaW5nIHRoZSBzbG90cywgb25lIG9mICZsc3F1bzsuJnJzcXVvOywgJmxzcXVvO1wvJnJzcXVvOyBvciAmbHNxdW87QyZyc3F1bzssIGFzIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG5cclxuPHA+VGhlIGxhc3QgdGVzdCBjYXNlIGlzIGZvbGxvd2VkIGJ5IGEgbGluZSBjb250YWluaW5nIHRocmVlIHplcm9zLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgZGlzcGxheSBhIHNpbmdsZSBsaW5lIGJlZ2lubmluZyB3aXRoIHRoZSBjYXNlIG51bWJlci4gSWYgdGhlcmUgaXMgYSBzb2x1dGlvbiwgZGlzcGxheSB0aGUgbWF4aW11bSBudW1iZXIgb2Ygd2lkZ2V0cyB0aGF0IGNhbiBiZSBhZGRlZCB0byB0aGUgY2hpcC4gRGlzcGxheSAmbGRxdW87aW1wb3NzaWJsZSZyZHF1bzsgaWYgdGhlcmUgaXMgbm8gc29sdXRpb24uPFwvcD5cclxuXHJcbjxwPkZvbGxvdyB0aGUgZm9ybWF0IG9mIHRoZSBzYW1wbGUgb3V0cHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > World Finals > 2011 World Finals D번

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