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

Петя не должен иметь возможности выиграть первым ходом. Поэтому должны выполняться неравенства $S+4<67$ и $3S<67$, откуда $S\leq 22$.

Проверим значение $S=22$. После хода Пети количество камней может стать равным $23$, $26$ или $66$.

Начальный массив: $[4, 7, 3, 8, 5, 0, 1, 2, 9, 6]$, переменная $c = 0$.

При $i = 1$: $4 < 7$, поэтому элементы меняются местами, а $c$ становится равным $1$. Массив: $[7, 4, 3, 8, 5, 0, 1, 2, 9, 6]$.

Изначально $s=0$. Последовательно сравниваем соседние элементы и при необходимости меняем их местами.

При $j=0$ перестановки нет: $0<8$.

Чтобы Петя не выиграл первым ходом, все возможные результаты его хода должны быть меньше 36: $S+1<36$, $S+4<36$ и $2S<36$.

После любого хода Пети Ваня должен иметь возможность выиграть одним ходом. При $S=17$ возможные позиции равны $18$, $21$ и $34$.

Чтобы Ваня выиграл первым ходом после неудачного хода Пети, ход Пети должен быть неокончательным, а из полученной позиции Ваня должен иметь ход, после которого сумма станет не менее 135.

При малых значениях $S$ выгоднее всего Петя удваивает вторую кучу: $(13,S) \rightarrow (13,2S)$. После этого Ваня также удваивает вторую кучу.

В начале $s=0$, $A[0]=14$. При $i=1$: $13<14$, поэтому к $s$ прибавляется $13\bmod 1=0$.

При $i=2$: $15<14$ — неверно, поэтому $A[0]$ изменяется на 15.

Чтобы найти минимальное значение $S$, рассмотрим ход Пети: он удваивает количество камней во второй куче. После этого в кучах находится 5 и $2S$ камней.$$5 + 2S < 59$$

Ваня может своим первым ходом снова удвоить вторую кучу. После этого суммарное количество камней станет равным $5 + 4S$.$$5 + 4S \geq 59$$

Петя не должен иметь возможности закончить игру своим первым ходом. Поэтому результат каждого возможного хода Пети должен быть больше 16.$$S-3>16,\quad S-8>16,\quad \left\lfloor\frac{S}{3}\right\rfloor>16$$

Наиболее строгое ограничение даёт ход с делением на 3:$$\left\lfloor\frac{S}{3}\right\rfloor>16\Rightarrow S\ge 51$$

Петя не должен иметь возможности закончить игру первым ходом. Поэтому после любого его хода количество камней должно быть больше 10.$$S-3>10,\quad S-5>10,\quad \left\lfloor\frac{S}{4}\right\rfloor>10$$

Первые два неравенства дают $S>13$ и $S>15$. Условие с делением выполняется при $S\ge 44$, так как при $S=43$ результат деления равен $10$, а при $S=44$ — $11$.$$\left\lfloor\frac{43}{4}\right\rfloor=10,\quad \left\lfloor\frac{44}{4}\right\rfloor=11$$

Чтобы Ваня выиграл своим первым ходом, после хода Пети должна существовать возможность одним действием получить не менее 231 камня. Минимальное значение $S$ получается, если Петя неудачно удваивает вторую кучу.$$17 + S \xrightarrow{\text{Петя}} 17 + 2S$$

Ваня удваивает вторую кучу ещё раз. После этого общее количество камней равно:$$17 + 4S$$

Рассмотрим неудачный первый ход Пети: он удваивает вторую кучу. Позиция становится $(13, 2S)$.

Ваня может своим первым ходом снова удвоить вторую кучу. После этого суммарное количество камней будет равно:$$13 + 4S$$

Изначально $s=0$, $n=0$, поэтому при каждом выполнении условия используется элемент $A[0]$. Начальное значение $A[0]$ равно 24.

При $i=1$: $17 \bmod 1=0$, поэтому $s=0+24=24$.

Петя может первым ходом увеличить вторую кучу в 3 раза. После этого получится позиция $(11, 3S)$.

Ваня может своим первым ходом снова увеличить вторую кучу в 3 раза. Тогда суммарное количество камней станет равным:$$11 + 9S$$

Чтобы Петя не выиграл первым ходом, после каждого возможного хода число камней должно быть меньше 55. В частности, для позиции $S=18$ это так: $18+1=19$, $18+4=22$, $18\cdot3=54$.

Проверим ответы Вани после каждого хода Пети. Из позиции $19$ Ваня умножает количество камней на $3$: $19\cdot3=57$.

Чтобы Петя не выиграл первым ходом, после его удвоения количество камней должно быть меньше 145:$$2S < 145$$

Если Петя добавит один камень, Ваня должен суметь выиграть удвоением:$$2(S+1) \geq 145$$

Петя не должен иметь возможности закончить игру первым ходом. При $S=24$ после любого его хода количество камней остаётся меньше 73.$$24+1=25<73,\quad 24+4=28<73,\quad 24\cdot 3=72<73$$

Если Петя добавляет 1 камень, Ваня умножает количество камней на 3 и получает не менее 73.$$25\cdot 3=75\geq 73$$

Игрок может выиграть одним ходом из позиции $x$, если после добавления одного камня или удвоения количества камней получится не менее 69 камней.$$x+1 \geq 69 \quad \text{или} \quad 2x \geq 69$$

Минимальное целое значение $x$, из которого можно выиграть одним ходом, равно 35: при $x=35$ удвоение даёт 70 камней.

Чтобы Ваня выиграл своим первым ходом, после хода Пети сумма камней должна оставаться меньше 255, но одно действие Вани должно увеличить её как минимум до 255.

Петя может удвоить вторую кучу. Тогда в кучах будет $17$ и $2S$ камней. Ваня также удваивает вторую кучу, поэтому итоговое количество камней равно:$$17 + 4S$$

Чтобы Ваня выиграл своим первым ходом, после хода Пети должна существовать куча, удвоение которой приведёт к сумме не менее 107.$$13 + 4S \geq 107$$

Наименьшее значение $S$ определяется из неравенства:$$4S \geq 94,\quad S \geq 23{,}5$$

Петя не должен выигрывать своим первым ходом, поэтому после каждого его хода количество камней должно оставаться больше 30. Для $S=124$ возможны позиции $121$, $119$ и $31$.$$124-3=121,\quad 124-5=119,\quad \left\lfloor\dfrac{124}{4}\right\rfloor=31$$

Из каждой полученной позиции Ваня может сделать ход, после которого в куче будет не более 30 камней.$$121\to\left\lfloor\dfrac{121}{4}\right\rfloor=30,\quad 119\to\left\lfloor\dfrac{119}{4}\right\rfloor=29,\quad 31\to31-3=28$$