Тапсырма 26 ЕГЭ по информатикаға: ФИПИ шешімдері қадамдық жауаптарымен

После первого хода первого игрока возможны четыре позиции: $(4, 2)$, $(3, 3)$, $(9, 2)$ или $(3, 6)$.

Позиция $(4, 3)$ проигрышна для игрока, которому предстоит ходить. Действительно, из неё нельзя сразу получить сумму не менее 16. После добавления камня получаются позиции $(5, 3)$ или $(4, 4)$, после утроения — $(12, 3)$ или $(4, 9)$. В…

Запишем каждую коробку как пару: длина стороны и материал. Отсортируем коробки по длине стороны.

Для коробки длины $x$ и материала $c$ допустимым предшественником является коробка материала $1-c$ с длиной не более $x-D$.

Из позиции (4, 33) Петя удваивает вторую кучу и получает позицию (4, 66), в которой сумма камней равна 70. После любого хода Вани Петя получает возможность завершить игру, а непосредственно из (4, 33) также можно удвоить вторую кучу до…

Однако более сильный непосредственный ход из позиции (4, 33) — удвоить вторую кучу: получается (4, 66), сумма равна 70. Ваня может добавить камень или удвоить одну из куч, после чего сумма станет не менее 71. Поэтому Петя выигрывает…

В задании 1 из позиции $(10,S)$ Петя может получить позиции $(10+S,S)$ и $(10,10+S)$. Их суммы равны $10+2S$ и $20+S$ соответственно. Чтобы Петя не мог выиграть одним ходом, обе суммы должны быть меньше 29.$$10+2S<29,\quad 20+S<29$$

Из второго неравенства получаем $S<9$, поэтому максимальное целое значение $S$ равно 8. При $S=8$ после ходов получаются суммы 26 и 28, то есть выиграть одним ходом нельзя.$$S_{\max}=8$$

Петя выигрывает одним ходом, если хотя бы один из переходов $S+2$, $S+3$, $2S$ даёт не менее 60. При $1 \leq S \leq 59$ это выполняется при $S \geq 30$.$$S \in \{30,31,\ldots,59\}$$

Для задания 1б можно взять $S=28$. После хода Пети получаются позиции 30, 31 или 56. Из позиций 30 и 31 Ваня удваивает количество камней, а из позиции 56 также удваивает его и сразу получает не менее 60.$$28 \to 30,31,56;\quad 30\to60,\ 31\to62,\ 56\to112$$

Для каждого запроса преобразуем время в секунды от начала суток и сравниваем его с 11:59:59. Если запрос подходит по времени, увеличиваем суммарный объём данных соответствующего клиента.$$t = 3600h + 60m + s$$

Перед размещением запроса проверяем, достаточно ли свободного места. Если текущий объём памяти вместе с новым запросом превысит K, текущий объём становится очередной резервной копией, после чего раздел освобождается.$$M + S > K \Rightarrow B_i = M,\ M = 0$$

В задании 1 Петя может заменить число 12 на сумму чисел. Тогда получится позиция $(12+S,S)$ с суммой $12+2S$. Требуется $12+2S\ge67$, поэтому $S\ge27{,}5$. Так как $S$ — целое число, минимальное значение равно 28.$$12+2S\ge67\Rightarrow S\ge27{,}5$$

В задании 2 из позиции $(15,14)$ Петя может получить либо $(29,14)$, либо $(15,29)$. В первом случае Ваня заменяет 14 на сумму и получает $(29,43)$, сумма которой равна 72. Во втором случае Ваня заменяет 15 на сумму и получает $(44,29)$…$$29+43=72\ge67,\qquad 44+29=73\ge67$$

Для каждого идентификатора клиента поддерживаем суммарный объём переданных данных. Это можно сделать словарём, не храня весь журнал.$$total[C] \mathrel{+}= S$$

Поддерживаем объём данных, накопленных в специальном разделе. Если очередной запрос не помещается, текущий объём становится резервной копией, после чего раздел освобождается.$$current + S > K \Rightarrow backups.append(current),\ current = 0$$

Из начальной позиции $(7,S)$ Петя может выиграть одним ходом, если после одного из возможных ходов сумма станет не менее 65.$$7+S+1\geq65 \Rightarrow S\geq57;\quad 14+S\geq65 \Rightarrow S\geq51;\quad 7+2S\geq65 \Rightarrow S\geq29$$

