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

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

Задача 1#19965

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

В начальный момент в первой куче было $20$ камней, во второй куче был $10$ каменей, в третьей — $S$ камней, $1 ≤ S ≤ 39$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

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

from functools import lru_cache

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

@lru_cache(None)
def f(h):
    if sum(h) >= 70:
        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) == "P2" or f(x) == "P1") for x in moves(h)):
        return "V2"

for s in range(39, 0, -1):
    h = 20, 10, s
    if f(h) == "P1":
        print(s, "P1")

Ответ: 20

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

Задача 2#19968

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

В начальный момент в первой куче было $9$ камней, во второй куче был $6$ каменей, в третьей было $8$ , в четвертой — $S$ камней, $1 ≤ S ≤ 39$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

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

from functools import lru_cache

def moves(h):
    a, b, c, d = h
    return (a + 2, b, c, d), (a, b + 2, c, d), (a, b, c + 2, d), (a, b, c, d + 2), (a * 3, b, c, d), (a, b * 3, c, d), (a, b, c * 3, d), (a, b, c, d * 3)

@lru_cache(None)
def f(h):
    if sum(h) >= 70:
        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) == "P2" or f(x) == "P1") for x in moves(h)):
        return "V2"

for s in range(39, 0, -1):
    h = 9, 6, 8, s
    if f(h) == "P1":
        print(s, "P1")

Ответ: 16

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

Задача 3#19974

Два игрока, Петя и Ваня, играют в следующую игру. Они передвигают жучка по координатной плоскости. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может либо сместить жучка с помощью вектора (1; 2), либо вектора (0, 1). Игра завершается в тот момент, когда жучок находится на расстоянии больше 20 от начала координат. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой жучок находится на расстоянии больше 20 от начала координат.

В начальный момент жучок был в точке с координатами $(10,S)$ , $1 ≤ S ≤ 17$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

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

from functools import lru_cache
from math import sqrt

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

@lru_cache(None)
def f(h):
    if sqrt(h[0] ** 2 + h[1] ** 2) > 20:
        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) == "P2" or f(x) == "P1") for x in moves(h)):
        return "V2"

for s in range(17, 0, -1):
    h = 10, s
    if f(h) == "P1":
        print(s, "P1")

Ответ: 15

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

Задача 4#19977

Два игрока, Петя и Ваня, играют в следующую игру. Они передвигают жучка по координатной плоскости. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может либо сместить жучка с помощью вектора (1; 2), либо (0, 1), либо (10, 1). Игра завершается в тот момент, когда жучок находится на расстоянии больше 30 от начала координат. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой жучок находится на расстоянии больше 30 от начала координат.

В начальный момент жучок был в точке с координатами $(15,S)$ , $1 ≤ S ≤ 25$ . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

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

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

from functools import lru_cache
from math import sqrt

def moves(h):
    a, b= h
    return (a + 1, b + 2), (a, b + 1), (a + 10, b + 1)

@lru_cache(None)
def f(h):
    if sqrt(h[0] ** 2 + h[1] ** 2) > 30:
        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) == "P2" or f(x) == "P1") for x in moves(h)):
        return "V2"

for s in range(25, 0, -1):
    h = 15, s
    if f(h) == "P1":
        print(s, "P1")

Ответ: 16

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

Задача 5#23814

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

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

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

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

