Очередная простая задача над которой я слишком долго думал. Опишу здесь ход своих мыслей: довольно витиеватый, нужно заметить.
Начнем с того, что перефразируем задачу:
У нас имеется три колонки высотой $$$a$$$, $$$b$$$ и $$$c$$$. На каждом ходу, номер которого не делится на $$$7$$$ без остатка, мы срезаем любую из колонок сверху на единицу. Если же номер хода делится на $$$7$$$, то мы срезаем единицу в нижней части каждой из колонок. Ни одна из них не должна быть пустой перед проведением такой операции.
Наша задача: свести в ноль все колонки на ходе кратном $$$7$$$.
Разобьем весь процесс на раунды. В каждом раунде есть $$$6$$$ ходов, когда мы срезаем единицу, и $$$1$$$ ход, когда мы срезаем тройку (супершот). В сумме за раунд мы удаляем $$$9$$$ единиц. Значит общее количество раундов $$$k = \frac{a + b + c}{9}$$$
Высота самой низкой колонки $$$h = \min(a, b, c)$$$. Все три колонки содержат $$$3h$$$ единиц вплоть до уровня $$$h$$$. Поверх этого уровня находятся неудобные остатки $$$d = a + b + c - 3h$$$, которые нужно как-то удалить за количество ходов не превышающее $$$h$$$. При этом понятно, что $$$3$$$ делит $$$d$$$ потому, что $$$3$$$ делит $$$a + b + c$$$.
В каждом раунде мы сможем удалять только $$$6$$$ единиц из этих остатков. Значит, для почти полного удаления остатков нам нужно $$$\left\lfloor\frac{d}{6}\right\rfloor$$$ раундов.
Проведем $$$x = min(h, \left\lfloor\frac{d}{6}\right\rfloor)$$$ раундов.
В случае, когда супершоты съедают все колонки до того как мы избавимся от остатков, имеем $$$h < \left\lfloor\frac{d}{6}\right\rfloor$$$ и, соответсвтенно, $$$x = h$$$. Далее эквивалентными преобразованиями получаем
Последнее неравенство означает, что если после $$$x$$$ раундов количество остатков превышает $$$d \bmod 6$$$, которое может быть только 0 или 3, то супершоты уничтожают самую маленькую колонку до того, как нам удастся убрать остатки, а значит наш ответ NO.
В противном случае должно выполняться равенство
Здеь возможны две ситуации
Поскольку после каждого раунда выполняется инвариант, о том, что суммарная длина колонок делится на $$$9$$$, то это означает, что под остатками должны быть еще $$$2$$$ ряда из $$$3$$$ единиц, которые могут быть уничтожены за один раунд. Далее у нас остаются $$$3$$$ колонки равной высоты кратной $$$3$$$. А это значит, что решение есть.
Вторая ситуация, когда
означает, что все колонки оказались одинаковой высоты. Благодаря инварианту о делимости на $$$9$$$ после каждого раунда, мы знаем, что все эти три колонки могут быть успешно уничтожены.
Таким образом решение существует, если $$$a + b + c$$$ делится на $$$9$$$ и если $$$d - \min(h, \left\lfloor\frac{d}{6}\right\rfloor) \leqslant 3$$$.
Решение из эдиториала как-то не пришло мне в голову. Вместо этого я использовал массив $$$b$$$ такой, что
что по-сути означает
Если для любого $$$k$$$ выполняется $$$a_k - b_k \leqslant \frac{a}{2}$$$, то тогда мы можем сказать, что
Для нашего $$$b_k$$$ это действительно так: Пусть в двоичной записи $$$a_k = 1\text{xxxx}$$$, тогда $$$b_k = 10000$$$, а $$$\frac{a_k}{2} = 01\text{xxx}$$$, т.е. для любого $$$b_k$$$ мы имеем
Посчитаем, какое минимальное количество элементов $$$b_k$$$ должно быть младшим в паре и назовем его $$$x_\min$$$. Также посчитаем минимальное количество элементов $$$b_k$$$, которые должны быть старшими в паре и назовем его $$$y_\min$$$. Тогда очевидно, что $$$x_\max = n - y_\min$$$. Значит ответом будет $$$x_\max - x_\min + 1$$$.
Остается теперь только вычислить $$$x_\min$$$ и $$$y_\min$$$. Делать это мы будем следующим образом:
В массиве $$$A = [1 .. 2n]$$$, нумеруемом начиная с 1, пометим все позиции занятые $$$b_k$$$. Далее применим следующее dp:
count_A[0] = 0; // Количество занятых позиций, где A[k] == 1.
vacant_count[0] = 0; // Количество незанятых позиций (A[k] == 0), не связаных ни в какой паре.
x_min[0] = 0;
// Далее в цикле по k <-- 1 .. n:
count_A[k] = count_A[k - 1] + A[k];
// Элемент становится младшим в паре только если он не может стать старшим
x_min[k] = x_min[k - 1] + (A[k] && vacant_count[k - 1] == 0 ? 1 : 0);
// k - count_A[k] - количество незанятых позиций.
// count_A[k] - min_x[k] - количество занятых позиций, являющихся старшими в паре
vacant_count[k] = (k - count_A[k]) - (count_A[k] - x_min[k]);
Аналогичным образом мы можем рассчитать $$$y_\min$$$.
Comments (0)
