Обратите внимание на необычное распределение баллов между F1 и F2. Эта задача значительно сложнее F1.
Для этой задачи доступен визуализатор. Его можно открыть по этой ссылке.
В этой задаче взломы отключены.
Это сложная версия задачи. Единственное отличие между двумя версиями состоит в ограничениях на $$$n$$$ и $$$k$$$.
У Верити есть таблица из $$$n$$$ строк и $$$n$$$ столбцов. Строки пронумерованы от $$$1$$$ до $$$n$$$ сверху вниз, а столбцы — от $$$1$$$ до $$$n$$$ слева направо. Клетка в строке $$$p$$$ и столбце $$$q$$$ обозначается как $$$(p, q)$$$.
Также у Верити есть робот Сиркьюити с предельно простой функциональностью. Верити должен запрограммировать Сиркьюити так, чтобы тот мог автоматически находить заданные клетки таблицы, но при этом эти клетки оставались скрытыми от чужих роботов.
В этой задаче есть две фазы.
Фаза 1: Верити (кодирование)
В этой фазе Верити пытается закодировать заданную клетку таблицы.
Верити получает целевую клетку $$$(r, c)$$$ и присваивает каждой клетке таблицы бинарное значение ($$$0$$$ или $$$1$$$). В клетках со значением $$$1$$$ будут установлены передающие сигнал маяки, а клетки со значением $$$0$$$ останутся пустыми.
Однако он считает, что при слишком малом числе маяков чужакам тоже будет легко найти целевую клетку. Поэтому он решил, что безопаснее всего использовать не более $$$k$$$ нулей.
Фаза 2: Сиркьюити (декодирование)
В этой фазе Сиркьюити пытается найти закодированную Верити клетку по созданной им таблице. Однако Сиркьюити не умеет эффективно обрабатывать большие таблицы.
В каждый момент времени Сиркьюити предполагает, что целевая клетка находится в подтаблице, ограниченной двумя клетками $$$(x_0, y_0)$$$ и $$$(x_1, y_1)$$$. Изначально $$$(x_0, y_0) = (1, 1)$$$ и $$$(x_1, y_1) = (n, n)$$$.
Сиркьюити находит закодированную клетку, последовательно принимая ровно $$$2n-2$$$ решений. Каждое решение принимается следующим образом.
Сиркьюити умеет определять число маяков в текущей подтаблице. Обозначим это число через $$$S$$$. Формально, $$$S$$$ — это число клеток со значением $$$1$$$ внутри подтаблицы, ограниченной клетками $$$(x_0, y_0)$$$ и $$$(x_1, y_1)$$$.
Основываясь исключительно на $$$S$$$, он выберет ровно одно из следующих действий:
Обратите внимание, что это решение не зависит от предыдущих решений и не может напрямую зависеть от значений $$$x_0, x_1, y_0$$$ или $$$y_1$$$. Сиркьюити не имеет памяти, и единственным параметром при принятии решения должно быть текущее значение $$$S$$$.
Если в какой-либо момент окажется, что $$$x_0 \gt x_1$$$ или $$$y_0 \gt y_1$$$, программа даст сбой и Сиркьюити не справится с задачей.
Верити закодировал в этой таблице некоторую клетку $$$(r, c)$$$. После всех $$$2n-2$$$ решений должны выполняться равенства $$$x_0 = x_1 = r$$$ и $$$y_0 = y_1 = c$$$.
Всего существует ровно 32 теста:
В единственной строке входных данных находится одно целое число $$$n$$$ ($$$n = 3$$$ или $$$10 \le n \le 40$$$).
Выведите $$$n^2$$$ бинарных таблиц.
$$$i$$$-я таблица — это таблица, которую Верити должен выбрать, если целевой клеткой является $$$(r, c)$$$, где $$$r = \lfloor \frac{i-1}{n} \rfloor + 1$$$ и $$$c = ((i-1) \bmod n) + 1$$$.
Иными словами, первая таблица соответствует цели $$$(1,1)$$$, вторая таблица соответствует цели $$$(1,2)$$$, $$$(n+1)$$$-я таблица соответствует цели $$$(2,1)$$$ и так далее.
Каждая таблица должна содержать не более $$$k=f(n)$$$ нулей.
Выведите последовательность из $$$n^2 + 1$$$ символов: $$$a_0, a_1, a_2, \ldots, a_{n^2}$$$. Каждый символ должен быть одним из U, D, L или R. $$$i$$$-й символ означает, что при $$$S=i$$$ Сиркьюити выполняет действие $$$a_i$$$.
3
111 111 001 011 111 100 110 110 110 010 111 111 111 111 111 010 111 101 111 111 110 111 011 111 011 010 111 DURLDULRUU
Рассмотрим в качестве примера третью таблицу. Целевая клетка — $$$(1,3)$$$.
Верити выбирает следующую таблицу:
110
110
110
Последовательность действий:
DURLDULRUU
Изначально Сиркьюити рассматривает подтаблицу, ограниченную клетками $$$(1,1)$$$ и $$$(3,3)$$$.
Он должен найти клетку $$$(1,3)$$$, поэтому примет $$$2 \cdot 3 - 2 = 4$$$ решения.
Новой подтаблицей становится $$$[(1,2),(3,3)]$$$.
Новой подтаблицей становится $$$[(1,3),(3,3)]$$$.
Новой подтаблицей становится $$$[(1,3),(2,3)]$$$.
Новой подтаблицей становится $$$[(1,3),(1,3)]$$$.
После всех решений Сиркьюити оказывается в клетке $$$(1,3)$$$, которая действительно является целевой.
