Олимпиадный тренинг

Задача . F. Упрощенный японский кроссворд


Задача

Темы: meet-in-the-middle битмаски дп хэши *2400

В этой задаче вам предстоит написать программу, решающую упрощенный японский кроссворд для полей не более 5 × 20.

Упрощенный японский кроссворд — это головоломка, в которой надо построить такое поле (каждая клетка либо белая, либо черная), которое соответствует заданной информации для строк и столбцов. Для каждой строки и каждого столбца задано количество блоков из черных клеток. Ваша задача — построить такое поле, для которого все эти количества имеют место быть.

Например, если размеры поля n = 3, m = 5, а количества блоков для строк это [2, 3, 2], а для столбцов — [1, 0, 1, 2, 1], то решение может выглядеть так:

Гарантируется, что для каждого теста, на котором будет запущена ваша программа, хотя бы одно решение головоломки существует.

Входные данные

В первой строке входных данных записаны два целых числа n, m (1 ≤ n ≤ 5, 1 ≤ m ≤ 20) — количество строк и столбцов соответственно.

Вторая строка содержит n целых чисел a1, a2, ..., an, где ai — количество черных блоков в i-й строке искомого поля.

Аналогично, третья строка содержит m целых чисел b1, b2, ..., bm, где bi — количество черных блоков в i-м столбце искомого поля.

Гарантируется, что хотя бы одно решение головоломки существует.

Выходные данные

Выведите любое из возможных решений. Ваш вывод должен содержать n строк по m символов в каждой из них. Белую ячейку следует обозначать символом «.», а черную — символом «*».


Примеры
№Входные данныеВыходные данные
1 3 5
2 3 2
1 0 1 2 1 
*.**.
*.*.*
*..**
2 3 3
2 1 2
2 1 2 
*.*
.*.
*.*
3 3 3
1 0 1
2 2 2 
***
...
***

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет