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

В начальной клетке минимальная и максимальная суммы равны стоимости этой клетки: $1$.

Для каждой следующей клетки считаем две величины: минимальную и максимальную сумму на пути из левой верхней клетки. В клетку можно попасть только из верхней или левой клетки.$$m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1}),\quad M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$

Создаём две таблицы. В первой храним максимальную сумму монет, которую можно собрать при попадании в каждую клетку, во второй — минимальную.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$

При вычислении учитываем стены: переход через стену исключается. Для минимальной суммы вместо максимума берём минимум.$$m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$

Обозначим через $max[i][j]$ и $min[i][j]$ максимальную и минимальную суммы монет на пути из левой верхней клетки в клетку $(i,j)$.

Для каждой клетки рассмотрим переходы сверху и слева. Переход учитывается только в том случае, если между соответствующими клетками нет стены.

Робот может прийти в клетку только из клетки сверху или из клетки слева. Поэтому для каждой клетки вычисляем максимальную и минимальную суммы, которые можно набрать при попадании в неё.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1}),\quad m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$

В первой строке и первом столбце значение накапливается единственным возможным маршрутом. Затем таблицы заполняются слева направо и сверху вниз.

После первого хода Пети возможны позиции $(16,S)$, $(14,S+2)$, $(28,S)$ и $(14,2S)$.

Для минимального значения $S$ выгоднее всего Петя должен удвоить вторую кучу. Тогда после его хода получится позиция $(14,2S)$.

Построим дерево возможных позиций игры и классифицируем позиции по выигрышной стратегии: выигрышные позиции позволяют игроку завершить игру или перейти в проигрышную позицию соперника.

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

Петя не должен иметь возможности выиграть одним ходом. Для этого после начального количества камней должно быть меньше 33 камней, поскольку при $S\geq 33$ Петя сможет удвоить кучу и получить не менее 66 камней.$$S<33$$

После любого хода Пети Ваня должен иметь возможность выиграть одним ходом. Если после хода Пети в куче не менее 33 камней, Ваня удваивает их количество и получает не менее 66 камней.$$S+1\geq 33,\quad 2S\geq 33$$

Чтобы Петя не выиграл первым ходом, после каждого возможного хода количество камней должно быть меньше 35:$$S+1<35,\quad S+4<35,\quad 2S<35$$

Из условия $2S<35$ следует $S\leq 17$. Именно это ограничение является наиболее сильным.

Петя выигрывает за один ход, если после одного из его ходов количество камней становится не более 17.$$S-2 \le 17 \quad\text{или}\quad S-4 \le 17 \quad\text{или}\quad \left\lfloor\frac{S}{3}\right\rfloor \le 17$$

Для третьего варианта условие выполняется при $S \le 53$. Поэтому при $S=54$ Петя уже не может выиграть за один ход: после его ходов остаётся $52$, $50$ или $18$ камней.

Петя не должен иметь возможности выиграть первым ходом. Поэтому после любого его хода количество камней должно быть меньше 103: $S+1<103$, $S+4<103$ и $3S<103$.

Из последнего неравенства получаем $S \le 34$.

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

Из второго неравенства следует $S\leq 64$. Значение $S=64$ является наибольшим возможным кандидатом.

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

Минимальное целое значение $n$, из которого можно выиграть одним ходом, равно 25.

Чтобы Петя не выиграл первым ходом, после каждого из его возможных ходов количество камней должно быть меньше 91:$$S+1<91,\quad S+4<91,\quad 3S<91$$

Наиболее ограничивающим является условие $3S<91$, поэтому $S\leq 30$.

Петя не должен иметь возможности выиграть за один ход. Для этого ни один из результатов его ходов не должен быть не менее 58. В частности, $2S < 58$, поэтому $S \leq 28$.

После любого хода Пети Ваня должен иметь возможность выиграть одним ходом. Если после хода Пети в куче $x$ камней, то Ваня выигрывает при $x \geq 29$ удвоением, при $x \geq 54$ добавлением 4 или при $x \geq 57$ добавлением 1.

Петя не должен иметь возможности выиграть одним ходом. Поэтому после любого его первого хода количество камней должно быть меньше 38: $S+1<38$ и $2S<38$.

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

Петя не должен иметь возможности выиграть первым ходом. Поэтому для начального значения $S$ должно выполняться $2S < 27$, а также $S+4 < 27$. Наиболее существенное ограничение даёт удвоение: $S \leq 13$.$$2S < 27$$

Ваня может выиграть одним ходом из позиции $x$, если удвоением получить не менее 27 камней. Это возможно при $x \geq 14$.$$2x \geq 27 \Rightarrow x \geq 14$$

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

Чтобы Ваня мог выиграть после любого хода Пети, обе возможные позиции после хода Пети должны позволять Ване завершить игру. При ходе «добавить один камень» необходимо $S+1\geq 67$, поэтому $S\geq 66$.

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

Наиболее ограничивающим является условие $3S<85$, поэтому $S\leq 28$.

После первого хода Пети возможны четыре позиции: $(17,S)$, $(14,S+3)$, $(42,S)$ и $(14,3S)$.

Проверим вариант, при котором Петя утроил вторую кучу. После этого позиция имеет вид $(14,3S)$, а сумма камней равна $14+3S$, поэтому ход Пети не является завершающим при найденном значении $S$.

Начинаем с $s=0$ и последовательно выполняем цикл. При $i=1$: $53 \mathbin{\ div} 17=3$, поэтому $A[1]$ не меняется.

При $i=2$: $17 \mathbin{\ div} 33=0<2$, поэтому $s=33$. При $i=3$: $33 \mathbin{\ div} 12=2$, поэтому $A[3]=12\cdot3=36$.