Educational Codeforces Round 100

Revision ru1, by nechaev, 2021-01-07 09:56:17

1463A - Dungeon

Очередная простая задача над которой я слишком долго думал. Опишу здесь ход своих мыслей: довольно витееватый, нужно заметить.

Начнем с того, что перефразируем задачу:

У нас имеется три колонки высотой $$$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$$$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru5 Russian nechaev 2021-01-09 17:52:23 0 (опубликовано)
ru4 Russian nechaev 2021-01-09 17:52:03 4 Мелкая правка: 'n$$\n\sum{a_k - b_k} \leqslan' -> 'n$$\n\sum{(a_k - b_k)} \leqslan'
ru3 Russian nechaev 2021-01-09 17:47:08 1863 Problems: B and D
ru2 Russian nechaev 2021-01-07 09:58:21 2 Мелкая правка: 'вольно витееватый, ну' -> 'вольно витиеватый, ну'
ru1 Russian nechaev 2021-01-07 09:56:17 2848 edu_100_A (сохранено в черновиках)