Нестандартные задачи —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#56478

Для правил, описанных в задании 19 найдите наименьшее $N > 105$ , для которого у Пети есть выигрышная стратегия.

Показать ответ и решение

Давайте рассмотрим 3 случая для этой задачи:

1) $N$ нечетно

2) $N$ четно, а $N$ не является степенью $2$

3) $N$ — степень $2$

Если $N$ нечетно, единственный ход - вычесть нечетный делитель (поскольку все делители нечетные). Делая это, мы получим четное число, которое не является степенью 2 (случай 2). Если $D$ является делителем $N$ , то $N − D$ также должен быть кратным $D$ , и так как $D$ нечетно, то $N − D$ не может быть степенью числа $2$ .

Если $N$ четно и не является степенью 2, это означает, что $N$ имеет нечетный делитель. Вычитая этот нечетный делитель, мы получим $N − D$ нечетное (случай 1).

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

Итак, мы доказали, что нечетные числа проигрывают, а четные числа, которые не являются степенями $2$ , выигрывают.

Что делать, если $N$ - это степень $2$ ? Вы можете сделать две вещи за один ход, уменьшить вдвое $N$ или сделать $N$ четным числом, которое не является степенью $2$ (мы доказали, что это выигрышная позиция для другого игрока).

Единственный оптимальный ход - уменьшить $N$ вдвое, сделав его еще одной степенью 2. Игроки продолжают в том же духе, пока один из них не получит 2, что является простым числом, так что он проигрывает. Если $log2(n )$ четное, выигрывает Петя, в противном случае выигрывает Вася.

19.5) В задаче фактически просят найти наибольшее простое не превышающее 100. Ответ: 97

20.5) Получить ответ можно либо перебором начиная от 22, либо после полноценного решения задачи разбором всех случаев. Ответ: 22

21.5) Следует провести полноценные рассуждения об анализе выигрышных и проигрышных позиций. Ответ: 100002.

Ответ: 100002

Ошибка.
Попробуйте повторить позже

Задача 2#56477

Для правил, описанных в задании 19 известно, что $N = 24$ .

Петя сделал неудачный ход и после этого проиграл игру (было сделано ещё какое-то неизвестное количество ходов). Найдите наибольшее значение, которое могло принимать $N$ , после неудачного первого хода Пети.

Показать ответ и решение

Давайте рассмотрим 3 случая для этой задачи:

1) $N$ нечетно

2) $N$ четно, а $N$ не является степенью $2$

3) $N$ — степень $2$

Если $N$ нечетно, единственный ход - вычесть нечетный делитель (поскольку все делители нечетные). Делая это, мы получим четное число, которое не является степенью 2 (случай 2). Если $D$ является делителем $N$ , то $N − D$ также должен быть кратным $D$ , и так как $D$ нечетно, то $N − D$ не может быть степенью числа $2$ .

Если $N$ четно и не является степенью 2, это означает, что $N$ имеет нечетный делитель. Вычитая этот нечетный делитель, мы получим $N − D$ нечетное (случай 1).

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

Итак, мы доказали, что нечетные числа проигрывают, а четные числа, которые не являются степенями $2$ , выигрывают.

Что делать, если $N$ - это степень $2$ ? Вы можете сделать две вещи за один ход, уменьшить вдвое $N$ или сделать $N$ четным числом, которое не является степенью $2$ (мы доказали, что это выигрышная позиция для другого игрока).

Единственный оптимальный ход - уменьшить $N$ вдвое, сделав его еще одной степенью 2. Игроки продолжают в том же духе, пока один из них не получит 2, что является простым числом, так что он проигрывает. Если $log2(n )$ четное, выигрывает Петя, в противном случае выигрывает Вася.

19.5) В задаче фактически просят найти наибольшее простое не превышающее 100. Ответ: 97

20.5) Получить ответ можно либо перебором начиная от 22, либо после полноценного решения задачи разбором всех случаев. Ответ: 22

21.5) Следует провести полноценные рассуждения об анализе выигрышных и проигрышных позиций. Ответ: 100002.

Ответ: 22

Ошибка.
Попробуйте повторить позже

Задача 3#56476

Петя и Вася играют в игру. Они начинают с целого положительного числа $N$ и поочередно выполняют над ним операции. В свой ход игрок может вычесть из $N$ один из его делителей, который не равен $1$ или $N$ . Игрок, который не может сделать ход проигрывает. Начинает Петя.

