Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 65. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах оказывается 65 или больше камней.
В начальный момент в первой куче было шесть камней, во второй куче – S камней; 1 ≤ S ≤ 58.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
ЕГЭ по информатике Основная волна 07.06.2024 kompege.ru – задание №19-21
19. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.
Ответ:
20. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Ответ:
21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
- у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
- у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе укажите наименьшее из них.
Ответ:
Решение на Python
|
def f(a, b, m): if a+b>=65: return m%2==0 if m==0: return 0 h= [f(a+1,b,m-1), f(a,b+1,m-1), f(a*3,b,m-1), f(a,b*3,m-1), ] return any(h) if (m-1)%2==0 else all(h) print('19)', [s for s in range(1, 59) if f(s, 6, 2)]) #all->any print('20)', [s for s in range(1, 59) if not f(s, 6, 1) and f(s, 6, 3)]) print('21)', [s for s in range(1, 59) if not f(s, 6, 2) and f(s, 6, 4)]) |
19) [
7, 8, 9, 10, 11, 12,,… …]
20) [10, 19]
21) [18]
Объяснение кода:
- Функция
f(a, b, m)
:
|
def f(a, b, m): if a+b>=65: return m%2==0 if m==0: return 0 h= [f(a+1,b,m-1), f(a,b+1,m-1), f(a*3,b,m-1), f(a,b*3,m-1)] return any(h) if (m-1)%2==0 else all(h) |
Функция f
определяет, есть ли выигрышная стратегия для игрока с текущими параметрами:
if a+b>=65: return m%2==0
: Если сумма камней в кучах больше или равна 65, игра заканчивается. Возвращаем True
, если текущий игрок выиграл (ход четный).
if m==0: return 0
: Если ходов не осталось, возвращаем False
.
- Создаем список
h
, содержащий результаты всех возможных ходов (добавление 1 камня или умножение количества камней в куче на 3).
return any(h) if (m-1)%2==0 else all(h)
: Возвращаем any(h)
, если ход четный, иначе all(h)
.
- Задача 19:
|
print('19)', [s for s in range(1, 59) if f(s, 6, 2)]) |
Для задачи 19 мы ищем значения S
, при которых Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от хода Вани.
- Задача 20:
|
print('20)', [s for s in range(1, 59) if not f(s, 6, 1) and f(s, 6, 3)]) |
Для задачи 20 мы ищем значения S
, при которых Петя не может выиграть за один ход, но может выиграть своим вторым ходом.
- Задача 21:
|
print('21)', [s for s in range(1, 59) if not f(s, 6, 2) and f(s, 6, 4)]) |
Для задачи 21 мы ищем значения S
, при которых Петя не может выиграть гарантированно за один ход, может выиграть своим вторым ходом.
Исправление для задачи 19:
Для задачи 19, изменение условия возврата функции f
:
|
return any(h) if (m-1)%2==0 else any(h) |
Таким образом, для задачи 19, условие в строке return any(h) if (m-1)%2==0 else all(h)
изменяется на return any(h) if (m-1)%2==0 else any(h)
. (Ваня выиграл своим первым ходом после неудачного первого хода Пети)
Итог:
Этот код решает задачи 19, 20 и 21, связанные с определением выигрышной стратегии для игры двух игроков. Функция f
проверяет возможность выигрыша в зависимости от текущего состояния игры и количества оставшихся ходов.