Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
993. Веселые шахматы
Полный переборСокращение перебора с помощью идеи
Олимпиадные задачи на русском языке
| 03/07/2008 | Лето 2008 дорешивание ( 7H) |
| 16/07/2008 | Лето 2008 - 7 (H) |
Ограничения: время – 7s/14s, память – 8MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В журнале "Красный Глаз Программиста" опубликовали конкурсную программу. Нужно найти, сколькими способами можно расставить заданный набор шахматных фигур (или его часть) на заданные клетки, чтобы не возникло противоречий с известными данными о клетках, находящихся под боем, а также со следующими двумя правилами:
- Два короля не могут быть на двух соседних клетках.
- Король не должен быть под боем.
В прошлом номере журнала было опубликовано решение комсомольца, но, к сожалению, оно работало неверно по невыясненным причинам (саботаж?). Поэтому у читателей вновь появился шанс стать первым решившим эту задачу. И у Вас тоже, товарищ (в том числе стать дважды не решившим данную задачу).
Ввод
Первые 8 строк входного файла – шахматное поле 8x8, на котором:
- "?" – обозначает, что в этой клетке находится какая-то фигура. На поле может быть от 1 до 10 вопросов.
- "." – обозначает, что в этой клетке нет фигуры и неизвестно, сколько раз она находится под боем.
- шестнадцатеричная цифра 0..9,A..F – обозначает, сколько раз клетка находится под боем.
9 строка – набор шахматных фигур без пробелов. N – конь, B – слон, R – ладья, Q – ферзь, K – король. Пешек в наборе нет. Длина строки от 1 до 255 символов.
Вывод
В первой строке вывести количество возможных расстановок. Если такая расстановка только одна, то также вывести ее на последующих восьми строках. Если нет ни одной расстановки, вывести одно слово "IMPOSSIBLE" (без кавычек).
Пример ввода 1
........ ........ ........ ........ ..?10... ........ ........ ........ KQ
Пример вывода 1
1 ........ ........ ........ ........ ..K..... ........ ........ ........
Пример ввода 2
........ ........ ........ ........ ..?1.... ........ ........ ........ KQ
Пример вывода 2
2
Пример ввода 3
........ ........ ...1.... ........ ..?1.... ........ ........ ........ KQ
Пример вывода 3
IMPOSSIBLE
