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

Тема 19. Теория игр

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела теория игр

Решаем задачи

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

Задача 1#87237

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

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

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

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

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

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

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

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

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

Ответ: В4

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#87232

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

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

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

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

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

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

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

Ответ: В313

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

Задача 3#87228

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

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

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

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

Ответ: П7

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

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

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

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

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

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

Курсы

Всё необходимое для достижения цели

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

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

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

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

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущий раздел

Следующий раздел