Номер 19-21. ЕГЭ по информатике

Экселька_для_решения_ЛЮБЫХ_ИГР_на_2_кучи_ruiv Скачать

Задача №1 (8192)

(ЕГКР-2025) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два или пять камней либо увеличить количество камней в куче в два раза. У каждого игрока есть неограниченное количество камней, чтобы делать ходы. Игра завершается в тот момент, когда количество камней в куче становится не менее 128. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, состоящую из 128 или более камней. В начальный момент в куче было S камней; 1 ≤ S ≤ 127. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
  Вопрос 1. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
  Вопрос 2. Найдите два наименьших значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
  Вопрос 3. Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение

Вопрос 1 (19е задание).

Нарисуем схему игры. Ваня выигрывает своим первым ходом (это второй ход игры) независимо от того, как ходит Петя:

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

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

Задаём рекурсивную функцию g(s, p), где s – текущее количество камней в куче; p – номер хода с начала игры (первый ход Пети – p = 0):

def g(s,p):

Запишем условия окончания игры – она заканчивается, если в куче оказывается 128 и более камней, при этом нас интересует только тот случай, если игра завершилась ровно на втором ходу (p == 2):

if s>=128: return p==2

Ограничиваем глубину рекурсии – нас не интересуют партии длиннее двух ходов:

if p>2: return 0

Задаем список возможных ходов в соответствии с условием задачи – игрок может добавить 2 камня; добавить 5 камней; умножить количество камней в куче на 2. После каждого хода увеличивается счётчик ходов p:

moves = [g(s+2,p+1),g(s+5,p+1),g(s*2,p+1)]

Описываем логику игры. Игроки ходят по очереди: нечётный ход – Петя, чётный ход – Ваня (счёт начинается с 0). Если (p + 1) % 2 == 0, значит ход Вани, ему достаточно одного выигрышного варианта, то есть хотя бы один ход должен приводить к нужной победе:

if (p+1)%2==0: return any(moves)

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

else: return all(moves)

Для получения ответа, перебираем все возможные начальные значения S, при начальном состоянии p = 0 (ходов еще не было) и выводим на экран подходящие значения:

print(19,[s for s in range(1,128) if g(s,0)==1])

Запускаем, получаем ответ на первый вопрос задачи:

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

Можно получить визуализацию работы этой функции с помощью приложения https://recursion.vercel.app/. Например, для S = 62, дерево будет выглядеть так:

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

Вопрос 2 (20е задание). Нарисуем схему игры:

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

Как и раньше, используем рекурсивную функцию g(s, p), которая перебирает все возможные варианты игры, ищет только те, где победа наступает строго на третьем ходу, учитывает стратегию игроков: Петя — достаточно одного удачного хода, Ваня — все его ходы должны сохранять возможность победы Пети.

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

if s>=128: return p==3

Изменяем глубину рекурсии, нас не интересуют игры длиннее трех ходов:

if p>3: return 0

Теперь нам нужно, чтобы у Пети был хотя бы один выигрышный ход, и при этом все ходы Вани сохраняли возможность победы Пети. (p + 1) % 2 != 0, ходит Петя, функция возвращает any (moves). Иначе ходит Ваня, функция возвращает all(moves):

if (p+1)%2!=0: return any(moves)

else: return all(moves)

print(20,[s for s in range(1,128) if g(s,0)==1])

Запускаем, получаем ответ на второй вопрос задачи:

Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня, если в начальный момент времени в куче будет 31, 57, 58, 60, 61 камень. Наименьшее значение – 31, наибольшее – 61, эти числа – ответ на второй вопрос задачи.

Вопрос 3 (21е задание). Нарисуем схему игры:

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

Как и раньше, используем рекурсивную функцию g(s, p), которая перебирает все возможные варианты игры, ищет только те, где победа наступает строго на 2-м или 4-м ходу, учитывает стратегию игроков: для Вани – достаточно одного удачного хода, для Пети – все его ходы должны сохранять возможность победы Вани.

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

if s>=128: return p==2 or p==4

Изменяем глубину рекурсии, нас не интересуют игры длиннее четырех ходов:

if p>4: return 0

Теперь нам нужно, чтобы у Вани был хотя бы один выигрышный ход, и при этом все ходы Пети сохраняли возможность победы Вани. Игроки ходят по очереди: нечётный ход – Петя, чётный ход – Ваня (счёт начинается с 0). Если (p + 1) % 2 == 0, значит ход Вани, ему достаточно одного выигрышного варианта, то есть хотя бы один ход должен приводить к нужной победе. По условию задачи при любом ходе Пети должен выиграть Ваня, значит, во всех ходах Пети должна сохраняться возможности выигрыша Вани:

if (p+1)%2==0: return any(moves)

else: return all(moves)

print(21,[s for s in range(1,128) if g(s,0)==1])

Запускаем, получаем ответ на третий вопрос задачи:

Ваня может выиграть своим первым или вторым ходом независимо от того, как будет ходить Петя, если в начальный момент времени в куче будет 55, 56, 59, 62, 63 камня. Видим, что числа 62 и 63 совпадают с ответом на 19е задание, при таком начальном количестве камней в куче Ваня выигрывает своим первым ходом. Для ответа на 21е задания эти числа не подходят. Указываем в ответе минимальное из оставшихся полученных чисел, это число 21.

