Информатика ЕГЭ — решения заданий ФИПИ с ответами

Переменная $s$ изначально равна 0. На каждом шаге цикла сравниваются соседние элементы $A[j]$ и $A[j+1]$.

Если $A[j] > A[j+1]$, выполняется обмен элементов, а значение $s$ увеличивается на 1.

Инициализируем счётчик подходящих элементов нулём.$$j = 0$$

Первым циклом просматриваем весь массив. Элемент учитывается, если он больше 50 и его последняя цифра равна 0.$$a[i] > 50 \;\text{и}\; a[i] \bmod 10 = 0$$

Ищем минимальное число $R$, превышающее 190. Ближайшее такое число — 191, но оно не получается при рассмотрении правил построения записи.

Для чётного $N$ к двоичной записи числа слева приписывается единица, а справа — два нуля. Возьмём наименьшее число, двоичная запись которого после такого преобразования может дать значение около 191: $N=16$.

Для чётного числа с шестью двоичными разрядами слева добавляется единица, а справа — два нуля. Уже при $N=32$ получаем $R=11000000_2=192$, а при $N=34$ и больших чётных числах результат превышает $210$. Поэтому проверяем нечётные числа.

Для нечётного числа $N=49$ двоичная запись имеет вид $110001_2$. Сумма её цифр равна $4? Нет, сумма равна 3$, а её двоичная запись — $11_2$.

Перебираем простые числа, содержащие последовательность цифр 16 ровно один раз. Для каждого такого простого p ищем простое q с тем же свойством, чтобы произведение $pq$ было больше 1 103 285 717.$$n=pq$$

Первые подходящие произведения с наименьшими множителями имеют пары $(p,q)$: $(163,6\,769\,163)$, $(167,6\,607\,163)$, $(163,6\,770\,161)$, $(167,6\,608\,161)$ и $(163,6\,771\,161)$.

В начале $s = 0$ и $n = 0$. Условие цикла выполняется, пока $s < 71$.

После каждого прохода цикла значение $s$ увеличивается на 8. После 8 проходов $s = 64$, условие ещё выполняется.

Числа $N$ с двоичной записью длины не более трёх не превосходят 7, поэтому для поиска максимального ответа достаточно рассмотреть четырёхразрядные числа от 8 до 15.

Для $N=8$ имеем $1000_2$. Сумма цифр чётная, поэтому после дописывания нуля и замены двух левых разрядов получаем $10000_2=16$.

После первого хода первого игрока возможны четыре позиции: $(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$, создаём резервную копию накопленных данных, запоминаем её объём и очищаем раздел перед обработкой…