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