Известно, что Морти выиграл своим первым ходом после неудачного первого хода Рика. Укажите минимальное значение $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 any(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’

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

Ответ: 5

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

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

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

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

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

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

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

Задача 9#37821

У Виктора и Петра есть одинаковые наборы карточек. В каждом наборе $50$ карточек, на которых написаны числа от $1$ до $99$ по одному разу каждое. Петр и Виктор по очереди выкладывают на стол свои карточки (Начинает, конечно Первый, то есть Петр). Выигрывает тот, после хода которого сумма чисел на всех карточках, лежащих на столе, будет делится на $132$ .

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

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

Очевидно, что после двух ходов сумма не превышает $198$ , значит, если Виктор выиграл своим вторым ходом, то итоговая сумма составила ровно $132$ . Далее заметим, что если Петр выложил любую карточку, на которой записано меньше $33$ — Виктор не может доложить свою карточку и получить сумму $132$ . Значит минимальное число это $33$ .

$132− 99 = 33$

Ответ: 33

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

Задача 10#43477

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

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

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

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

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

Ответ: 1

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

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

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

Задача 12#56407

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу три камня, добавить шесть камней или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который этот же игрок делал на предыдущем ходу. Повторять чужие ходы и свои более старые ходы разрешается. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее 68. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 68 или больше камней. В начальный момент в куче было S камней, 1 $≤$ S $≤$ 67.

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

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

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

def f(x, s1, s2):  # s1 - предыдущий ход, s2 - ПРЕДпредыдущий ход
    if x >= 68:
        return 0
    t = []
    # Делаем каждый ход, только если ПРЕДпредыдущий не совпадает с номером того, который собираемся сделать
    if s2 != 1:
        t += [f(x + 3, 1, s1)]  # Делаем первый ход - прошлый предыдущий становится ПРЕДпредыдущим
    if s2 != 2:
        t += [f(x + 6, 2, s1)]
    if s2 != 3:
        t += [f(x * 3, 3, s1)]

    n = [i for i in t if i <= 0]
    if n:
        return -max(n) + 1
    return -max(t)


for i in range(1, 67 + 1):
    if f(i, 0, 0) == 2:
        print(i)
        break

Ответ: 14

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

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

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

Задача 14#72476

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат три кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 110. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 110 или больше камней. В начальный момент в первой куче было 10 камней, во второй куче – 5 камней, а в третьей куче - S камней; $1 ≤ S ≤ 94$ .

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

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

from functools import lru_cache
@lru_cache(None)
def f(a,b,c):
    if a+b+c >= 110:return 0
    m = [f(a+1,b,c),f(a*2,b,c),f(a,b+1,c),f(a,b*2,c),f(a,b,c+1),f(a,b,c*2)]
    n = [i for i in m if i <= 0]
    if n:return -max(n) + 1
    return -max(m)
for i in range(1,95):
    if f(10,5,i) == -1:
        print(i)

Ответ: 47

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

Задача 15#72488

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками на координатной плоскости стоит фишка. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок увеличить координату X фишки на 2, или координату Y фишки на 3. Игра завершается в тот момент, расстояние от фишки до начала координат становится не менее 20. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой расстояние от фишки до начала координат становится не менее 20. В начальный момент координата X фишки была равна 5, координата $Y − 1 ≤ Y ≤ 19$ .

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

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

def f(x,y):
    if (x**2 + y**2)**0.5 >= 20:return 0
    m = [f(x+2,y),f(x,y+3)]
    n = [i for i in m if i <= 0]
    if n:return -max(n) + 1
    return -max(m)
for y in range(1,20):
    if f(5,y) == -1:
        print(y)

Ответ: 16

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

Задача 16#76982

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит три кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч 16 или 32 камня или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда в сумме в кучах будет не менее 150 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в кучах было (6, 2S, 3S) камней, $1 ≤ S ≤ 66$ .

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

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

from functools import lru_cache
lru_cache(None)
def f(a, b, d, c = 0):
    if a + b + d >= 150:
        return 0
    if c > 3:
        return 1000000
    t = [f(a*2, b, d,  c+1),f(a+16, b, d, c+1),f(a+32, b, d, c+1),
    f(a, b*2, d,  c+1),f(a, b+16, d, c+1),f(a, b+32, d, c+1),
    f(a, b, d*2,  c+1),f(a, b, d+16, c+1),f(a, b, d+32, c+1)]
    n = [i for i in t if i <= 0]
    if n:
        return -max(n) + 1
    return -max(t)

a = []
for i in range(1,67):
    if f(6, 2*i, 3*i) == 1:
        a.append(i)
print(min(a))

Ответ: 18

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

Задача 17#76985

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит три кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч сумму камней двух других куч или увеличить количество камней в куче в три раза. Игра завершается в тот момент, когда в сумме в кучах будет не менее 300 камней. Победителем считается игрок, сделавший последний ход. В начальный момент в кучах было (45, S, S+25) камней, $1 ≤ S ≤ 100$ .

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

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

from functools import lru_cache
lru_cache(None)
def f(a, b, d, c = 0):
    if a + b + d >= 300:
        return 0
    if c > 4:
        return 1000000
    t = [f(a*3, b, d,  c+1),f(a+b+d, b, d, c+1),f(a, b*3, d, c+1),
    f(a, b + a + d, d,  c+1),f(a, b, d*3, c+1),f(a, b, d+a+b, c+1)]
    n = [i for i in t if i <= 0]
    if n:
        return -max(n) + 1
    return -max(t)

a = []
for i in range(1,101):
    if f(45, i, i + 25) == 1:
        a.append(i)
print(len(a))

Ответ: 56

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

Задача 18#87228

Два игрока, Петя и Ваня, играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого. Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Первый ход делает Петя. Выигрывает тот, кто первый составит слово из заданного набора.

Определите, у кого из игроков есть выигрышная стратегия для набора слов ГЭНДАЛЬФЧЕРНЫЙ, ГЭНДАЛЬФСЕРЫЙ и ГЭНДАЛЬФБЕЛЫЙ.

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

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

Петя ходит первый, а значит он ставит все нечетные буквы, в то время как Ваня ставит четные. Значит Петя победит, если составит слово из нечетного количества букв, а Ваня - из четного.

Все три слова начинаются одинаково, поэтому при составлении ГЭНДАЛЬФ у игроков не будет вариантов, какую букву ставить. Буква после Ф по счету является девятой, значит её ставит Петя. Он может поставить либо Ч, либо С, либо Б. Если он поставит Ч, то составит слово ГЕНДАЛЬФЧЕРНЫЙ, которое имеет четное количество букв, что сделает победителем Ваню. А вот если он поставит С или Б, то победителем уже окажется сам Петя, так как остальные два слова имеют нечетную длину. Количество ходов же, которое потребуется сделать Пете, будет являться количеством букв на нечетных местах, их всего 7.

Ответ: П7

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

Задача 19#87232

Два игрока, Петя и Ваня, играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого. Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Причём нельзя ставить две гласные подряд. Первый ход делает Ваня. Выигрывает тот, кто первый составит слово из заданного набора.

Определите, у кого из игроков есть выигрышная стратегия для набора слов ГОРОДА...ГОРОДА, ЗВУКИ...ЗВУКИ. В первом слове 123 раза повторяется последовательность букв ГОРОДА, во втором 125 раз повторяется последовательность букв ЗВУКИ.

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

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

Ваня ходит первый, а значит он ставит все нечетные буквы, в то время как Петя ставит четные. Значит Ваня победит, если составит слово из нечетного количества букв, а Петя - из четного.

Ваня ходит первый, а значит именно он определяет, какое слово из двух будут составлять игроки. Слово ГОРОДА...ГОРОДА имеет длину $6⋅123$ , а значит оно состоит из четного количества букв, из чего делаем вывод, что победит Петя.

Слово ЗВУКИ...ЗВУКИ имеет длину $5 ⋅125$ , а значит оно состоит из нечетного количество букв, из чего делаем вывод, что победит Ваня.

Значит Ваня выберет именно второе слово и сделает 313 ходов (на 1 больше, чем целая часть половины длины слова).

Ответ: В313

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

Задача 20#87237

Два игрока, Петя и Ваня, играют в следующую игру. Задан некоторый набор символьных цепочек («слов»), в котором ни одно слово не является началом другого. Игра начинается с пустой строки, в конец которой игроки по очереди дописывают буквы, по одной букве за ход так, чтобы полученная цепочка на каждом шаге была началом одного из заданных слов. Причём нельзя ставить две гласные подряд. Первый ход делает Петя. Выигрывает тот, кто первый составит слово из заданного набора.

Определите, у кого из игроков есть выигрышная стратегия для набора слов ЧЕРЕПИЦА и ЧЕРЕПАХАХАМ.

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

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

Петя ходит первый, а значит он ставит все нечетные буквы, в то время как Ваня ставит четные. Значит Петя победит, если составит слово из нечетного количества букв, а Ваня - из четного.

Все три слова начинаются одинаково, поэтому при составлении ЧЕРЕП у игроков не будет вариантов, какую букву ставить. Буква после П по счету является шестой, значит её ставит Ваня. Он может поставить либо И, либо А.

Если он поставит И, то составит слово ЧЕРЕПИЦА, которое имеет четное количество букв, что сделает победителем Ваню.

А вот если он поставит А, то победителем уже окажется Петя, так как слово ЧЕРЕПАХАХАМ имеет нечетную длину.

Количество ходов же, которое потребуется сделать Ване, будет являться количеством букв на четных местах, их всего 4.

Ответ: В4

19.07 Прочие прототипы