eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Задача з мікропроцесором

Задача з мікропроцесором

Ліміт часу 30 секунд
Ліміт використання пам'яті 256 MiB

Відома компанія з виробництва мікропроцесорів попросила Вас розмістити декілька компонентів, які можуть взаємно замінюватись, (віджетів) на комп'ютерних чіпах. Кожен чіп складаєьтся з N×N квадратних слотів. Один слот може містити лише один компонент. Вам потрібно розмістити на чіпі якомога більшу кількість віджетів.

Конструкція сучасних процесорів досить складна. На жаль, у Вас є наступні обмеження:

  • Деякі слоти стали непридатними і не працюють.

  • Деякі слоти вже містять інші компоненти і не можуть використовуватись для віджетів.

  • До вертикальних та горизонтальних кінців чіпа пприкріплено шини пам'яті, тому повинна бути врахована їхня пропускна здатність. Саме тому у першому рядку і у першому стовбці повинна знаходитись однакова кількість компонен, число компонент у другому рядку і другому стовбці також повинно співпадати і так далі. При підрахунку компонет слід враховувати як ті, які знаходились на чіпі спочатку, так і віджети, які було додано у пусті слоти.

  • До кінців кожного рядка і стовбця чіпа підключено джерело живлення. Для уникнення перегріву кожен рядок і стовбець чіпа повинен містити не більше A/B компонент для заданих значень A та B.

Чіп задається N рядками по N символів кожен, де '.' вказує на пустои слот, '/' вказує на пошкоджений слот, а 'C' вказує на те що слот вже зайнято компонентою. Наприклад:

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

Якщо не більше ніж 3/10 компонент може знаходитсь у кожному рядку і кожному стовбці, то найбільша кількість віджетів яка може бути додана до 5×5 чіпа, становить 7. Можливе розміщення подано нижче, де через 'W' позначено віджет, який додано у відкритий слот.

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

Вхідні дані

Вхідні дані складаються з декількох тестів. Кожен тест починається со рядком, який містить три цілих числа: розмір чіпу N (1N10), і значення A та B (1B1000, 0AB). Кожен з наступних N рядків містить N символів, які описують слоти: '.', '/' або 'C'.

Останній тест завершується рядком, що містить три нулі.

Вихідні дані

Для кожного тесту у окремому рядку виведіть його номер. Якщо розв'язок існує, то слід вивести максимальну кількість віджетів, які можна розмістити на чіпі. Вивести "impossible", якщо розв'язку не існує.

Приклад

Вхідні дані #1
2 1 1
/.
//
0 0 0
Вихідні дані #1
Case 1: 0
Джерело ICPC 2011 World Finals