Известно, что Петя проиграл первым же ходом(не смог сделать первый ход). Найдите наибольшее возможное $N$ , не превышающее $100$ , для которого это могло случится.

Показать ответ и решение

Давайте рассмотрим 3 случая для этой задачи:

1) $N$ нечетно

2) $N$ четно, а $N$ не является степенью $2$

3) $N$ — степень $2$

Если $N$ нечетно, единственный ход - вычесть нечетный делитель (поскольку все делители нечетные). Делая это, мы получим четное число, которое не является степенью 2 (случай 2). Если $D$ является делителем $N$ , то $N − D$ также должен быть кратным $D$ , и так как $D$ нечетно, то $N − D$ не может быть степенью числа $2$ .

Если $N$ четно и не является степенью 2, это означает, что $N$ имеет нечетный делитель. Вычитая этот нечетный делитель, мы получим $N − D$ нечетное (случай 1).

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

Итак, мы доказали, что нечетные числа проигрывают, а четные числа, которые не являются степенями $2$ , выигрывают.

Что делать, если $N$ - это степень $2$ ? Вы можете сделать две вещи за один ход, уменьшить вдвое $N$ или сделать $N$ четным числом, которое не является степенью $2$ (мы доказали, что это выигрышная позиция для другого игрока).

Единственный оптимальный ход - уменьшить $N$ вдвое, сделав его еще одной степенью 2. Игроки продолжают в том же духе, пока один из них не получит 2, что является простым числом, так что он проигрывает. Если $log2(n )$ четное, выигрывает Петя, в противном случае выигрывает Вася.

19.5) В задаче фактически просят найти наибольшее простое не превышающее 100. Ответ: 97

20.5) Получить ответ можно либо перебором начиная от 22, либо после полноценного решения задачи разбором всех случаев. Ответ: 22

21.5) Следует провести полноценные рассуждения об анализе выигрышных и проигрышных позиций. Ответ: 100002.

Ответ: 97

Ошибка.
Попробуйте повторить позже

Задача 4#46174

Для правил, описанных в задании 19 известно, что $N = 100000$ . Какой игрок имеет выигрышную стратегию и за сколько ходов он победит? В ответ запишите сумму. Например, если первый гарантированно побеждает за 2 хода, но при этом при неправильной игре второго может победить и за один ход, то считается, что первый побеждает за 2 хода, а в ответ нужно записать 1 + 2 = 3.

Показать ответ и решение

Первый имеет выигрышную стратегию. Он выиграет за 16 ходов. Ответ: 17.

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 5#46173

Для правил, описанных в задании 19 известно, что $N = 100000$ . Какой игрок имеет выигрышную стратегию и за сколько ходов он победит? В ответ запишите сумму. Например, если первый гарантированно побеждает за 2 хода, но при этом при неправильной игре второго может победить и за один ход, то считается, что первый побеждает за 2 хода, а в ответ нужно записать 1 + 2 = 3.

Показать ответ и решение

Первый мог убрать 1, 2, 3, 4, ..., 7, 8, 10, 11, ..., 20. Итого 20 * 21 / 2 - 9 = 201

Ответ: 201

Ошибка.
Попробуйте повторить позже

Задача 6#46172

На столе выложено $N$ спичек. Играют двое. Ход состоит в том, чтобы убрать со стола не более половины спичек, но не менее 1. Проигрывает тот, кто не может сделать ход. При $N = 15$ . Какой игрок имеет выигрышную стратегию? В ответе укажите его номер (1 или 2 соответственно).

Показать ответ и решение

Заметим, что проигрышными являются позиции вида $2t − 1$ , где $t > − 1$ . Более того, позиция вида $2t − 1$ , где $t > 1$ является позицией типа $‘LOSET − 1′$ , а для произвольного числа $q$ , которое не является степенью двойки уменьшенной на один, есть всегда и ровно 1 выигрышный ход в позицию вида $2t − 1$ , достаточно лишь найти наибольшее такое $t$ , что $t 2 −$ 1 меньше чем $q$ , а позиция тогда является позицией типа $′ ‘W IN T$ .

Для решения номеров 19 и 20 достаточно лишь анализа всех позиций от 1 до 40.

19) Ответ: 2

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 7#43479

Для правил, описанных в задании $19$ известно, что $m = 15$ и что $n > 10$ , и при этом первый игрок не при любом начальном количестве камней может играть так, чтобы выиграть (при любой игре второго). Найдите максимальное значение $n$ .

