Главная / Задания ЕГЭ / Задание 20
Задание 20 ЕГЭ по информатике
Теория игр: выигрыш вторым ходом. Нужно найти значения S, при которых Петя не может выиграть первым ходом, но выигрывает вторым при любой игре Вани.
Как решать
- Используйте ту же рекурсивную функцию «выигрыш за k ходов».
- Отберите S, где выигрыш за 1 ход невозможен, а за 2 хода — гарантирован.
Частые ошибки
- Не проверяют все ответы Вани.
Пример задания
Два игрока, Петя и Ваня, играют в следующую игру. Игроки ходят по очереди, первый ход делает Петя. Перед игроками лежат две кучи камней. За один ход игрок может по своему выбору выполнить одно из действий с одной из куч:
• добавить 2 камня;
• увеличить количество камней в 2 раза.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 109. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 18 камней, во второй — S камней; 1 ≤ S ≤ 90.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Для игры, описанной выше, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите через пробел в порядке возрастания.
• добавить 2 камня;
• увеличить количество камней в 2 раза.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 109. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 18 камней, во второй — S камней; 1 ≤ S ≤ 90.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Для игры, описанной выше, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите через пробел в порядке возрастания.
Показать ответ и разбор
Ответ: 35 36
Петя выигрывает своим вторым ходом (но не первым) при S = 35, 36, 43, 44. Два наименьших: 35 и 36. Удобно перебрать S рекурсивной функцией «кто выигрывает за ≤ k ходов».
В тренажёре каждый раз новое задание этого типа: ответ проверяется сразу, после ответа виден короткий разбор.
Все задания ЕГЭ
1Граф и таблица2Таблица истинности3Базы данных4Условие Фано5Алгоритм6Черепаха7Звук и изображения8Комбинаторика9Электронные таблицы10IP-адреса11Количество информации12Исполнитель МТ13Количество программ14Системы счисления15Логика с параметром16Рекурсия17Последовательности18Робот и таблица19Теория игр20Теория игр21Теория игр22Процессы23Взвешенный граф24Символьные строки25Делители и маски26Сортировка и жадные алгоритмы27Кластеры
Нужна помощь с ЕГЭ?
На пробном уроке посмотрим ваш уровень по 2–3 темам ЕГЭ по информатике и составим план подготовки.
Записаться на пробный урок