Обратите внимание на необычное распределение баллов между 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$$$, он выберет ровно одно из следующих действий:

• Действие U: увеличить $$$x_0$$$ на $$$1$$$
• Действие L: увеличить $$$y_0$$$ на $$$1$$$
• Действие D: уменьшить $$$x_1$$$ на $$$1$$$
• Действие R: уменьшить $$$y_1$$$ на $$$1$$$

Обратите внимание, что это решение не зависит от предыдущих решений и не может напрямую зависеть от значений $$$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 = 3,10,11,\ldots,40$$$ используется ровно в одном тесте, в указанном порядке.
• Для каждого допустимого $$$n$$$ выполнено $$$k=f(n)$$$, где $$$f(n)$$$ — минимальное возможное число нулей в худшем случае, необходимое для кодирования любой клетки таблицы $$$n \times n$$$.