Задания 19, 20 и 21 — про одну и ту же игру двух игроков: они по очереди добавляют камни в одну или две кучи, и выигрывает тот, кто первым наберёт нужное число. Базовый уровень: в задании 19 нужно найти, при каком начальном числе камней возможен или гарантирован выигрыш первым ходом; ответ — число, 1 балл.
Ответ
число в поле ответа
Баллы
1 балл
Проверяет
умение анализировать алгоритм логической игры: понять по правилам, кто и за сколько ходов может выиграть из данной позиции
Сколько времени закладывать
около 5 минут по спецификации ФИПИ
Какие бывают подтипы
Такая ситуация возможна — Как в демоверсии: известно, что Ваня выиграл первым ходом, но, может быть, после ошибки Пети. Хватает одного неудачного хода Пети.
Выигрыш при любой игре соперника — Ваня выигрывает первым ходом, как бы ни сходил Петя: все ходы Пети ведут в проигрыш.
Пример с полным разбором
Условие. В куче S камней, 1≤S≤29. Петя и Ваня ходят по очереди, первым ходит Петя. За ход можно добавить в кучу один камень или увеличить число камней вдвое. Игра заканчивается, когда в куче становится 30 камней или больше; победил тот, кто сделал последний ход. Найдите наименьшее S, при котором Ваня может выиграть своим первым ходом, если Петя сходит неудачно.
Сначала находим кучи, из которых ходящий выигрывает одним ходом: удвоение даёт 30 и больше при S≥15. Кучи от 15 до 29 — выигрышные одним ходом.
Ваня выигрывает первым ходом, если после хода Пети в куче оказалось от 15 до 29 камней.
Условие не требует, чтобы так было при любом ходе Пети: достаточно одного его хода в эту зону — Петя мог ошибиться.
Удвоением Петя попадает в зону при 2S≥15, то есть при S≥8: из 8 камней он делает 16, и Ваня удваивает до 32. Прибавлением одного камня туда попадают только из 14.
Наименьшее S — 8.
Ответ: 8
Частые ошибки
Путают «такая ситуация возможна» и «при любой игре Пети»: в первом случае хватает одного неудачного хода Пети.
Переносят условие победы неточно: «не меньше 30» и «больше 30» — разные игры.
Забывают, что первый ход в стартовой позиции делает Петя, а вопрос задан про Ваню.
Ищут наибольшее значение вместо наименьшего.
Когда куч две, сравнивают с целью одну кучу, а не сумму камней в обеих.
Что нужно знать для задания 19
Оглавление курса «ЕГЭ по информатике» под это задание. Содержание открывается после оплаты.
Один, если число совпало с верным. Задания 20 и 21 — про ту же игру, но оцениваются отдельно, каждое в 1 балл.
Нужна ли программа для заданий 19–21?
По спецификации специальные программы здесь не требуются: игру разбирают на черновике, выписывая позиции. Короткая программа-перебор тоже допустима — оценивают только ответ.
Что такое выигрышная стратегия?
Способ играть, при котором игрок выигрывает при любых ходах соперника. В задании 19 бывает и более слабое требование — выигрыш только при ошибке соперника.