Задача 102927

Тема:    [ Задачи на полный перебор ]

Сложность: 3+ Классы: Название задачи: Кроссворд .

Условие

Задан набор из N слов, из которых требуется составить связный кроссворд. Слова в кроссворде должны располагаться либо вертикально, либо горизонтально, причем каждое слово, записанное по вертикали, должно пересекаться с каждым словом, записанным по горизонтали. Слова, записанные в одном направлении, отделяются друг от друга как минимум одним пустым рядом. Каждое слово в кроссворде должно встречаться в точности столько раз, сколько раз оно присутствует в наборе.

Входные данные
Первая строка входного файла содержит целое число N – количество слов в наборе (1 ≤ N ≤ 9). В каждой из N последующих строк содержится по одному слову (некоторые из них могут повторяться). Слово представляет собой последовательность не более чем из 20 русских и/или английских букв.

Выходные данные
В выходной файл выведите один из возможных вариантов составления кроссворда, либо сообщение «NO SOLUTION», если кроссворд, удовлетворяющий условию задачи, составить невозможно.

Пример входного файла
СБОРЫ
СОН
ПОТОП
АНТОН

Пример выходного файла
П
СБОРЫ
О Т
АНТОН
П

Решение

Скачать архив тестов и решений

Источники и прецеденты использования

книга
предмет	информатика
Автор	Беров В., Лапунов А., Матюхин В., Пономарев А.
Название	Особенности национальных задач по информатике
Издательство	Триада-С
Год издания	2000
глава
Номер	2
Название	Перебор с возвратом
гЮДЮВЮ
Номер	7