19-21. Игры —Каталог задач по ЕГЭ - Информатика

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

Задача 1#38807

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

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

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

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

from functools import lru_cache


def moves(h):
    return h + 1, h + 2, h * 3


@lru_cache(None)
def f(h):
    if (h >= 50):
        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,50):
    if f(s) == ’V2’:
        print(s)

Ответ: 13

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

Задача 2#38806

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

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

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

from functools import lru_cache

def moves(h):
    return h + 1, h + 2, h * 3

@lru_cache(None)
def f(h):
    if (h >= 50):
        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, 50):
    if f(s) == ’P2’:
        print(s)

Ответ: 1415

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

Задача 3#38805

Два игрока, ДЮ и ТС, играют в следующую игру. Перед игроками лежит куча крабов. Игроки ходят по очереди, первый ход делает ДЮ. За один ход игрок может добавить в кучу одного краба или добавить в кучу два краба или увеличить количество крабов в куче в $3$ раза. Например, имея кучу из $10$ крабов, за один ход можно получить кучу из $11$ или $12$ или $30$ крабов. Чтобы делать ходы, у каждого игрока есть неограниченное количество крабов. Игра завершается в тот момент, когда количество крабов в куче становится не менее $50$ .

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет $50$ или более крабов. В начальный момент в куче было $S$ крабов, $1 ≤ S ≤ 49$ .

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

Найдите минимальное значение $S$ , при котором ТС выигрывает своим первым ходом при любой игре ДЮ.

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

from functools import lru_cache

def moves(h):
    return h + 1, h + 2, h * 3

@lru_cache(None)
def f(h):
    if (h >= 50):
        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’

for s in range(1,50):
    if f(s) == ’V1’:
        print(s)

Ответ: 16

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

Задача 4#60747

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

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

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

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

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

from functools import lru_cache


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


def pr(h):
    a, b = h
    return a*b


@lru_cache(None)
def f(h):
    if pr(h) >= 1250:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


for i in range(1, 312):
    h = 4, i
    if f(h) == ’LOSE2’:
        print(i, end=’’)

Ответ: 4860

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

Задача 5#60746

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

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

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

from functools import lru_cache


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


def pr(h):
    a, b = h
    return a*b


@lru_cache(None)
def f(h):
    if pr(h) >= 1250:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


for i in range(1, 312):
    h = 4, i
    if f(h) == ’WIN2’:
        print(i, end=’’)

Ответ: 124961

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

Задача 6#60745

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в пять раз. Например, пусть в одной куче будет $9$ камней, а в другой $10$ камней; такую позицию мы будем обозначать $(9,10)$ . За один ход из позиции $(9,10)$ можно получить любую из четырёх позиций: $(10,10),(9,11),(45,10),(9,50)$ . Игра завершается в тот момент, когда произведение количества камней в кучах становится не менее $1250$ .

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

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

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

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

from functools import lru_cache


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


def pr(h):
    a, b = h
    return a*b


@lru_cache(None)
def f(h):
    if pr(h) >= 1250:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


for i in range(1, 312):
    h = 4, i
    if f(h) == ’LOSE1’:
        print(i)

Ответ: 62

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

Задача 7#60744

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

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

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

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

from functools import lru_cache


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


def pr(h):
    a, b = h
    return a*b


@lru_cache(None)
def f(h):
    if pr(h) >= 1000:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


for i in range(1, 83):
    h = 12, i
    if f(h) == ’LOSE2’:
        print(i)

Ответ: 24

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

Задача 8#60743

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

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

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

from functools import lru_cache


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


def pr(h):
    a, b = h
    return a*b


@lru_cache(None)
def f(h):
    if pr(h) >= 1000:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


for i in range(1, 83):
    h = 12, i
    if f(h) == ’WIN2’:
        print(i, end=’’)

Ответ: 92526

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

Задача 9#60742

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче будет $9$ камней, а в другой $10$ камней; такую позицию мы будем обозначать $(9,10)$ . За один ход из позиции $(9,10)$ можно получить любую из четырёх позиций: $(10,10),(9,11),(27,10),(9,30)$ . Игра завершается в тот момент, когда произведение количества камней в кучах становится не менее $1000$ .

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой произведение камней в кучах будет $1000$ или более. В начальный момент в первой куче было $12$ камней, а во второй куче $S$ камней $1 ≤ S ≤ 83$ .

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

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

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

from functools import lru_cache


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


def pr(h):
    a, b = h
    return a*b


@lru_cache(None)
def f(h):
    if pr(h) >= 1000:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if all(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’
    if any(f(x) == ’LOSE1’ for x in moves(h)):
        return ’WIN2’
    if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)):
        return ’LOSE2’


for i in range(1, 83):
    h = 12, i
    if f(h) == ’LOSE1’:
        print(i)

Ответ: 27

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

Задача 10#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

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

Задача 11#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

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

Задача 12#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

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

Задача 13#56322

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

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

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

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

from functools import lru_cache
def moves(h):
    a = [h * 2]
    if (h + 1) % 2 == 0:
        a += [h + 1]
        a += [h + 3]
    return a
@lru_cache(None)
def f(h):
    if h >= 88:
        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 reversed(range(1, 88)):
    if f(s) == ’V2’:
        print(s)
        break

Ответ: 10

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

Задача 14#56321

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

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

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

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

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

from functools import lru_cache
def moves(h):
    a = [h * 2]
    if (h + 1) % 2 == 0:
        a += [h + 1]
        a += [h + 3]
    return a
@lru_cache(None)
def f(h):
    if h >= 88:
        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’
ans = []
for s in reversed(range(1, 88)):
    if f(s) == ’P2’:
        ans += [str(s)]
        if len(ans) == 2:
            break
print(ans[-1] + ans[-2])

Ответ: 3941

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

Задача 15#56320

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в $2$ раза, при этом после каждого хода в куче должно быть четное количество камней. Например, пусть в куче будет $6$ камней. Тогда за один ход можно получить кучу из $12$ камней. Игра завершается в тот момент, когда количество камней в куче становится не менее $88$ .

Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет $88$ или более камней. В начальный момент в куче было S камней, $1 ≤ S ≤ 87$ .

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

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

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

from functools import lru_cache
def moves(h):
    a = [h * 2]
    if (h + 1) % 2 == 0:
        a += [h + 1]
        a += [h + 3]
    return a
@lru_cache(None)
def f(h):
    if h >= 88:
        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’
for s in range(1, 88):
    if f(s) == ’V1’:
        print(s)
        break

Ответ: 22

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

Задача 16#46174

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

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

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

Ответ: 17

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

Задача 17#46173

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

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

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

Ответ: 201

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

Задача 18#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

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

Задача 19#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

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

Задача 20#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