[problem:1463A]↵
↵
Очередная простая задача над которой я слишком долго думал.↵
Опишу здесь ход своих мыслей: довольно витиеватый, нужно заметить.↵
↵
Начнем с того, что перефразируем задачу:↵
↵
У нас имеется три колонки высотой $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$.↵
Далее эквивалентными преобразованиями получаем↵
$$↵
6x < 6 \left\lfloor\frac{d}{6}\right\rfloor↵
$$↵
$$↵
d - 6\left\lfloor\frac{d}{6}\right\rfloor < d - 6x↵
$$↵
$$↵
d \bmod 6 < d - 6x↵
$$↵
Последнее неравенство означает, что↵
если после $x$ раундов количество остатков превышает $d \bmod 6$, которое может быть только 0 или 3, то супершоты уничтожают самую маленькую колонку до того, как нам удастся убрать остатки, а значит наш ответ _NO_.↵
↵
В противном случае должно выполняться равенство↵
$$↵
d \bmod 6 = d - 6x↵
$$↵
Здеь возможны две ситуации↵
$$↵
d - 6x = 3↵
$$↵
Поскольку после каждого раунда выполняется инвариант, о том, что суммарная длина колонок делится на $9$, то это означает, что под остатками должны быть еще $2$ ряда из $3$ единиц, которые могут быть уничтожены за один раунд. Далее у нас остаются $3$ колонки равной высоты кратной $3$. А это значит, что решение есть.↵
↵
Вторая ситуация, когда↵
$$↵
d - 6x = 0↵
$$↵
означает, что все колонки оказались одинаковой высоты.↵
Благодаря инварианту о делимости на $9$ после каждого раунда, мы знаем, что все эти три колонки могут быть успешно уничтожены.↵
↵
Таким образом решение существует, если↵
$a + b + c$ делится на $9$ и если $d - \min(h, \left\lfloor\frac{d}{6}\right\rfloor) \leqslant 3$.↵
↵
↵
[problem:1463B]↵
↵
Решение из эдиториала как-то не пришло мне в голову.↵
Вместо этого я использовал массив $b$ такой, что↵
$$↵
b_k = 2^{\lfloor\lg{a_k}\rfloor}↵
$$↵
что по-сути означает↵
$$↵
b_k = 2^{\alpha{}_k}: 2^{\alpha{}_k} \leqslant a_k < 2^{\alpha{}_k + 1}↵
$$↵
Если для любого $k$ выполняется $a_k - b_k \leqslant \frac{a}{2}$, то тогда мы можем сказать, что↵
$$↵
\sum{(a_k - b_k)} \leqslant \sum{\frac{a_k}{2}} = \frac{S}{2}↵
$$↵
Для нашего $b_k$ это действительно так:↵
Пусть в двоичной записи $a_k = 1\text{xxxx}$, тогда $b_k = 10000$, а $\frac{a_k}{2} = 01\text{xxx}$, т.е. для любого $b_k$ мы имеем↵
$$↵
b_k \leqslant \frac{a_k}{2}↵
$$↵
↵
↵
[problem:1463D]↵
↵
Посчитаем, какое минимальное количество элементов $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] ==01.↵
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$.
↵
Очередная простая задача над которой я слишком долго думал.↵
Опишу здесь ход своих мыслей: довольно витиеватый, нужно заметить.↵
↵
Начнем с того, что перефразируем задачу:↵
↵
У нас имеется три колонки высотой $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$.↵
Далее эквивалентными преобразованиями получаем↵
$$↵
6x < 6 \left\lfloor\frac{d}{6}\right\rfloor↵
$$↵
$$↵
d - 6\left\lfloor\frac{d}{6}\right\rfloor < d - 6x↵
$$↵
$$↵
d \bmod 6 < d - 6x↵
$$↵
Последнее неравенство означает, что↵
если после $x$ раундов количество остатков превышает $d \bmod 6$, которое может быть только 0 или 3, то супершоты уничтожают самую маленькую колонку до того, как нам удастся убрать остатки, а значит наш ответ _NO_.↵
↵
В противном случае должно выполняться равенство↵
$$↵
d \bmod 6 = d - 6x↵
$$↵
Здеь возможны две ситуации↵
$$↵
d - 6x = 3↵
$$↵
Поскольку после каждого раунда выполняется инвариант, о том, что суммарная длина колонок делится на $9$, то это означает, что под остатками должны быть еще $2$ ряда из $3$ единиц, которые могут быть уничтожены за один раунд. Далее у нас остаются $3$ колонки равной высоты кратной $3$. А это значит, что решение есть.↵
↵
Вторая ситуация, когда↵
$$↵
d - 6x = 0↵
$$↵
означает, что все колонки оказались одинаковой высоты.↵
Благодаря инварианту о делимости на $9$ после каждого раунда, мы знаем, что все эти три колонки могут быть успешно уничтожены.↵
↵
Таким образом решение существует, если↵
$a + b + c$ делится на $9$ и если $d - \min(h, \left\lfloor\frac{d}{6}\right\rfloor) \leqslant 3$.↵
↵
↵
[problem:1463B]↵
↵
Решение из эдиториала как-то не пришло мне в голову.↵
Вместо этого я использовал массив $b$ такой, что↵
$$↵
b_k = 2^{\lfloor\lg{a_k}\rfloor}↵
$$↵
что по-сути означает↵
$$↵
b_k = 2^{\alpha{}_k}: 2^{\alpha{}_k} \leqslant a_k < 2^{\alpha{}_k + 1}↵
$$↵
Если для любого $k$ выполняется $a_k - b_k \leqslant \frac{a}{2}$, то тогда мы можем сказать, что↵
$$↵
\sum{(a_k - b_k)} \leqslant \sum{\frac{a_k}{2}} = \frac{S}{2}↵
$$↵
Для нашего $b_k$ это действительно так:↵
Пусть в двоичной записи $a_k = 1\text{xxxx}$, тогда $b_k = 10000$, а $\frac{a_k}{2} = 01\text{xxx}$, т.е. для любого $b_k$ мы имеем↵
$$↵
b_k \leqslant \frac{a_k}{2}↵
$$↵
↵
↵
[problem:1463D]↵
↵
Посчитаем, какое минимальное количество элементов $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] ==
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$.
