시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 43 16 7 25.926%

문제

유명한 마이크로프로세서 회사 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+XHJcblx0PGxpPlx1YjYxMFx1ZDU1YyBcdWJlNDRcdWMyYjdcdWQ1NThcdWFjOGMsIFx1YzgwNFx1YzZkMCBcdWFjZjVcdWFlMDlcdWFlMzBcdWFjMDAgXHVhYzAxIFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM3NTggXHViMDVkXHVjNWQwIFx1YzVmMFx1YWNiMFx1YjQyMCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YWNmY1x1YzVmNFx1Yzc0NCBcdWI5YzlcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YzViNFx1YjVhNCBcdWQ1ODlcdWM3NzRcdWIwOTggXHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4XHVjNjQwIFx1YzgwNFx1Y2NiNCBcdWNlNjkgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJkODBcdWQ0ODhcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzU4IFx1YmU0NFx1YzcyOFx1Yzc3NCBBXC9CIFx1Y2QwOFx1YWNmY1x1YWMwMCBcdWI0MThcdWJhNzQgXHVjNTQ4XHViNDFjXHViMmU0LiAoQVx1YzY0MCBCXHViMjk0IFx1YWMwMSBcdWNlNjlcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWQ1NThcdWIwOThcdWM3NTggXHVjZTY5XHVjNzQwIE5cdWFjMWNcdWM3NTggXHViYjM4XHVjNzkwXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzggXHVhYzgzXHVjNzc0XHViMmU0LiAmIzM5Oy4mIzM5O1x1Yzc0MCBcdWM1ZjRcdWI4MjRcdWM3ODhcdWIyOTQoXHVjNTQ0XHVjOWMxIFx1YzBhY1x1YzZhOVx1YjQxOFx1YzljMCBcdWM1NGFcdWM3NDApXHVjMmFjXHViODZmXHVjNzc0XHVhY2UwLCAmIzM5O1wvJiMzOTtcdWM3NDAgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVjMmFjXHViODZmLCBcdWFkZjhcdWI5YWNcdWFjZTAgJiMzOTtDJiMzOTtcdWIyOTQgXHVjNzc0XHViYmY4IFx1YjJlNFx1Yjk3OCBcdWJkODBcdWQ0ODhcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1YzBhY1x1YzZhOVx1YjQxOFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjMmFjXHViODZmXHVjNzc0XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjZTY5XHVjNzQ0IFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHByZT5cclxuQ0NcLy4uXHJcbi5cLy5cL1wvXHJcbi4uQy5DXHJcblwvLkMuLlxyXG5cLy5cL0NcL1xyXG48XC9wcmU+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QgXHVkNTVjIFx1ZDU4OVx1Yzc3NFx1YjA5OCBcdWM1ZjRcdWM1ZDAgM1wvMTBcdWM3NzRcdWMwYzFcdWM3NTggXHViZDgwXHVkNDg4XHVjNzc0IFx1Yzc4OFx1YzViNFx1YzExY1x1YjI5NCBcdWM1NDhcdWI0MWNcdWIyZTRcdWFjZTAgXHVkNTU4XHViYTc0LCBcdWM3NzQgXHVjZTY5IFx1YzcwNFx1YzVkMCBcdWNkNWNcdWIzMDBcdWQ1NWNcdWM3M2NcdWI4NWMgXHVjZDk0XHVhYzAwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjODJmXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCA3XHVhYzFjXHVhYzAwIFx1YjQxY1x1YjJlNC4gXHVhYzAwXHViMmE1XHVkNTVjIFx1YmMzMFx1Y2U1OFx1YjI5NCBcdWM1NDRcdWI3OThcdWM1ZDAgXHVjNzg4XHVjNzNjXHViYTcwICYjMzk7VyYjMzk7XHViMjk0IFx1YzVmNFx1YjgyNFx1Yzc4OFx1YjI5NCBcdWMyYWNcdWI4NmZcdWM1ZDAgXHVjZDk0XHVhYzAwXHViNDFjIFx1YzcwNFx1YzgyZlx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkNDXC9XLlxyXG5XXC9XXC9cL1xyXG5XLkMuQ1xyXG5cLy5DV1dcclxuXC9XXC9DXC9cclxuPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVjOTA0XHVjNzQwIFx1YzEzOFx1YWMwMFx1YzljMCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNDogXHVjZTY5XHVjNzU4IFx1ZDA2Y1x1YWUzMCZuYnNwO04gKDEgJmxlOyBOICZsZTsgNDApLCBcdWFkZjhcdWI5YWNcdWFjZTAgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWJlNDRcdWM3MjhcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHViMjk0IEFcdWM2NDAgQigxICZsZTsgQiAmbGU7IDEwMDAsIDAgJmxlOyBBICZsZTsgQikuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDAgXHVjMmFjXHViODZmXHVjNzU4IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAgXHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCBOXHVhYzFjXHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWJiMzhcdWM3OTBcdWIyOTQgJiMzOTsuJiMzOTssJiMzOTtcLyYjMzk7IFx1YjYxMFx1YjI5NCAmIzM5O0MmIzM5O1x1Yzc3NFx1YmE3MCBcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzEyNFx1YmE4NVx1ZDU1YyBcdWIzMDBcdWI4NWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1YzljMFx1YjljOSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IDAgXHVjMTM4IFx1YWMxY1x1Yjg1YyZuYnNwO1x1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWMwMSBcdWM5MDRcdWM3NDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVhYzAwXHViMmE1XHVkNTVjIFx1YzcwNFx1YzgyZiBcdWJjMzBcdWNlNThcdWFjMDAgXHVjNzg4XHViMmU0XHViYTc0IFx1Y2U2OSBcdWM3MDRcdWM1ZDAgXHVjZDk0XHVhYzAwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjNzA0XHVjODJmXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFjMDBcdWIyYTVcdWQ1NWMgXHViYzMwXHVjZTU4XHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCAmcXVvdDtpbXBvc3NpYmxlJnF1b3Q7XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjVcdWM3NDQgXHViNTMwXHViNzdjXHVjMTFjIFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDIxOCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNoaXBzIENoYWxsZW5nZSIsImRlc2NyaXB0aW9uIjoiPHA+QSBwcm9taW5lbnQgbWljcm9wcm9jZXNzb3IgY29tcGFueSBoYXMgZW5saXN0ZWQgeW91ciBoZWxwIHRvIGxheSBvdXQgc29tZSBpbnRlcmNoYW5nZWFibGUgY29tcG9uZW50cyAod2lkZ2V0cykgb24gc29tZSBvZiB0aGVpciBjb21wdXRlciBjaGlwcy4gRWFjaCBjaGlwJnJzcXVvO3MgZGVzaWduIGlzIGFuIE4mdGltZXM7TiBzcXVhcmUgb2Ygc2xvdHMuIE9uZSBzbG90IGNhbiBob2xkIGEgc2luZ2xlIGNvbXBvbmVudCwgYW5kIHlvdSBhcmUgdG8gdHJ5IHRvIFx1ZmIwMXQgaW4gYXMgbWFueSB3aWRnZXRzIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5Nb2Rlcm4gcHJvY2Vzc29yIGRlc2lnbnMgYXJlIGNvbXBsZXgsIG9mIGNvdXJzZS4gWW91IHVuZm9ydHVuYXRlbHkgaGF2ZSBzZXZlcmFsIHJlc3RyaWN0aW9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Tb21lIG9mIHRoZSBzbG90cyBhcmUgZGlzYWJsZWQuPFwvbGk+XHJcblx0PGxpPlNvbWUgb2YgdGhlIHNsb3RzIGFyZSBhbHJlYWR5IG9jY3VwaWVkIGJ5IG90aGVyIGNvbXBvbmVudHMgYW5kIGNhbm5vdCBiZSB1c2VkIGZvciB3aWRnZXRzLjxcL2xpPlxyXG5cdDxsaT5UaGVyZSBhcmUgc2libGluZyBtZW1vcnkgYnVzZXMgY29ubmVjdGVkIHRvIHRoZSBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBlZGdlcyBvZiB0aGUgY2hpcCBhbmQgdGhlaXIgYmFuZHdpZHRoIGxvYWRzIG5lZWQgdG8gbWF0Y2guIEFzIHN1Y2gsIHRoZXJlIG11c3QgYmUgZXhhY3RseSBhcyBtYW55IGNvbXBvbmVudHMgaW4gdGhlIFx1ZmIwMXJzdCByb3cgYXMgaW4gdGhlIFx1ZmIwMXJzdCBjb2x1bW4sIGV4YWN0bHkgYXMgbWFueSBpbiB0aGUgc2Vjb25kIHJvdyBhcyBpbiB0aGUgc2Vjb25kIGNvbHVtbiwgYW5kIHNvIG9uLiBDb21wb25lbnQgY291bnRzIGluY2x1ZGUgYm90aCB0aGUgY29tcG9uZW50cyBhbHJlYWR5IHNwZWNpXHVmYjAxZWQgb24gdGhlIGNoaXAgYW5kIHRoZSBhZGRlZCB3aWRnZXRzLjxcL2xpPlxyXG5cdDxsaT5TaW1pbGFybHksIHRoZSBwb3dlciBzdXBwbHkgaXMgY29ubmVjdGVkIGF0IHRoZSBlbmQgb2YgZWFjaCByb3cgYW5kIGNvbHVtbi4gVG8gYXZvaWQgaG90IHNwb3RzLCBhbnkgZ2l2ZW4gcm93IG9yIGNvbHVtbiBtdXN0IGhhdmUgbm8gbW9yZSB0aGFuIEFcL0Igb2YgdGhlIHRvdGFsIGNvbXBvbmVudHMgb24gdGhlIGNoaXAgZm9yIGEgZ2l2ZW4gQSBhbmQgQi48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BIHNwZWNpXHVmYjAxY2F0aW9uIGZvciBhIGNoaXAgaXMgTiBsaW5lcyBvZiBOIGNoYXJhY3RlcnMsIHdoZXJlICZsc3F1bzsuJnJzcXVvOyBpbmRpY2F0ZXMgYW4gb3BlbiBzbG90LCAmbHNxdW87XC8mcnNxdW87IGluZGljYXRlcyBhIGRpc2FibGVkIHNsb3QsIGFuZCAmbHNxdW87QyZyc3F1bzsgaW5kaWNhdGVzIGEgc2xvdCBhbHJlYWR5IG9jY3VwaWVkIGJ5IGEgY29tcG9uZW50LiBGb3IgZXhhbXBsZTo8XC9wPlxyXG5cclxuPHByZT5cclxuQ0NcLy4uXHJcbi5cLy5cL1wvXHJcbi4uQy5DXHJcblwvLkMuLlxyXG5cLy5cL0NcLzxcL3ByZT5cclxuXHJcbjxwPklmIG5vIG1vcmUgdGhhbiAzXC8xMCBvZiB0aGUgY29tcG9uZW50cyBtYXkgYmUgaW4gYW55IG9uZSByb3cgb3IgY29sdW1uLCB0aGUgbWF4aW11bSBudW1iZXIgb2Ygd2lkZ2V0cyB0aGF0IGNhbiBiZSBhZGRlZCB0byB0aGlzIDUmdGltZXM7NSBjaGlwIGlzIDcuIEEgcG9zc2libGUgYXJyYW5nZW1lbnQgaXMgYmVsb3csIHdoZXJlICZsc3F1bztXJnJzcXVvOyBpbmRpY2F0ZXMgYSB3aWRnZXQgYWRkZWQgaW4gYW4gb3BlbiBzbG90LjxcL3A+XHJcblxyXG48cHJlPlxyXG5DQ1wvVy5cclxuV1wvV1wvXC9cclxuVy5DLkNcclxuXC8uQ1dXXHJcblwvV1wvQ1wvPFwvcHJlPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggY2FzZSBzdGFydHMgd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aHJlZSBpbnRlZ2VyczogVGhlIHNpemUgb2YgdGhlIGNoaXAgTiAoMSAmbGU7IE4gJmxlOyA0MCksIGFuZCBBIGFuZCBCICgxICZsZTsgQiAmbGU7IDEwMDAsIDAgJmxlOyBBICZsZTsgQikgYXMgZGVzY3JpYmVkIGFib3ZlLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBOIGNoYXJhY3RlcnMgZGVzY3JpYmluZyB0aGUgc2xvdHMsIG9uZSBvZiAmbHNxdW87LiZyc3F1bzssICZsc3F1bztcLyZyc3F1bzsgb3IgJmxzcXVvO0MmcnNxdW87LCBhcyBkZXNjcmliZWQgYWJvdmUuPFwvcD5cclxuXHJcbjxwPlRoZSBsYXN0IHRlc3QgY2FzZSBpcyBmb2xsb3dlZCBieSBhIGxpbmUgY29udGFpbmluZyB0aHJlZSB6ZXJvcy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIGRpc3BsYXkgYSBzaW5nbGUgbGluZSBiZWdpbm5pbmcgd2l0aCB0aGUgY2FzZSBudW1iZXIuIElmIHRoZXJlIGlzIGEgc29sdXRpb24sIGRpc3BsYXkgdGhlIG1heGltdW0gbnVtYmVyIG9mIHdpZGdldHMgdGhhdCBjYW4gYmUgYWRkZWQgdG8gdGhlIGNoaXAuIERpc3BsYXkgJmxkcXVvO2ltcG9zc2libGUmcmRxdW87IGlmIHRoZXJlIGlzIG5vIHNvbHV0aW9uLjxcL3A+XHJcblxyXG48cD5Gb2xsb3cgdGhlIGZvcm1hdCBvZiB0aGUgc2FtcGxlIG91dHB1dC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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