Пол с колонной
Пол в зале — квадрат 2k × 2k клеток, и в одной клетке стоит колонна. Плитка бывает только одна — уголок из трёх клеток, то есть квадрат 2 × 2 без одной клетки; уголки можно поворачивать. Уложите плитку на весь пол, кроме колонны, без резки, без зазоров и без наложений.
Клеток на полу без колонны 4k − 1, и это число всегда делится на три — но значит ли это, что уложить можно при любом месте колонны?
Вход
Одна строка: k, r, c (1 ≤ k ≤ 8, 1 ≤ r, c ≤ 2k) — размер пола и строка и столбец колонны, клетки нумеруются с единицы.
Выход
2k строк по 2k целых чисел: на месте колонны 0, в остальных клетках — номер плитки, которая её покрывает. Номера — любые положительные числа; каждый номер должен стоять ровно в трёх клетках, образующих уголок. Если раскладок несколько, выведите любую.
Примеры
Пример 1
2 2 3
2 2 3 3 2 1 0 3 4 1 1 5 4 4 5 5
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Попробуйте разложить пол 4 × 4 руками для разных мест колонны. Укладка по строкам слева направо иногда заводит в угол, где уголок уже не помещается. Нужен способ, который не зависит от удачи.
2Подсказка 2
Разрежьте пол на четыре четверти 2k−1 × 2k−1. Колонна стоит в одной из них — для этой четверти задача та же, только вдвое меньше. А как сделать такими же три остальные четверти, в которых колонны нет?
3Идея
Положим один уголок в самый центр пола так, чтобы он занял по одной клетке в каждой из трёх четвертей без колонны. Тогда в каждой из четырёх четвертей ровно одна занятая клетка — колонна или кусок центрального уголка, — и каждая четверть становится той же задачей меньшего размера. Пол 2 × 2 с одной занятой клеткой — это ровно один уголок.
4Разбор
Рекурсивная функция получает квадрат (верхний левый угол и сторону) и занятую в нём клетку. Если сторона 1, делать нечего. Иначе находим четверть с занятой клеткой; для каждой из трёх других берём её клетку, прилегающую к центру большого квадрата, — это клетки (h − 1, h − 1), (h − 1, h), (h, h − 1), (h, h) относительно угла, где h — половина стороны, — и кладём на три из них один новый уголок. Они действительно образуют уголок: все четыре клетки лежат в центральном квадрате 2 × 2, и мы берём три. Затем вызываемся для каждой четверти с её занятой клеткой.
Заодно это доказательство: индукцией по k пол 2k × 2k с одной вырезанной клеткой укладывается уголками при любом её месте. Так это доказал Соломон Голомб в 1954 году, в статье, с которой началась теория полимино.
4+Решение
5Сложность
T(n) = 4T(n/4) + O(1), где n = 4k — число клеток: по основной теореме Θ(n), по одному уголку на вызов, а вызовов (n − 1)/3. Глубина рекурсии — k ≤ 8. Время уходит в основном на вывод 65 536 чисел.
6Типичные ошибки
- Жадная укладка по строкам. Кладёт первый подходящий уголок в первую свободную клетку и на полу 8 × 8 уже оставляет клетки, куда уголок не помещается (четвёртый тест).
- Центральный уголок не той стороной. Он должен накрывать три четверти без колонны; если по ошибке накрыть четверть с колонной, в ней окажутся две занятые клетки, а в другой — ни одной.
- Одна и та же «занятая клетка» для всех четвертей. Каждой четверти нужна своя: колонна для своей и свой кусок центрального уголка для остальных.