Текст программы полностью:

def g(s,p):

if s>=128: return p==2

if p>2: return 0

moves = [g(s+2,p+1),g(s+5,p+1),g(s*2,p+1)]

if (p+1)%2==0: return any(moves) #g(..) or g(..) or g(..)

else: return all(moves) #g(..) and g(..) ang g(..)

print(19,[s for s in range(1,128) if g(s,0)==1])

def g(s,p):

if s>=128: return p==3

if p>3: return 0

moves = [g(s+2,p+1),g(s+5,p+1),g(s*2,p+1)]

if (p+1)%2!=0: return any(moves)

else: return all(moves)

print(20,[s for s in range(1,128) if g(s,0)==1])

def g(s,p):

if s>=128: return p==2 or p==4

if p>4: return 0

moves = [g(s+2,p+1),g(s+5,p+1),g(s*2,p+1)]

if (p+1)%2==0: return any(moves)

else: return all(moves)

print(21,[s for s in range(1,128) if g(s,0)==1])

Ответ:

1) 62
2) 31 57
3) 55

Задача №2 (7938)

(ЕГКР-2024) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– добавить в кучу 3 камня;
– добавить в кучу 6 камней;
– увеличить количество камней в куче в 3 раза. Например, из кучи в 20 камней за один ход можно получить кучу из 23, 26 или 60 камней. Игра завершается, когда количество камней в куче становится не менее 132. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 132 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 131. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
  Вопрос 1. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
  Вопрос 2. Найдите два наименьших значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
  Вопрос 3. Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение

Задание 19.

Задаём рекурсивную функцию g(s, p), где s – текущее количество камней в куче; p – номер хода с начала игры (первый ход Пети – p = 0). Запишем условия окончания игры – она заканчивается, если в куче оказывается 132 и более камней, при этом нас интересует только тот случай, если игра завершилась ровно на втором ходу (p == 2). Нас не интересуют партии длиннее двух ходов, поэтому функция будет возвращать 0 если p>2. Задаем список h возможных ходов в соответствии с условием задачи – игрок может добавить 3 камня; добавить 6 камней; умножить количество камней в куче на 3. После каждого хода увеличивается счётчик ходов p.

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

def g(s,p):

if s>=132: return p==2

if p>2: return 0

h = [g(s+3,p+1),g(s+6,p+1),g(s*3,p+1)]

if (p+1)%2==0: return any(h)

else: return all(h)

Для получения ответа, перебираем все возможные начальные значения S, при начальном состоянии p = 0 (ходов еще не было) и добавляем их в список v1, чтобы в дальнейшем исключать из ответа на третий вопрос задачи, выводим на экран подходящие значения:

v1 = [s for s in range(1,132) if g(s,0)]

print(19,[s for s in range(1,132) if g(s,0)])

Запускаем, получаем ответ на первый вопрос задачи:

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

Задание 20.

Задаём рекурсивную функцию g(s, p). Запишем условия окончания игры – нас интересует только тот случай, если игра завершилась ровно на третьем ходу (p == 3). Задаем список h возможных ходов в соответствии с условием задачи.

Описываем логику игры. Теперь нам нужно, чтобы у Пети был хотя бы один выигрышный ход, и при этом все ходы Вани сохраняли возможность победы Пети. (p + 1) % 2 != 0, ходит Петя, функция возвращает any (h). Иначе ходит Ваня, функция возвращает all(h):

def g(s,p):

if s>=132: return p==3

if p>3: return 0

h = [g(s+3,p+1),g(s+6,p+1),g(s*3,p+1)]

if (p+1)%2!=0: return any(h)

else: return all(h)

print(20,[s for s in range(1,132) if g(s,0)])

Запускаем, получаем ответ на второй вопрос задачи:

Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня, если в начальный момент времени в куче будет 14, 35, 36, 37, 38, 39 или 40 камней. Наименьшее значение – 14, наибольшее – 35, эти числа – ответ на второй вопрос задачи.

Задание 21.

Как и раньше, используем рекурсивную функцию g(s, p), которая перебирает все возможные варианты игры, ищет только те, где победа наступает на втором или четвертом ходу, учитывает стратегию игроков: для Вани – достаточно одного удачного хода, для Пети – все его ходы должны сохранять возможность победы Вани.

if s>=132: return p==2 or p==4

Изменяем глубину рекурсии, нас не интересуют игры длиннее четырех ходов:

if p>4: return 0

if (p+1)%2==0: return any(h)

else: return all(h)

Для получения ответа, перебираем все возможные начальные значения S, при начальном состоянии p = 0 (ходов еще не было) и выводим на экран подходящие значения. При этом исключаем из вывода значения S, при которых Ваня выигрывает своим первым ходом:

print(21,[s for s in range(1,132) if s not in v1 and g(s,0)])

Запускаем, получаем ответ на третий вопрос задачи:

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

Текст программы полностью:

def g(s,p):

if s>=132: return p==2

if p>2: return 0

h = [g(s+3,p+1),g(s+6,p+1),g(s*3,p+1)]