Показать ответ и решение

Если при любом количестве камней в куче первый может сделать ход так, чтобы в куче осталось число камней, отличное и от m, и от n, то он победит. Пусть в куче k камней и ход первого. Если $k <= 10$ , то первый выигрывает одним ходом (вычитая 10, если $k = 10$ , или $1$ , если $k <= 9$ ). Пусть $k > 10$ . Первый может оставить в куче либо $k − 1$ камень, либо $k − 10$ . Если бы в одном случае получалось $m$ , а в другом – $n$ , число $|m − n|$ равнялось бы 9.

Значит, для $m = 15$ единственное возможное n - это 24.

Ответ: 24

Ошибка.
Попробуйте повторить позже

Задача 8#43478

Для правил, описанных в задании $19$ известно, что $S = 20$ , $m = 2$ , $n = 3$ .

Кто побеждает при правильной игре? В ответе запишите номер игрока.

Показать ответ и решение

Ходы для каждого из игроков различны, значит стоит рассматривать выигрышные проигрышные позиции для двух игроков. Иначе говоря, считать не стандартные state[x][y], а state[x][y][type]. Анализ позиций приводит к ответу: выигрывает второй. Позиция S = 20, для первого игрока является позицией типа LOSE5

from functools import lru_cache

def h1(n):
    if (n >= 10):
        return n - 1, n - 10
    else:
        return n - 1, n - 1

def h2(n):
    if (n >= 3):
        return n - 2, n - 3
    else:
        return n - 2, n - 2

@lru_cache(None)
def f1(n):
    if (n == 0):
        return ’END’
    if (any(f2(x) == ’END’ for x in h1(n))):
        return ’WIN1’
    if (all(f2(x) == ’WIN1’ for x in h1(n))):
        return ’LOSE1’
    if (any(f2(x) == ’LOSE1’ for x in h1(n))):
        return ’WIN2’
    if (all(f2(x) == ’WIN1’ or f2(x) == ’WIN2’ for x in h1(n))):
        return ’LOSE2’
    if (any(f2(x) == ’LOSE2’ for x in h1(n))):
        return ’WIN3’
    if (all(f2(x) == ’WIN1’ or f2(x) == ’WIN2’ or \
            f2(x) == ’WIN3’ for x in h1(n))):
        return ’LOSE3’
    if (any(f2(x) == ’LOSE3’ for x in h1(n))):
        return ’WIN4’
    if (all(f2(x) == ’WIN1’ or f2(x) == ’WIN2’ \
            or f2(x) == ’WIN3’ or f2(x) == ’WIN4’ for x in h1(n))):
        return ’LOSE4’
    if (any(f2(x) == ’LOSE4’ for x in h1(n))):
        return ’WIN5’
                                                                                                     
                                                                                                     
    if (
            all(f2(x) == ’WIN1’ or f2(x) == ’WIN2’ or f2(x) == ’WIN3’ \
                or f2(x) == ’WIN4’ or f2(x) == ’WIN5’ for x in
                h1(n))):
        return ’LOSE5’
    if (any(f2(x) == ’LOSE5’ for x in h1(n))):
        return ’WIN6’

@lru_cache(None)
def f2(n):
    if (n < 2):
        return ’END’
    if (any(f1(x) == ’END’ for x in h2(n))):
        return ’WIN1’
    if (all(f1(x) == ’WIN1’ for x in h2(n))):
        return ’LOSE1’
    if (any(f1(x) == ’LOSE1’ for x in h2(n))):
        return ’WIN2’
    if (all(f1(x) == ’WIN1’ or f1(x) == ’WIN2’ for x in h2(n))):
        return ’LOSE2’
    if (any(f1(x) == ’LOSE2’ for x in h2(n))):
        return ’WIN3’
    if (all(f1(x) == ’WIN1’ or f1(x) == ’WIN2’ or \
            f1(x) == ’WIN3’ for x in h2(n))):
        return ’LOSE3’
    if (any(f1(x) == ’LOSE3’ for x in h2(n))):
        return ’WIN4’
    if (all(f1(x) == ’WIN1’ or f1(x) == ’WIN2’ or f1(x) == ’WIN3’ or \
            f1(x) == ’WIN4’ for x in h2(n))):
        return ’LOSE4’
    if (any(f1(x) == ’LOSE4’ for x in h2(n))):
        return ’WIN5’
    if (
            all(f1(x) == ’WIN1’ or f1(x) == ’WIN2’ or f1(x) == ’WIN3’ or \
                f1(x) == ’WIN4’ or f1(x) == ’WIN5’ for x in
                h2(n))):
        return ’LOSE5’
    if (any(f1(x) == ’LOSE5’ for x in h2(n))):
        return ’WIN6’
