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

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

Задача 1#49383

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два или три камня или увеличить количество камней в куче в четыре раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17, 18 или 60 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 83.

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

В начальный момент в куче было $S$ камней; $6 ≤ S ≤ 80$ .

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

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

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

def f(a,b):
 if a>=83: return b%2==0
 if b==0:return 0
 h = [f(a+2, b-1), f(a+3, b-1),f(a*4, b-1)]
 return any(h) if b%2!=0 else all(h)
print(min([a for a in range(6,81) if f(a,1)]))

Ответ: 21

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

Задача 2#87237

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

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

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

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

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

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

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

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

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

Ответ: В4

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

Задача 3#87232

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

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

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

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

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

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

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

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

Ответ: В313

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

Задача 4#87228

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

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

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

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

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

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

Ответ: П7

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

Задача 5#78635

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

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

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

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

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

from functools import lru_cache
lru_cache(None)
def f(a, b, c=0):
    if a + b >= 186:
        return 0
    if c > 5:
        return 1000
    t = [f(a+7, b, c+1), f(a+11, b, c+1), f(a*2, b, c+1), f(a, b*2, c+1), f(a, b+7, c+1),f(a, b+11, 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, 176):
    if f(10, i) == 1:
        a.append(i)
print(min(a))

Ответ: 88

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

Задача 6#78632

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

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

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

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

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

from functools import lru_cache
lru_cache(None)
def f(a, b, c=0):
    if a + b >= 205:
        return 0
    if c > 5:
        return 1000
    if a > b:
        t = [f(a, b + a, c + 1), f(a, b * 2, c + 1)]
    else:
        t = [f(a + b, b, c + 1), f(a * 2, b, c + 1)]
    n = [i for i in t if i <= 0]
    if n:
        return -max(n) + 1
    return -max(t)

for i in range(1, 197):
    if f(9, i) == 1:
        print(i)

Ответ: 98

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

Задача 7#78629

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

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

В начальный момент в первой куче было 15 камней, во второй куче – S камней; 1 $≤$ S $≤$ 152.

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

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

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

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

for i in range(1, 154):
    if f(15, i) == -1:
        print(i)

Ответ: 50

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

Задача 8#78626

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

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

В начальный момент в первой куче было 13 камней, во второй куче – S камней; 1 $≤$ S $≤$ 110.

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

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

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

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

for i in range(1, 111):
    if f(13, i) == -1:
        print(i)

Ответ: 55

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

Задача 9#78623

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

В начальный момент в куче было S камней, $1 ≤ S ≤ 46$ .

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

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

def f(a):
  if a >= 47:  #если камней в куче стало больше 47, то выход из функции
    return 0
  t = [f(a+2), f(a+5), f(a*2)]    #сформировали список ходов
  n = [i for i in t if i <= 0] #записываем отрицательные элементы из t
  if n:  #если n не пустой список
    return -max(n)+1 #получаем положительный выигрышный ход для Пети
  else:
    return -max(t) #получаем отрицательный выигрышный ход для Вани


for i in range(1,47):
    if f(i) == -1:
        print(i)

Ответ: 22

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

Задача 10#76991

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

Сколько существует пар (S; P), таких что Ваня выигрывает первым ходом при любой игре Пети?

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

from functools import lru_cache
@lru_cache(None)
def f(a, b):
    if a + b >= 50:
        return 0
    h = [f(a + 2, b), f(a * 3, b),f(a, b + 2),f(a, b * 3)]
    t = [i for i in h if i <= 0]
    if t:return -max(t)+1
    return -max(h)
c = 0
for i in range(1, 40):
    for j in range(1, 40):
        if f(i, j) == -1:
            print(i, j)
            c += 1
print(c)

Ответ: 18

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

Задача 11#76988

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

а) добавить в кучу 7 камней;

б) увеличить количество камней в куче в три раза;

в) добавить в кучу 5 камней.

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

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

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

from functools import lru_cache
@lru_cache(None)
def f(a):
    if a >= 65: return 0
    if a * 3 >= 109:
        n = [f(a + 5), f(a + 7)]
    else:
        n = [f(a + 5), f(a + 7), f(a * 3)] #список с возможными ходами
    t = [i for i in n if i <= 0] #список с отрицательными ходами
    if t:
        return -max(t) + 1 #выигрыш Пети
    else:
        return -max(n) #выигрыш Вани
for i in range(1, 40):
    if f(i) == 1:
        print(i)

Ответ: 22

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

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

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

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

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

Задача 14#76979

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

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

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

from functools import lru_cache
@lru_cache(None)
def f(a):
    if a >= 100: return 0
    if a * 4 > 120:
        n = [f(a + 3)]
    else:
        n = [f(a + 3), f(a * 4)] #список с возможными ходами
    t = [i for i in n if i <= 0] #список с отрицательными ходами
    if t:
        return -max(t) + 1 #выигрыш Пети
    else:
        return -max(n) #выигрыш Вани
for i in range(1, 61):
    if f(i) == 1:
        print(i)

Ответ: 25

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

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

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

Задача 17#72457

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

В начальный момент в куче было S камней, $1 ≤ S ≤ 63$ .

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

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

def f(a):
    if a >= 64:return 0
    m = [f(a+1),f(a*2)]
    n = [i for i in m if i <= 0]
    if n:return -max(n) + 1
    return -max(m)
for i in range(1,64):
    if f(i) == -1:
        print(i)

Ответ: 31

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

Задача 18#72442

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

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

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

from functools import lru_cache
@lru_cache(None)
def f(a,b):
    if a + b >= 122:return 0
    m = [f(a+1,b),f(a*3,b),f(a,b+1),f(a,b*3)]
    n = [i for i in m if i <= 0]
    if n:return -max(n)+1
    return -max(m)
for i in range(1,115):
    if f(7,i) == -1:
        print(i)

Ответ: 38

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

Задача 19#72431

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

В начальный момент в куче было S камней, $1 ≤ S ≤ 119$ .

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

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

from functools import  lru_cache
@lru_cache(None)
def f(a):
    if a >= 120:return 0
    m = [f(a+2),f(a+3),f(a*3)]
    n = [i for i in m if i <= 0]
    if n:return -max(n)+1
    return -max(m)
for i in range(1,120):
    if f(i) == -1:
        print(i)
        break

Ответ: 38

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

Задача 20#72420

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

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

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

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

Ответ: 0