if (p+1)%2==0: return any(h)

else: return all(h)

v1 = [s for s in range(1,132) if g(s,0)]

print(19,[s for s in range(1,132) if g(s,0)])

def g(s,p):

if s>=132: return p==3

if p>3: return 0

h = [g(s+3,p+1),g(s+6,p+1),g(s*3,p+1)]

if (p+1)%2!=0: return any(h)

else: return all(h)

print(20,[s for s in range(1,132) if g(s,0)])

def g(s,p):

if s>=132: return p==2 or p==4

if p>4: return 0

h = [g(s+3,p+1),g(s+6,p+1),g(s*3,p+1)]

if (p+1)%2==0: return any(h)

else: return all(h)

print(21,[s for s in range(1,132) if s not in v1 and g(s,0)])

Ответ:

1) 41
2) 14 35
3) 32

Задача №3 (8665)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 3 камня;
– убрать из кучи 5 камней;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до меньшего).
Игра завершается, когда количество камней в куче становится не более 30. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 30 или менее камней. В начальный момент в куче было S камней, S ≥ 31. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
  Вопрос 1. Укажите минимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
  Вопрос 2. Найдите два наименьших значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
  Вопрос 3. Найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение

Задание 19.

Задаём рекурсивную функцию g(s, p), где s – текущее количество камней в куче; p – номер хода с начала игры (первый ход Пети – p = 0). Запишем условия окончания игры – она заканчивается, если в куче оказывается 30 и менее камней, при этом нас интересует только тот случай, если игра завершилась ровно на втором ходу (p == 2). Нас не интересуют партии длиннее двух ходов, поэтому функция будет возвращать 0 если p>2, объединим эти условия, запишем в одну строку:

def g(s,p):

if s<=30 or p>2: return p==2

Задаем список h возможных ходов в соответствии с условием задачи – игрок может убрать из кучи 3 камня; убрать из кучи 5 камней; уменьшить количество камней в куче в 4 раза (выполнить целочисленное деление количества камней в куче на 4). После каждого хода увеличивается счётчик ходов p.

