Задание 19 ЕГЭ по информатике: решения ФИПИ с ответами по шагам

Чтобы Ваня выиграл первым ходом после неудачного хода Пети, ход Пети должен быть неокончательным, а из полученной позиции Ваня должен иметь ход, после которого сумма станет не менее 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$$

Петя не может выиграть первым ходом, если после прибавления 1 или 4, а также после удвоения количество камней меньше 31. Для $S \le 15$ это условие выполняется.

Ваня может выиграть одним ходом из любой позиции с количеством камней не менее 16: достаточно удвоить количество камней, поскольку $2 \cdot 16 = 32 \ge 31$.

Петя выигрывает за один ход, если после одного из его ходов в куче останется не более 23 камней. Для деления на 4 это выполняется при $\lfloor S/4 \rfloor \le 23$, то есть при $S \le 95$. Поэтому минимальное значение, при котором Петя уже…$$\left\lfloor \frac{S}{4} \right\rfloor \le 23 \text{ при } S \le 95$$

Проверим значение $S=96$. После ходов Пети возможны кучи из $94$, $92$ и $24$ камней.

После хода Пети количество камней должно оставаться больше 15, иначе Петя сразу выиграет.$$S-3>15,\quad S-7>15,\quad \left\lfloor S/4 \right\rfloor>15$$

Наиболее строгое условие задаёт деление на 4: результат должен быть не меньше 16.$$\left\lfloor S/4 \right\rfloor\ge 16 \Rightarrow S\ge 64$$

Чтобы Петя не смог выиграть за один ход, ни один из возможных результатов его хода не должен достигать 97.$$S+1<97,\quad S+4<97,\quad 3S<97$$

Наиболее сильное ограничение даёт неравенство $3S<97$, откуда $S\leq 32$.