Главная / Задания ЕГЭ / Задание 19
Задание 19 ЕГЭ по информатике
Теория игр: выигрыш первым ходом. Игра с кучей или двумя кучами камней. Нужно найти значения S, при которых Ваня выигрывает первым ходом после неудачного хода Пети.
Как решать
- Опишите ходы функцией и проверяйте позиции рекурсивно.
- Позиция выигрышная, если есть ход в проигрышную для соперника.
- Перебирайте S и проверяйте условие задачи.
Частые ошибки
- Путают «Петя выигрывает» и «Ваня выигрывает после неудачного хода Пети».
Пример задания
Два игрока, Петя и Ваня, играют в следующую игру. Игроки ходят по очереди, первый ход делает Петя. Перед игроками лежат две кучи камней. За один ход игрок может по своему выбору выполнить одно из действий с одной из куч:
• добавить 5 камней;
• увеличить количество камней в 2 раза.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 101. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 20 камней, во второй — S камней; 1 ≤ S ≤ 80.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.
• добавить 5 камней;
• увеличить количество камней в 2 раза.
Игра завершается в тот момент, когда суммарное количество камней в двух кучах становится не менее 101. Победителем считается игрок, сделавший последний ход.
В начальный момент в первой куче было 20 камней, во второй — S камней; 1 ≤ S ≤ 80.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.
Показать ответ и разбор
Ответ: 21
Перебор S с проверкой позиций от конца игры (на Python — рекурсия с мемоизацией). Ваня выигрывает своим первым ходом после неудачного хода Пети при S = 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, …. Наименьшее — 21.
В тренажёре каждый раз новое задание этого типа: ответ проверяется сразу, после ответа виден короткий разбор.
Все задания ЕГЭ
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 темам ЕГЭ по информатике и составим план подготовки.
Записаться на пробный урок