print(f1(20))

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 9#43477

Двое играют в следующую игру. Есть кучка, в которой $S$ камней. Первый каждым своим ходом берет $1$ или $10$ камней. Второй каждым своим ходом берёт $m$ или $n$ камней. Ходят по очереди, начинает первый. Тот, кто не может сделать ход, проигрывает

Известно, что $S = 100$ , $m = 1$ , $n = 10$ .

Кто побеждает при правильной игре? В ответе запишите номер игрока.

Показать ответ и решение

Ходы симметричны, а значит стратегия дополнения до 11. Первый выигрывает забрав 1 камень.

Ответ: 1

Ошибка.
Попробуйте повторить позже

Задача 10#30405

Для игры, описанной в задании $43,$ найдите такое максимальное значение $S$ , при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если такого значения нет, в ответ запишите $0.$

Показать ответ и решение

Решение руками

В данной задаче требуется найти максимальную позиции типа $LOSE2$ . Таких позиций две. Это позиции $S = 8$ и $S = 9.$ Максимальная из них это $S = 9.$

Решение программой

from functools import lru_cache


def moves(heap):
    return heap + 2, heap * 3


@lru_cache(None)
def game(heap):
    if heap >= 42:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(40, 0, -1):
    if game(s) == ’V2’:
        print(s)
        break

Ответ: 9

Ошибка.
Попробуйте повторить позже

Задача 11#30404

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

– Петя не может выиграть за один ход;

– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Из всех найденных значений запишите в ответе минимальное и максимальное в порядке возрастания без пробелов и знаков препинания.

Показать ответ и решение

Решение руками

Для начала найдём все позиции типа $WIN1$ . Это все позиции $S ≥ 14.$ Значит позиции $S = 13$ и $S = 12$ это позиции $LOSE1$ . В них можно прийти из позиций $S = 4,10,11.$

Решение программой

from functools import lru_cache


def moves(heap):
    return heap + 2, heap * 3


@lru_cache(None)
def game(heap):
    if heap >= 42:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 41):
    if game(s) == ’P2’:
        print(s)

Ответ: 411

Ошибка.
Попробуйте повторить позже

Задача 12#30403

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит лист бумаги, на котором написано двоичное число. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может приписать справа или слева к имеющемуся на листе числу двоичную запись любого из чисел вида $22n + 1$ , где $n$ — произвольное натуральное число, либо приписать справа и слева от имеющегося на листе числа его копию. Например, имея двоичное число $11001$ , за один ход можно получить путём копирования число $110011100111001$ или путём приписывания двоичной записи числа $5$ числа $10111001$ или $11001101$ .

Игра завершается в тот момент, когда количество единиц в двоичной записи числа на листе станет больше или равно $42$ . Победителем считается игрок, сделавший последний ход, т. е. первым получивший двоичное число, в записи которого использовано $42$ или более единиц.

В начальный момент единиц в числе было $S(1 ≤ S ≤ 41)$ .

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение $S$ , когда такая ситуация возможна.

Показать ответ и решение

Решение руками

Эта задача легко сводится к куче камней. За один ход можно добавить к куче $2$ камня, ведь любое число, имеющее вид $22n + 1$ имеет лишь $2$ единицы, либо умножить количество камней в куче на $3$ . Тогда очевидно, что первым ходом Петя утроил количество камней, после чего Ваня сделал то же самое. Значит нам подойдёт значение $S = 5.$

Решение программой

from functools import lru_cache


def moves(heap):
    return heap + 2, heap * 3


