시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 33 12 5 22.727%

문제

유명한 마이크로프로세서 회사 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"을 출력하면 된다.

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

예제 입력

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

예제 출력

Case 1: 0
Case 2: 1
Case 3: impossible
Case 4: 7
Case 5: impossible

힌트

출처

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