Задание 19 ЕГЭ Информатика ФИПИ
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
добавить в кучу один камень или увеличить количество камней в куче в два раза.
Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или из 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче превышает 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 46 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 45.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы следующего стратегии игрока, которые не являются для него безусловно выигрышными.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Решение
1. Структура рекурсивной функции f(x, p)
Функция f(x, p) проверяет, может ли игрок на текущем ходе выиграть при данных условиях.
Параметры:
- x - текущее количество камней в куче
- p - номер хода (0 - начало игры, 1 - первый ход, 2 - второй ход)
2. Базовые случаи (условия завершения)
if x >= 46 and p == 2:
return 1
Если камней ≥46 И это второй ход (ход Вани) → Ваня выиграл → возвращаем 1 (победа)
elif x < 46 and p == 2:
return 0
Если камней <46 И это второй ход → игра закончилась, но Ваня не выиграл → возвращаем 0 (проигрыш)
elif x >= 46 and p < 2:
return 0
Если камней ≥46 ДО второго хода → Петя выиграл на первом ходу → возвращаем 0 (это не удовлетворяет условию, что Ваня выиграл)
3. Рекурсивные вызовы
else:
a = []
a.append(f(x + 1, p + 1))
a.append(f(x * 2, p + 1))
return any(a)
- Если игра продолжается, рассматриваем все возможные ходы:
Добавить 1 камень: f(x + 1, p + 1)
Удвоить количество: f(x * 2, p + 1) - any(a) возвращает True (1), если ХОТЯ БЫ ОДИН из ходов ведёт к победе
4. Логика работы программы
Цикл поиска:
python
for s in range(1, 46):
if f(s, 0) == 1:
print("19 задание = ", s)
break
- Перебираем все возможные начальные значения S от 1 до 45
- Для каждого S запускаем функцию с параметрами f(s, 0) (начало игры, ход Пети)
- Ищем минимальное S, при котором возвращается 1
5. Как это соответствует условию задачи
Программа ищет ситуации, где:
- Петя делает первый ход из позиции S
- Ваня выигрывает на своём первом ходу (p = 2)
Важно: Функция проверяет, существует ли стратегия для текущего игрока, которая гарантирует победу при ЛЮБОМ ходе противника.
6. Пример работы для S = 12
f(12, 0):
p=0, x=12 < 46
Вычисляем f(13, 1) и f(24, 1)
f(13, 1):
p=1, x=13 < 46
Вычисляем f(14, 2) и f(26, 2)
f(14, 2): 14<46 и p=2 → return 0
f(26, 2): 26<46 и p=2 → return 0
any([0,0]) = 0
f(24, 1):
p=1, x=24 < 46
Вычисляем f(25, 2) и f(48, 2)
f(25, 2): 25<46 и p=2 → return 0
f(48, 2): 48≥46 и p=2 → return 1
any([0,1]) = 1
any([0,1]) = 1
Результат: f(12, 0) = 1 → S=12 подходит.
7. Почему программа находит правильный ответ
Программа проверяет для каждого S:
- Может ли Петя выбрать такой ход, чтобы Ваня мог выиграть на своём ходе
- При этом учитываются ВСЕ возможные ответные ходы
Функция возвращает 1, если существует ХОТЯ БЫ ОДИН ход Пети, приводящий к победе Вани.
8. Особенности реализации
- any() возвращает True при первом найденном True (ленивое вычисление)
- break останавливает поиск после нахождения минимального подходящего S
- Рекурсия может быть неэффективной для больших глубин, но здесь глубина всего 2 хода
Результат выполнения: программа найдёт и выведет 19 задание = 12
Задача 20 ЕГЭ Информатика ФИПИ
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
добавить в кучу один камень или увеличить количество камней в куче в два раза.
Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или из 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче превышает 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 46 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 45.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы следующего стратегии игрока, которые не являются для него безусловно выигрышными.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
Решение
1. Логика задачи в терминах рекурсивной функции
Функция f(x, p) проверяет, может ли игрок при ходе p и количестве камней x достичь победы при своей игре в соответствии с условиями.
p — чётность:
- p = 0 — ход Пети (начало)
- p = 1 — ход Вани
- p = 2 — ход Пети (второй)
- p = 3 — ход Вани (второй) — но игра может закончиться раньше.
python
def f(x, p):
if x >= 46 and p == 3:
return 1
elif x < 46 and p == 3:
return 0
elif x >= 46 and p < 3:
return 0
else:
a = []
if p % 2 != 0: # ход Вани (нечётные p: 1)
a.append(f(x + 1, p + 1))
a.append(f(x * 2, p + 1))
return all(a) # Ваня выигрывает, если все его ходы ведут к победе
else: # ход Пети (чётные p: 0, 2)
a.append(f(x + 1, p + 1))
a.append(f(x * 2, p + 1))
return any(a) # Петя выигрывает, если хотя бы один ход ведёт к победе
2. Разбор условий в функции
Анализ работы программы для s = 11
Логика функции:
- p - номер хода (0, 1, 2, 3)
- p = 0, 2 (четные) - ходы противника: any (достаточно одного выигрышного пути)
- p = 1, 3 (нечетные) - ходы нашего игрока: all (нужны все выигрышные пути)
- Цель: на p = 3 иметь x ≥ 46
Вычисление f(11, 0):
f(11,0) → any
├── f(12,1) → all → ❌ [0]
│ ├── f(13,2) → any → ❌ [0]
│ │ ├── f(14,3) → 0 (14<46)
│ │ └── f(26,3) → 0 (26<46)
│ └── f(24,2) → any → ✅ [1]
│ ├── f(25,3) → 0 (25<46)
│ └── f(48,3) → 1 (48≥46)
└── f(22,1) → all → ✅ [1]
├── f(23,2) → any → ✅ [1]
│ ├── f(24,3) → 0 (24<46)
│ └── f(46,3) → 1 (46≥46)
└── f(44,2) → any → ✅ [1]
├── f(45,3) → 0 (45<46)
└── f(88,3) → 1 (88≥46)
Результат: f(11,0) = any([0, 1]) = 1 ✅
Выигрышная стратегия:
- Ход 1 (p=0): 11 → 22 (умножить на 2)
- Ход 2 (p=1): противник может пойти:
22 → 23 (+1) → наш ответ: 23 → 46 (×2)
22 → 44 (×2) → наш ответ: 44 → 88 (×2)
Оба варианта гарантируют победу на 3-м ходу.
Анализ работы программы для s = 21
Логика функции:
- p - номер хода (0, 1, 2, 3)
- p = 0, 2 (четные) - ходы противника: any (достаточно одного выигрышного пути)
- p = 1, 3 (нечетные) - ходы нашего игрока: all (нужны все выигрышные пути)
- Цель: на p = 3 иметь x ≥ 46
Вычисление f(21, 0):
f(21,0) → any
├── f(22,1) → all → ✅ [1]
│ ├── f(23,2) → any → ✅ [1]
│ │ ├── f(24,3) → 0 (24<46)
│ │ └── f(46,3) → 1 (46≥46)
│ └── f(44,2) → any → ✅ [1]
│ ├── f(45,3) → 0 (45<46)
│ └── f(88,3) → 1 (88≥46)
└── f(42,1) → all → ❌ [0]
├── f(43,2) → any → ❌ [0]
│ ├── f(44,3) → 0 (44<46)
│ └── f(86,3) → 1 (86≥46)
└── f(84,2) → any → ✅ [1]
├── f(85,3) → 1 (85≥46)
└── f(168,3) → 1 (168≥46)
Результат: f(21,0) = any([1, 0]) = 1 ✅
Выигрышная стратегия:
- Ход 1 (p=0): 21 → 22 (+1)
- Ход 2 (p=1): противник может пойти:
22 → 23 (+1) → наш ответ: 23 → 46 (×2)
22 → 44 (×2) → наш ответ: 44 → 88 (×2)
Оба варианта гарантируют победу на 3-м ходу.
Ключевая логика ветвления:
- Если p нечётное (Ваня), то all(a) — Ваня выигрывает, только если при любых его ходах (в рамках ограничения p=3) он побеждает.
- Если p чётное (Петя), то any(a) — Петя выигрывает, если существует ход, ведущий к победе.
Но из-за условия if x>=46 and p<3: return 0 — если Петя выигрывает на p=0 или p=2, это не считается? Нет, это условие говорит: если куча >=46 до p=3, то это не та ситуация, которую мы рассматриваем как "успех по плану до p=3". Это ошибка — оно должно быть return 1, если это ход Пети (p чётное), и return 0, если ход Вани (p нечётное), но у вас оно всегда 0.
Задание 21 ЕГЭ Информатика ФИПИ
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
добавить в кучу один камень или увеличить количество камней в куче в два раза.
Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или из 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче превышает 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 46 или больше камней.
В начальный момент в куче было S камней; 1 ≤ S ≤ 45.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы следующего стратегии игрока, которые не являются для него безусловно выигрышными.
Найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение
def f(x,p):
if x>=46 and (p==2 or p==4): return 1
elif x<46 and p==4: return 0
elif x>=46 and p<4:return 0
else:
a=[]
if p%2==0:
a.append(f(x+1,p+1))
a.append(f(x*2,p+1))
return all(a)
else:
a.append(f(x + 1, p + 1))
a.append(f(x * 2, p + 1))
return any(a)
for s in range(1,46):
if f(s,0)==1:
print("21 задание = ",s)
1. Понимание условия
У нас есть:
- Петя (1-й ход) и Ваня ходят по очереди
- Начальное число: s (ищем, для каких s выигрывает Ваня)
- Ход: +1 или *2
- Цель: первым достичь ≥46
- Рассматриваются партии, где ровно 4 хода (2 хода Петей, 2 ходя Ваней)
2. Анализ функции f(x, p)
Параметры:
- x — текущее число
- p — номер хода (0, 1, 2, 3, 4)
Условия:
python
if x>=46 and (p==2 or p==4): return 1
Если достигли 46+ на ходу 2 (первый ход Вани) или ходу 4 (второй ход Вани) — это победа Вани.
python
elif x<46 and p==4: return 0
Если после 4 ходов не достигли 46 — Ваня не выиграл.
python
elif x>=46 and p<4: return 0
Если достигли 46+ до хода 2 или 4 — победа не в нужный момент (не Ваня выиграл).
3. Логика ходов
- p чётное (0, 2, 4) — ход Вани? Нет: p=0 — Петя, p=1 — Ваня, p=2 — Петя, p=3 — Ваня, p=4 — Петя? Подождите, проверяем:
p=0: Петя
p=1: Ваня
p=2: Петя
p=3: Ваня
p=4: Петя
Значит:
- p чётное (0, 2, 4) — ход Пети
- p нечётное (1, 3) — ход Вани
Дерево вычислений для f(20, 0) ✅❌
f(20,0) = any ✅
├── f(21,1) = all ❌
│ ├── f(22,2) = any ❌
│ │ ├── f(23,3) = all ❌
│ │ │ ├── f(24,4) = 0 ❌
│ │ │ └── f(46,4) = 1 ✅
│ │ └── f(44,3) = all ❌
│ │ ├── f(45,4) = 0 ❌
│ │ └── f(88,4) = 1 ✅
│ └── f(42,2) = any ✅
│ ├── f(43,3) = all ❌
│ │ ├── f(44,4) = 0 ❌
│ │ └── f(86,4) = 1 ✅
│ └── f(84,3) = all ✅
│ ├── f(85,4) = 1 ✅
│ └── f(168,4) = 1 ✅
└── f(40,1) = all ✅
├── f(41,2) = any ✅
│ ├── f(42,3) = all ❌
│ │ ├── f(43,4) = 0 ❌
│ │ └── f(84,4) = 1 ✅
│ └── f(82,3) = all ✅
│ ├── f(83,4) = 1 ✅
│ └── f(164,4) = 1 ✅
└── f(80,2) = 1 ✅
Финальный результат: f(20, 0) = 1 ✅
Присоединяйтесь к нашему каналу в ДЗЕН «Учитель версии 4.0»!
Будем рады видеть вас среди наших подписчиков. На канале вас ждет эксклюзивный контент:
- Разборы сложных задач по Информатике.
- Советы по использованию Digital-инструментов в учебе.
- Актуальные новости из мира образовательных технологий.
Подписывайтесь, чтобы быть в курсе!
Учитель Информатики
Халтурина Надежда Вячеславовна