@lru_cache(None)
def game(heap):
    if heap >= 42:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif any(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’


for s in range(1, 41):
    if game(s) == ’V1’:
        print(s)
        break

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 13#30390

Для игры, описанной ранее, найдите такое значение $S,$ при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если такого значения нет, в ответ запишите $0.$

Показать ответ и решение

Решение руками

Рассмотрим $S = 22$ :

Решение программой

from functools import lru_cache

def moves(heap):
    a, b, c = heap
    m = []
    if a >= 1:
        m += [(a - 1, b, c)]
        if a > 1:
            m += [((a + 1) // 2, b, c)]
    if b >= 1:
        m += [(a, b - 1, c)]
        if b > 1:
            m += [(a, (b + 1) // 2, c)]
    if c >= 1:
        m += [(a, b, c - 1)]
        if c > 1:
            m += [(a, b, (c + 1) // 2)]
    return m

@lru_cache(None)
def game(heap):
    if sum(heap) <= 16:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

for s in range(10, 100):
    if game((3, 4, s)) == ’LOSE2’:
        print(s)
        break

Ответ: 22

Ошибка.
Попробуйте повторить позже

Задача 14#30389

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

Показать ответ и решение

Решение руками

Путём небольшого перебора находим $5$ значений $S : 38,37,23,21,20.$ В каждой из этих позиций есть ход, который приведёт Ваню в позицию $LOSE1$ , значит они нам подходят.

Решение программой

from functools import lru_cache

def moves(heap):
    a, b, c = heap
    m = []
    if a >= 1:
        m += [(a - 1, b, c)]
        if a > 1:
            m += [((a + 1) // 2, b, c)]
    if b >= 1:
        m += [(a, b - 1, c)]
        if b > 1:
            m += [(a, (b + 1) // 2, c)]
    if c >= 1:
        m += [(a, b, c - 1)]
        if c > 1:
            m += [(a, b, (c + 1) // 2)]
    return m

@lru_cache(None)
def game(heap):
    if sum(heap) <= 16:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

counter = 0
for s in range(10, 100):
    if game((3, 4, s)) == ’WIN2’:
        counter += 1
print(counter)

Ответ: 5

Ошибка.
Попробуйте повторить позже

Задача 15#30388

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат три кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из одной из куч один камень или уменьшить количество камней в куче в два раза (если количество камней в куче нечётно, остаётся на $1$ камень больше, чем убирается). При любом из ходов кол-во камней в одной из куч должно измениться. Например, пусть в первой куче будет $6$ камней, во второй куче $7$ камней, а в третьей $8$ камней; такую позицию мы будем обозначать $(6,7,8).$ За один ход из позиции $(6,7,8)$ можно получить любую из четырёх позиций: $(5,7,8),(6,6,8),(6,7,7),(3,7,8),(6,4,8),(6,7,4).$ Игра завершается в тот момент, когда суммарное количество камней в кучах становится не более $16.$

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет $16$ или менее камней. В начальный момент в первой куче было $3$ камня, во второй куче было $4$ камня, в третьей куче $S$ камней, $S > 9$ .

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите максимальное значение $S,$ когда такая ситуация возможна.

Показать ответ и решение

Решение руками

Наиболее неудачным для Пети ходом будет уменьшение наибольшей кучи в $2$ раза. Будем рассматривать этот случай. Тогда после этого Ваня уменьшает эту же кучу еще в $2$ раза и выигрывает.

$3+ 4 + S∕4 ≤ 16 ⇒ S∕4 ≤ 9 ⇒ S = 36.$

Решение программой

from functools import lru_cache

def moves(heap):
    a, b, c = heap
    m = []
    if a >= 1:
        m += [(a - 1, b, c)]
        if a > 1:
            m += [((a + 1) // 2, b, c)]
    if b >= 1:
        m += [(a, b - 1, c)]
        if b > 1:
            m += [(a, (b + 1) // 2, c)]
    if c >= 1:
        m += [(a, b, c - 1)]
        if c > 1:
            m += [(a, b, (c + 1) // 2)]
    return m

@lru_cache(None)
def game(heap):
    if sum(heap) <= 16:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif any(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’

for s in range(100, 9, -1):
    if game((3, 4, s)) == ’V1’:
        print(s)
        break

Ответ: 36

Ошибка.
Попробуйте повторить позже

Задача 16#24005

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

В ответе запишите числа в порядке возрастания без пробелов и знаков препинания.

Показать ответ и решение

Так как нас интересуют только единички, то очевидно, что при копировании числа у нас единичек становится в 3 раза больше. А при приписывании числа вида $22n−1$ получаем приписывание 1 единички.

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a * 3, b), (a, b * 3)


@lru_cache(None)
def f(h):
    if (sum(h) >= 100):
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if all(f(x) == ’P1’ for x in moves(h)):
        return ’V1’
    if any(f(x) == ’V1’ for x in moves(h)):
        return ’P2’
    if all(f(x) == ’P1’ or f(x) == ’P2’ for x in moves(h)):
        return ’V2’


for s in range(1, 92):
    h = 7, s
    if f(h) == ’V2’:
        print(s, end=’’)

Ответ: 2530

Ошибка.
Попробуйте повторить позже

Задача 17#24004

Укажите такое значение $S$ , при котором у Ани есть выигрышная стратегия, причём Аня не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Амина.

Если такого значения нет, в ответ запишите 0.

Показать ответ и решение

Так как нас интересуют только единички, то очевидно, что при копировании числа у нас единичек становится в 3 раза больше. А при приписывании числа вида $22n−1$ получаем приписывание 1 единички.

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a * 3, b), (a, b * 3)


@lru_cache(None)
def f(h):
    if (sum(h) >= 100):
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if all(f(x) == ’P1’ for x in moves(h)):
        return ’V1’
    if any(f(x) == ’V1’ for x in moves(h)):
        return ’P2’


for s in range(1, 92):
    h = 7, s
    if f(h) == ’P2’:
        print(s)
        break

Ответ: 26

Ошибка.
Попробуйте повторить позже

Задача 18#24003

Два игрока, Аня и Амина, играют в следующую игру. Перед игроками лежит лист бумаги, на котором написано два двоичных числа. Игроки ходят по очереди, первый ход делает Аня. За один ход игрок может приписать справа к любому имеющемуся на листе числу двоичную запись любого из чисел вида $22n−1$ , где $n$ — произвольное натуральное число, либо приписать слева и справа от имеющихся на листе чисел его копию. Например, имея двоичные числа $1010$ и $1101$ , за один ход можно получить путём копирования числа $101010101010$ или $110111011101$ или путём приписывания двоичной записи числа $8$ получить числа $10101000$ или $11011000$ .

Игра завершается в тот момент, когда суммарное количество единиц в двоичной записи чисел на листе станет больше или равно $100$ . Победителем считается игрок, сделавший последний ход, т. е. первым получивший суммарно в записи чисел $100$ или более единиц (Например $1001$ и $1000100$ — сумма 4).

В начальный момент единиц в первом числе было $7$ единиц, а во втором $S(1 ≤ S ≤ 92)$ .

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Известно, что Амина выиграла своим первым ходом после неудачного первого хода Ани. Укажите минимальное значение $S$ , когда такая ситуация возможна.

Показать ответ и решение

Так как нас интересуют только единички, то очевидно, что при копировании числа у нас единичек становится в 3 раза больше. А при приписывании числа вида $22n−1$ получаем приписывание 1 единички.

from functools import lru_cache


def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a * 3, b), (a, b * 3)


@lru_cache(None)
def f(h):
    if (sum(h) >= 100):
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’P1’
    if any(f(x) == ’P1’ for x in moves(h)):
        return ’V1’


for s in range(1, 92):
    h = 7, s
    if f(h) == ’V1’:
        print(s)
        break

Ответ: 11

Ошибка.
Попробуйте повторить позже

Задача 19#23816

Для игры, описанной ранее, найдите такое максимальное значение $S$ , при котором одновременно выполняются два условия:

– у Морти есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Рика;

– у Морти нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если такого значения нет, в ответ запишите 0.

Показать ответ и решение

from functools import lru_cache

def moves(heap):
    return heap + 2, heap * 3

@lru_cache(None)
def game(heap):
    if heap >= 42:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

for s in range(40, 0 ,-1):
    if game(s) == ’LOSE2’:
        print(s)
        break

Ответ: 9

Ошибка.
Попробуйте повторить позже

Задача 20#23815

Для игры, описанной в предыдущем задании, найдите такие значения $S$ , при которых у Рика есть выигрышная стратегия, причём одновременно выполняются два условия:

– Рик не может выиграть за один ход;

– Рик может выиграть своим вторым ходом независимо от того, как будет ходить Морти.

Из всех найденных значений запишите в ответе минимальное и максимальное в порядке возрастания без пробелов и знаков препинания.

Показать ответ и решение

from functools import lru_cache

def moves(heap):
    return heap + 2, heap * 3

@lru_cache(None)
def game(heap):
    if heap >= 42:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’

for s in range(1, 41):
    if game(s) == ’WIN2’:
        print(s)

Ответ: 411