Объединяя условия, получаем все значения $S$ от 29 до 57 включительно.$$S\in\{29,30,\ldots,57\}$$

Считаем все размеры коробок и сортируем их по неубыванию. Одинаковые размеры нельзя использовать последовательно, поскольку их разность меньше 7.

Для каждой позиции вычисляем длину максимальной цепочки, которая заканчивается коробкой на этой позиции: рассматриваем предыдущие коробки с размером не больше текущего минус 7.

Если в куче не менее $13$ камней, игрок может умножить количество камней на 5 и получить не менее $65$. Поэтому Петя выигрывает за один ход при всех $13 \leq S \leq 62$.$$5S \geq 63 \Longleftrightarrow S \geq 13$$

Для меньших значений последовательно определяем проигрышные позиции. Позиция проигрышная, если все возможные ходы переводят её в выигрышную позицию.$$L=\{1,4,7,9,10,12\}$$

Из начальной позиции $(6,S)$ Петя может выиграть за один ход утроением второй кучи, если $6+3S\geq74$. Отсюда $S\geq23$. При меньших значениях утроение первой кучи и добавление одного камня также не дают выигрыша.$$6+3S\geq74\Longleftrightarrow S\geq\frac{68}{3}\Longleftrightarrow S\geq23$$

Следовательно, в задании 1а подходят все значения $S$ от 23 до 67.

Для каждого запроса увеличиваем сумму переданных данных соответствующего клиента на величину $S$.

Поддерживаем объём данных в специальном разделе. Если текущий объём вместе с новым запросом становится не меньше вместимости раздела $K$, создаём резервную копию накопленных данных, запоминаем её объём и очищаем раздел перед обработкой…

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

Для каждой коробки определите максимальную длину цепочки, заканчивающейся этой коробкой. Предыдущая коробка должна иметь длину стороны не более $a_i - 13$.

Петя может выиграть за один ход, если после одного из разрешённых действий в куче будет не менее 68 камней. Условия $S+1 \geq 68$ и $S+4 \geq 68$ дают только значения, уже входящие в диапазон $14 \leq S \leq 67$, а условие $5S \geq 68$…$$S \in \{14,15,\ldots,67\}$$

Для задания 1б подходит $S=2$. Петя не может выиграть одним ходом: после его ходов получится 3, 6 или 10 камней. Из каждой из этих позиций Ваня выигрывает своим первым ходом: соответственно, умножением на 5 получает 15, 30 или 50? Нет…

Создаём массив времени освобождения ячеек. Изначально все ячейки свободны; это можно обозначить временем освобождения 0.

Заявки обрабатываются в порядке, указанном во входном файле. Для заявки с временем сдачи багажа t просматриваем ячейки по возрастанию номеров.

Рассмотрим позиции $(6, 27)$ и $(8, 26)$. Из позиции $(6, 27)$ возможны переходы в $(7, 27)$, $(12, 27)$, $(6, 28)$ и $(6, 54)$. В первых трёх позициях удвоение второй кучи приводит к сумме не менее 61, а из $(6, 54)$ соперник может сразу…$$6+27=33$$

Аналогично позиция $(8, 26)$ является проигрышной для игрока, делающего ход: любой его ход переводит игру в позицию, из которой следующий игрок может завершить игру или перейти к проигрышной для соперника позиции.

Сначала отсортируем все длины сторон коробок по возрастанию. Одинаковые коробки нельзя использовать последовательно, так как разность их сторон меньше 6.$$a_1 \leqslant a_2 \leqslant \dots \leqslant a_N$$

Будем просматривать отсортированный массив слева направо. Первую выбранную коробку включаем в цепочку, а следующую включаем только при выполнении условия размещения.$$a_i-a_{\text{last}}\geqslant 6$$

Считаем мероприятия совместимыми, если начало следующего мероприятия не меньше окончания предыдущего.

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

Петя может выиграть первым ходом, если после одного из разрешённых действий сумма камней станет не менее 63. Из позиции $(5,S)$ удвоение второй кучи даёт сумму $5+2S$, поэтому требуется $5+2S \geq 63$, то есть $S \geq 29$. При $S \geq 29$…$$5+2S\geq 63\Longleftrightarrow S\geq 29$$

Следовательно, в задании 1а подходят все значения $S$ от 29 до 57 включительно.