h = [g(s-3,p+1),g(s-5,p+1),g(s//4,p+1)]

Описываем логику игры. Сократим запись до одной строки. Игроки ходят по очереди: нечётный ход – Петя, чётный ход – Ваня (счёт начинается с 0). Если (p + 1) % 2 == 0, значит ход Вани, ему достаточно одного выигрышного варианта, то есть хотя бы один ход должен приводить к нужной победе. По условию задачи при любом ходе Пети должен выиграть Ваня, значит, во всех ходах Пети должна сохраняться возможности выигрыша Вани:

return any(h) if (p+1)%2==0 else all(h)

print(19,[s for s in range(31,1000) if g(s,0)])

Запускаем, получаем результат:

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

Задание 20.

Задаём рекурсивную функцию g(s, p). Запишем условия окончания игры – теперь нас интересует только тот случай, если игра завершилась ровно на третьем ходу (p == 3).

Задаем список h возможных ходов в соответствии с условием.

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

def g(s,p):

if s<=30 or p>3: return p==3

h = [g(s-3,p+1),g(s-5,p+1),g(s//4,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,[s for s in range(31,1000) if g(s,0)])

Запускаем, получаем ответ на второй вопрос задачи:

Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня, если в начальный момент времени в куче будет различное число камней. Два наименьших значения – 127 и 128, эти числа – ответ на второй вопрос задачи.

Задание 21.

Задаём рекурсивную функцию g(s, p). Запишем условия окончания игры – теперь нас интересует только тот случай, если игра завершилась ровно на втором или четвертом ходу.

Задаем список h возможных ходов в соответствии с условием задачи .

Описываем логику игры. Теперь нам нужно, чтобы у Вани был хотя бы один выигрышный ход, и при этом все ходы Пети сохраняли возможность победы Вани. Игроки ходят по очереди: нечётный ход – Петя, чётный ход – Ваня (счёт начинается с 0). Для получения ответа, перебираем все возможные начальные значения S, при начальном состоянии p = 0 (ходов еще не было) и выводим на экран подходящие значения:

def g(s,p):

if s<=30 or p>4: return p==2 or p==4

h = [g(s-3,p+1),g(s-5,p+1),g(s//4,p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(21,[s for s in range(31,1000) if g(s,0)])

Запускаем, получаем ответ на третий вопрос задачи:

Ваня может выиграть своим первым или вторым ходом независимо от того, как будет ходить Петя, если в начальный момент времени в куче будет 124-126 или 123-134 или 508-510 камней. Видим, что числа 124-126 совпадают с ответом на 19е задание, при таком начальном количестве камней в куче Ваня выигрывает своим первым ходом. Для ответа на 21е задания эти числа не подходят. Указываем в ответе минимальное из оставшихся полученных чисел, это число 132.

Текст программы полностью:

def g(s,p):

if s<=30 or p>2: return p==2

h = [g(s-3,p+1),g(s-5,p+1),g(s//4,p+1)]

return any(h) if (p+1)%2==0 else all(h)

#if (p+1)%2==0: return any(h)

#else: return all(h)

print(19,[s for s in range(31,1000) if g(s,0)])

def g(s,p):

if s<=30 or p>3: return p==3

h = [g(s-3,p+1),g(s-5,p+1),g(s//4,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,[s for s in range(31,1000) if g(s,0)])

def g(s,p):

if s<=30 or p>4: return p==2 or p==4

h = [g(s-3,p+1),g(s-5,p+1),g(s//4,p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(21,[s for s in range(31,1000) if g(s,0)])

Ответ:

1) 124
2) 127 128
3) 132

Задача №5 (2419)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч три камня или увеличить количество камней в куче в два раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 62. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 62 или больше камней.
В начальный момент в первой куче было 7 камней, во второй куче – S камней, 1 ≤ S ≤ 54. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
  Вопрос 1. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно.
  Вопрос 2. Укажите минимальное значение S, при котором у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
  Вопрос 3. Найдите два значения S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Найденные значения запишите в ответе в порядке возрастания.

Решение

Задача отличается от предыдущих, во-первых, наличием двух куч камней, рекурсивная функция будет принимать три переменные – количество камней в каждой из куч и номер хода, а во-вторых, в 19м задании Ваня выигрывает после неудачного хода Пети, то есть нет необходимости проверять, мог ли Петя выиграть своим первым ходом, этого не требуется по условию.

Задание 19.

Задаём рекурсивную функцию g(a,b,p), где a, b – текущее количество камней в каждой из двух куч; p – номер хода с начала игры (первый ход Пети – p = 0). Запишем условия окончания игры – она заканчивается, если суммарное количество камней в кучах оказывается не менее 62, при этом нас интересует только тот случай, если игра завершилась ровно на втором ходу (p == 2).

Задаем список h возможных ходов в соответствии с условием задачи – игрок может добавить в одну из куч три камня или увеличить количество камней в куче в два раза. После каждого хода увеличивается счётчик ходов p.

Для получения ответа, перебираем все возможные начальные значения S от 1 до 54, при начальном состоянии p = 0 (ходов еще не было), количестве камней в первой куче, равном 7, и выводим на экран подходящие значения:

def g(a,b,p):

if a+b>=62 or p>2: return p==2

h = [g(a+3,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h)

print(19,[s for s in range(1,55) if g(7,s,0)])

Запускаем, получаем результат:

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

Задание 20.

Задаём рекурсивную функцию g(a,b,p), запишем условия окончания игры – теперь нас интересует только тот случай, если игра завершилась ровно на третьем ходу (p == 3).

Задаем список h возможных ходов в соответствии с условием задачи.

def g(a,b,p):

if a+b>=62 or p>3: return p==3

h = [g(a+3,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,[s for s in range(1,55) if g(7,s,0)])

Запускаем, получаем ответ на второй вопрос задачи:

Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня, если в начальный момент времени в куче будет 13, 23, 24 или 25 камней. Наименьшее значение – 13, это ответ на второй вопрос задачи.

Задание 21.

Задаём рекурсивную функцию g(a,b,p). Запишем условия окончания игры, теперь нас интересует только тот случай, если игра завершилась на втором или четвертом ходе (p == 2 or p==4).

Задаем список h возможных ходов в соответствии с условием задачи.

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

def g(a,b,p):

if a+b>=62 or p>4: return p==2 or p==4

h = [g(a+3,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(21,[s for s in range(1,55) if g(7,s,0)])

Запускаем, получаем ответ на третий вопрос задачи:

Ваня может выиграть своим первым или вторым ходом независимо от того, как будет ходить Петя, если в начальный момент времени в куче будет 20, 22, 26 или 27 камней. Мы не можем сказать, при каком начальном количестве камней Ваня выиграет своим первом ходом, потому что не узнавали этого раньше. Поэтому временно уберем из программы условие “or p==4”, запустим её и узнаем начальное количество камней для выигрыша Вани первым ходом. Запустим, получим результат:

Значит, если в начальный момент в куче было 26 или 27 камней, Ваня имеет выигрышную стратегию в один ход, эти числа не могут быть ответом на 21 задание. Поэтому указываем в ответе оставшиеся два числа – 20 и 22.

Текст программы полностью:

def g(a,b,p):

if a+b>=62 or p>2: return p==2

h = [g(a+3,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h)

print(19,[s for s in range(1,55) if g(7,s,0)])

def g(a,b,p):

if a+b>=62 or p>3: return p==3

h = [g(a+3,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,[s for s in range(1,55) if g(7,s,0)])

def g(a,b,p):

if a+b>=62 or p>4: return p==2 or p==4

h = [g(a+3,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(21,[s for s in range(1,55) if g(7,s,0)])

Ответ:

1) 14
2) 13
3) 20 22

Задача №6 (2410)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч два камня или увеличить количество камней в куче в два раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 79. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 79 или больше камней.
В начальный момент в первой куче было 9 камней, во второй куче – S камней, 1 ≤ S ≤ 69. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
  Вопрос 1. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно.
  Вопрос 2. Укажите минимальное значение S, при котором у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
  Вопрос 3. Найдите два значения S, при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Найденные значения запишите в ответе в порядке возрастания.

Решение

Задание 19.

Задаём рекурсивную функцию g(a,b,p), где a, b – текущее количество камней в каждой из двух куч; p – номер хода с начала игры (первый ход Пети – p = 0). Запишем условия окончания игры – она заканчивается, если суммарное количество камней в кучах оказывается не менее 79, при этом нас интересует только тот случай, если игра завершилась ровно на втором ходу (p == 2).

Задаем список h возможных ходов в соответствии с условием задачи – ход игрок может добавить в одну из куч два камня или увеличить количество камней в куче в два раза. После каждого хода увеличивается счётчик ходов p.

Для получения ответа, перебираем все возможные начальные значения S от 1 до 69, при начальном состоянии p = 0 (ходов еще не было), количестве камней в первой куче, равном 9, и выводим на экран подходящие значения:

def g(a,b,p):

if a+b>=79 or p>2: return p==2

h = [g(a+2,b,p+1),g(a,b+2,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h)

print(19,[s for s in range(1,70) if g(9,s,0)])

Запускаем, получаем результат:

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

Задание 20.

Задаём рекурсивную функцию g(a,b,p). Запишем условия окончания игры, теперь нас интересует только тот случай, если игра завершилась ровно на третьем ходу (p == 3).

Задаем список h возможных ходов в соответствии с условием задачи.

def g(a,b,p):

if a+b>=79 or p>3: return p==3

h = [g(a+2,b,p+1),g(a,b+2,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,[s for s in range(1,70) if g(9,s,0)])

Запускаем, получаем ответ на второй вопрос задачи:

Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня, если в начальный момент времени в куче будет 17, 30, 32 или 33 камня. Наименьшее значение – 17, это ответ на второй вопрос задачи.

Задание 21.

Задаём рекурсивную функцию g(a,b,p). Запишем условия окончания игры – теперь нас интересует только тот случай, если игра завершилась на втором или четвертом ходе (p == 2 or p==4).

Задаем список h возможных ходов в соответствии с условием задачи.

def g(a,b,p):

if a+b>=79 or p>4: return p==2 or p==4

h = [g(a+2,b,p+1),g(a,b+2,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(21,[s for s in range(1,70) if g(9,s,0)])

Запускаем, получаем ответ на третий вопрос задачи:

Ваня может выиграть своим первым или вторым ходом независимо от того, как будет ходить Петя, если в начальный момент времени в куче будет 28, 31 или 34 камня. Мы не можем сказать, при каком начальном количестве камней Ваня выиграет своим первом ходом, потому что не узнавали этого раньше. Поэтому временно уберем из программы условие “or p==4”, запустим её и узнаем начальное количество камней для выигрыша Вани первым ходом. Запустим, получим результат:

Значит, если в начальный момент в куче было 34 камня, Ваня имеет выигрышную стратегию в один ход, это число не может быть ответом на 21 задание. Поэтому указываем в ответе оставшиеся два числа – 28 и 31.

Текст программы полностью:

def g(a,b,p):

if a+b>=79 or p>2: return p==2

h = [g(a+2,b,p+1),g(a,b+2,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h)

print(19,[s for s in range(1,70) if g(9,s,0)])

def g(a,b,p):

if a+b>=79 or p>3: return p==3

h = [g(a+2,b,p+1),g(a,b+2,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,[s for s in range(1,70) if g(9,s,0)])

def g(a,b,p):

if a+b>=79 or p>4: return p==2 or p==4

h = [g(a+2,b,p+1),g(a,b+2,p+1),g(a*2,b,p+1),g(a,b*2,p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(21,[s for s in range(1,70) if g(9,s,0)])

Ответ:

1) 18
2) 17
3) 28 31

Универсальная функция

Код, который мы писали, для решения задач, можно оптимизировать и упросить. Разберем решение уже разобранной задачи номер 3 с одной кучей камней.

Текст программы:

def g(s,p):

if s<=30 or p>2: return p==2

h = [g(s-3,p+1),g(s-5,p+1),g(s//4,p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(19,[s for s in range(31,1000) if g(s,0)])

def g(s,p):

if s<=30 or p>3: return p==3

h = [g(s-3,p+1),g(s-5,p+1),g(s//4,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,[s for s in range(31,1000) if g(s,0)])

def g(s,p):

if s<=30 or p>4: return p==2 or p==4

h = [g(s-3,p+1),g(s-5,p+1),g(s//4,p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(21,[s for s in range(31,1000) if g(s,0)])

Легко можно заметить, что функции для поиска ответов на все три вопроса различаются только в части номера конечного хода и использовании функций any и all для получения результата функции. Следовательно, можно написать одну универсальную функцию, добавив еще один параметр – «end», за сколько ходов должна закончиться игра. Используем этот параметр вместо числовых значений, соответствующих номеру хода, для выхода из функции:

def g(s, p, end):

if s <= 30 or p > end:

return p == end

h = [g(s-3, p+1, end), g(s-5, p+1, end), g(s//4, p+1, end)]

Теперь проанализируем использование функций any() и all() для победы разных игроков. Так, если победа должна произойти за чётное число ходов, то необходимо, чтобы функция возвращала истину во всех ходах Пети, и достаточно истины в одном ходе Вани, и, наоборот, если победа должна произойти за нечётное число ходов, то необходимо, чтобы функция возвращала истину во всех ходах Вани, и достаточно истины в одном ходе Пети. Т.е., если победа должна случиться за четное число ходов, то для игрока победителя(Вани) используется any(), а для Пети all(). И, наоборот, если победа должна случиться за нечетное число ходов, то для игрока победителя (Пети) используется any(), а для Вани all().

Очевидно, что зависимость определяется чётностью номера хода в игре. Если четность хода игрока совпадает с четностью хода победного окончания игры, то используется any(), иначе all():

return any(h) if (p+1)%2== end%2 else all(h) #победа в чётном ходе (у Вани)

или:

return all(h) if (p+1)%2!= end%2 else any (h) #победа в нечётном ходе (у Пети)

Т.е., если ход делает тот игрок, для которого мы ищем победу используется any(), если противник, то all(); определяется это через совпадение чётности (p+1) и end.

Таким образом функция будет иметь вид:

def g(s, p, end):

if s <= 30 or p > end:

return p == end

h = [g(s-3, p+1, end), g(s-5, p+1, end), g(s//4, p+1, end)]

return any(h) if (p+1)%2== end%2 else all(h)

Проверим работу полученной универсальной функции.

Вывод результатов работы оригинальной функции(трех отдельных):

Для вывода результатов для ответа на первый (19) вопрос задачи напишем, указав значение параметра end=2:

print(19,([s for s in range(31,1000) if g(s,0,2)]))

Ответы совпадают:

Второй вопрос задачи (20):

print(20,([s for s in range(31,1000) if g(s,0,3)]))

Получаем ответ:

Рассмотрим получение ответа на третий (21) вопрос задачи. Но при попытке написать аналогичный двум предыдущим выводам код:

print(21,([s for s in range(31,1000) if g(s,0,4)]))

Мы получим некорректный ответ. Функция выведет нам не весь список значений:

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

Но при запуске такого варианта программы мы получим ошибочные значения в выводе ответа на второй(19) вопрос задачи:

Это произошло потому, что при поиске победы Пети вторым ходом, мы нашли значения ходов и для победы первым ходом. Поэтому, для того, чтобы получить корректные ответы для 20 и 21 задания нужно добавить дополнительное условие, в противном случае на экран будут выводится значения для победы за один (для 20го) или за два (для 21го) хода, а этих чисел не должно быть в ответах на задачу. Вывод для 20 и 21 задания будет выглядеть так:

print(20,[s for s in range(31,1000) if not g(s,0,1) and g(s,0,3)]))

print(21,[s for s in range(31,1000) if not g(s,0,2) and g(s,0,4)]))

Теперь мы получаем правильный ответ:

Заметим, что запись с указанным конкретным числовым значением:

return p == end or p==end-2

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

return p%2 == end%2

Т.е. четность победного хода должна совпадать с четностью общего количества ходов в игре.

Таким образом, универсальная программа для решения 19-21 задач выглядит так:

def g(s, p, end):

if s <= 30 or p > end:

return p%2 == end%2

h = [g(s-3, p+1, end), g(s-5, p+1, end), g(s//4, p+1, end)]

return any(h) if (p+1)%2== end%2 else all(h)

print(19,[s for s in range(31,1000) if g(s,0,2)])

print(20,[s for s in range(31,1000) if not g(s,0,1) and g(s,0,3)])

print(21,[s for s in range(31,1000) if not g(s,0,2) and g(s,0,4)])

В продолжение совершенствования этой функции, выполним ряд преобразований, используя определенные математические действия. Заменим переменную end на разность end-p

Перепишем наш код с этой заменой, учитывая математические правила раскрытия скобок и действий с положительными и отрицательными числами:

def g(s, end-p):

if s <= 30 or end — p < 0 : return (end-p)%2==0

h = [g(s-3, end-p-1), g(s-5, end-p-1), g(s//4, end-p-1)]

return any(h) if (end-p-1)%2==0 else all(h)

print(19,[s for s in range(31,1000) if g(s,2)])

print(20,[s for s in range(31,1000) if not g(s,1) and g(s,3)])

print(21,[s for s in range(31,1000) if not g(s,2) and g(s,4)])

Следующим шагом заменим выражение end-p на переменную m, и снова перепишем код:

def g(s, m):

if s <= 30 or m < 0 : return m %2==0

h = [g(s-3, m-1), g(s-5, m-1), g(s//4, m-1]

return any(h) if (m-1)%2==0 else all(h)

print(19,[s for s in range(31,1000) if g(s,2)])

print(20,[s for s in range(31,1000) if not g(s,1) and g(s,3)])

print(21,[s for s in range(31,1000) if not g(s,2) and g(s,4)])

Это кратчайшая запись для решения заданий номер 19-21.

Задача №7 (8818)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
– убрать из кучи 1 камень;
– убрать из кучи 3 камня;
– уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до большего).
Игра завершается, когда количество камней в куче становится не более 2143. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу из 2143 или менее камней. В начальный момент в куче было S камней, S ≥ 2144. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
  Вопрос 1. Укажите сумму значений S, при которых Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
  Вопрос 2. Найдите наименьшее и наибольшее значения S, когда Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
  Вопрос 3. Найдите количество значений S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение

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

from math import ceil

Задание 19.

Задаем список h возможных ходов в соответствии с условием задачи – ход игрок может убрать из кучи 1 камень; убрать из кучи 3 камня; уменьшить количество камней в куче в 4 раза (количество камней, полученное при делении, округляется до большего). После каждого хода увеличивается счётчик ходов p.

Для получения ответа, перебираем все возможные начальные значения S от 2144 до 99999, при начальном состоянии p = 0 (ходов еще не было), и выводим на экран подходящие значения:

def g(s,p):

if s<=2143 or p>2: return p==2

h = [g(s-1,p+1),g(s-3,p+1),g(ceil(s/4), p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(19, sum[s for s in range(2144,100000) if g(s,0)])

Запускаем, получаем результат:

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

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

Задание 20.

Задаём рекурсивную функцию g(s,p). Запишем условия окончания игры – теперь нас интересует только тот случай, если игра завершилась ровно на третьем ходу (p == 3).

Задаем список h возможных ходов в соответствии с условием.

def g(s,p):

if s<=2143 or p>3: return p==3

h = [g(s-1,p+1),g(s-3,p+1),g(ceil(s/4), p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,[s for s in range(2144,100000) if g(s,0)])

Запускаем, получаем ответ на второй вопрос задачи:

Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня, если в начальный момент времени в куче будет 8574, 8576, 34289, 34290, 34291 или 34292 камня. Наименьшие два значения – 8574 и 8576, это ответ на второй вопрос задачи.

Задание 21.

Задаём рекурсивную функцию g(s,p). Запишем условия окончания игры – теперь нас интересует только тот случай, если игра завершилась на втором или четвертом ходе (p == 2 or p==4).

Задаем список h возможных ходов в соответствии с условием задачи.

def g(s,p):

if s<=2143 or p>4: return p==2 or p==4

h = [g(s-1,p+1),g(s-3,p+1),g(ceil(s/4), p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(21,[s for s in range(2144,100000) if g(s,0)])

Запускаем, получаем ответ на третий вопрос задачи:

Ваня может выиграть своим первым или вторым ходом независимо от того, как будет ходить Петя, если в начальный момент времени в куче будет 8573, 8575, 8577, 34293 камня. Мы знаем, что начальном количестве камней, равном 8573 Ваня выиграет своим первом ходом, поэтому не считаем это число в ответе на 3 вопрос задачи. Всего существует начальных значения S, при которых Ваня выигрывает вторым ходом, но не может гарантированно выиграть первым. Указываем в ответе число 3.

Текст программы полностью:

from math import ceil

def g(s,p):

if s<=2143 or p>2: return p==2

h = [g(s-1,p+1),g(s-3,p+1),g(ceil(s/4), p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(19, [s for s in range(2144,100000) if g(s,0)])

def g(s,p):

if s<=2143 or p>3: return p==3

h = [g(s-1,p+1),g(s-3,p+1),g(ceil(s/4), p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,[s for s in range(2144,100000) if g(s,0)])

def g(s,p):

if s<=2143 or p>4: return p==2 or p==4

h = [g(s-1,p+1),g(s-3,p+1),g(ceil(s/4), p+1)]

return any(h) if (p+1)%2==0 else all(h)

print(21,[s for s in range(2144,100000) if g(s,0)])

Ответ:

1) 8573

2) 8574 34292

3) 3

Задача №8 (7678)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит две кучи камней. Игроки ходят по очереди, первый ход делает Петя. У каждого игрока есть 4 варианта хода: 1) добавить четыре камня в первую кучу; 2) добавить три камня во вторую кучу; 3) увеличить в 2 раза количество камней в первой куче; 4) увеличить в 3 раза количество камней во второй куче. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 178. Победителем считается игрок, сделавший последний ход, т. е. первым получивший суммарно в двух кучах 178 или больше камней.
В начальный момент в первой куче был 21 камень, во второй куче было S камней; 1 ≤ S ≤ 156.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Ответьте на следующие вопросы:
  Вопрос 1. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.
  Вопрос 2. Найдите сумму всех значений S, при которых Петя имеет выигрышную стратегию, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
  Вопрос 3. Найдите произведение всех значений S, при которых одновременно выполняются два условия:
– у Пети есть выигрышная стратегия, позволяющая ему выиграть первым, вторым или третьим ходом при любой игре Вани;
– у Пети нет стратегии, которая позволит ему гарантированно выиграть первым или вторым ходом.

Решение

Задание 19.

Задаём рекурсивную функцию g(a,b,p), где a, b – текущее количество камней в каждой из двух куч; p – номер хода с начала игры (первый ход Пети – p = 0). Запишем условия окончания игры – она заканчивается, если суммарное количество камней в кучах оказывается не менее 178, при этом нас интересует только тот случай, если игра завершилась ровно на втором ходу (p == 2).

Задаем список h возможных ходов в соответствии с условием задачи. После каждого хода увеличивается счётчик ходов p.

Для получения ответа, перебираем все возможные начальные значения S от 1 до 156, при начальном состоянии p = 0 (ходов еще не было), количестве камней в первой куче, равном 21, и выводим на экран минимальное подходящее значения:

def g(a,b,p):

if a+b>=178 or p>2: return p==2

h = [g(a+4,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*3,p+1)]

return any(h)

print(19,min([s for s in range(1,157) if g(21,s,0)]))

Запускаем, получаем результат:

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

Задание 20.

Задаём рекурсивную функцию g(a,b,p). Запишем условия окончания игры – теперь нас интересует только тот случай, если игра завершилась ровно на третьем ходе (p == 3).

Задаем список h возможных ходов в соответствии с условием задачи.

def g(a,b,p):

if a+b>=178 or p>3: return p==3

h = [g(a+4,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*3,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,sum([s for s in range(1,157) if g(21,s,0)]))

Запускаем, получаем ответ на второй вопрос задачи:

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

Задание 21.

Задаём рекурсивную функцию g(a,b,p). Запишем условия окончания игры – нас интересуют случаи, если игра завершилась на первом, третьем ходе или пятом ходе.

Задаем список h возможных ходов в соответствии с условием задачи.

def g(a,b,p):

if a+b>=178 or p>5: return p==5 or p==3 or p==1

h = [g(a+4,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*3,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

Для того, чтобы ответить на третий вопрос задачи (в этом случае игра должна закончиться пятым ходом (Петин третий ход)), нужно найти так же значения S, при которых Петя выигрывает за один или три хода. Для этого последовательно запустим программу для решения 21 задания, оставив сначала только условие p = 1, а затем оставив только условие p = 3. Получим два списка значений, Петя выигрывает первым ходом при S от 53 до 156, запишем их в отсортированный список p1, и Петя выигрывает своим вторым ходом при S = 17, 44, 45, 48, 49, 50, запишем эти значения в список p2.

p1 = list(range(53,157))

p2 = [17, 44, 45, 48, 49, 50]

Находим ответ на третий вопрос задачи – выводим на экран список чисел, при которых Петя имеет выигрышную стратегию в 3 хода, но не имеет выигрышной стратегии в 1 или 2 хода:

print(21,[s for s in range(1,157) if s not in p1+p2 and g(21,s,0)])

Запускаем программу, получаем результат:

Произведение этих чисел равно 1004640, это ответ на задачу.

Второй способ.

Импортируем функцию prod из библиотеки math для того, чтобы найти произведение чисел для ответа на третий вопрос задачи:

from math import prod

Напишем функцию, которая кроме аргументов a и b – количества камней в кучах будет принимать аргумент m – количество ходов до конца игры. Задаем условия игры и доступные ходы, если игра закончилась, функция проверяет четность m, от этого зависит кем был сделан последний ход (четное m – Ваня, нечетное – Петя):

def g(a,b,m):

if a+b>=178 or m<0: return m%2==0

h = [g(a+4,b,m-1),g(a,b+3,m-1),g(a*2,b,m-1),g(a,b*3,m-1)]

return any(h) if (m-1)%2==0 else all(h)

Выводим на экран ответы на вопросы задачи: в первой строке мы выводим минимальное значение S, при котором Ваня выигрывает своим первым ходом; во второй строке – сумму значений S, при которых Петя не выигрывает первым ходом, но выигрывает своим вторым ходом (третий ход игры); в третьей строке – произведение значений S, при которых Петя не выигрывает первым или вторым ходом, но выигрывает своим третьим ходом (пятый ход игры);

print(19,min([s for s in range(1,157) if g(21,s,2)]))

print(20,sum([s for s in range(1,157) if not g(21,s,1) and g(21,s,3)]))

print(21, prod([s for s in range(1,157) if not g(21,s,3) and g(21,s,5)]))

Запускаем программу, получаем результат:

Текст программы полностью:

def g(a,b,p):

if a+b>=178 or p>2: return p==2

h = [g(a+4,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*3,p+1)]

return any(h)

print(19,min([s for s in range(1,157) if g(21,s,0)]))

def g(a,b,p):

if a+b>=178 or p>3: return p==3

h = [g(a+4,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*3,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(20,sum([s for s in range(1,157) if g(21,s,0)]))

p1 = list(range(53,157))

p2 = [17, 44, 45, 48, 49, 50]

def g(a,b,p):

if a+b>=178 or p>5: return p==5 or p==3 or p==1

h = [g(a+4,b,p+1),g(a,b+3,p+1),g(a*2,b,p+1),g(a,b*3,p+1)]

return any(h) if (p+1)%2!=0 else all(h)

print(21,[s for s in range(1,157) if s not in p1+p2 and g(21,s,0)])

#II способ

from math import prod

def g(a,b,m):

if a+b>=178 or m<0: return m%2==0

h = [g(a+4,b,m-1),g(a,b+3,m-1),g(a*2,b,m-1),g(a,b*3,m-1)]

return any(h) if (m-1)%2==0 else all(h)

print(19, min([s for s in range(1,157) if g(21,s,2)]))

print(20,sum([s for s in range(1,157) if not g(21,s,1) and g(21,s,3)]))

print(21, prod([s for s in range(1,157) if not g(21,s,3) and g(21,s,5)]))

Ответ:

1) 18
2) 253
3) 1004640

Номер 19-21. ЕГЭ по информатике

Ещё номера