시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 128 MB | 37 | 18 | 10 | 62.500% |
유명한 마이크로프로세서 회사 letnI는 컴퓨터용 칩 위에 몇 개의 교체 가능한 부품(위젯)을 배치하는 일을 위해 당신의 도움을 필요로 한다. 각 칩은 NxN개의 정사각형 슬롯으로 이루어져 있다. 하나의 슬롯에는 하나의 위젯을 끼워 넣을 수 있으며, 최대한 많은 위젯을 끼워넣는 것이 목표이다.
최근의 프로세서 디자인들은 매우 복잡하기 때문에 당신은 운 나쁘게도 아래와 같은 제한들을 지켜야 한다.
하나의 칩은 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