ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Игры и выигрышные стратегии.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах оказывается 59 или больше камней.
В начальный момент в первой куче было пять камней, во второй куче – S камней; 1 ≤ S ≤ 53.
| КЭС: | 2.13 Графы. Основные понятия. Виды графов. Описание графов с помощью матриц смежности, весовых матриц, списков смежности. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа) 2.14 Деревья. Бинарное дерево. Деревья поиска. Способы обхода дерева. Представление арифметических выражений в виде дерева. Использование графов и деревьев при описании объектов и процессов окружающего мира 3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность 3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат 3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве 3.11 Двумерные массивы (матрицы). Алгоритмы обработки двумерных массивов: заполнение двумерного числового массива по заданным правилам, поиск элемента в двумерном массиве, вычисление максимума (минимума) и суммы элементов двумерного массива, перестановка строк и столбцов двумерного массива 3.12 Словари (ассоциативные массивы, отображения). Хэш-таблицы. Построение алфавитно-частотного словаря для заданного текста 3.13 Стеки. Анализ правильности скобочного выражения. Вычисление арифметического выражения, записанного в постфиксной форме. Очереди. Использование очереди для временного хранения данных 3.14 Алгоритмы на графах. Построение минимального остовного дерева взвешенного связного неориентированного графа. Количество различных путей между вершинами ориентированного ациклического графа. Алгоритм Дейкстры 3.15 Деревья. Реализация дерева с помощью ссылочных структур. Двоичные (бинарные) деревья. Построение дерева для заданного арифметического выражения. Рекурсивные алгоритмы обхода дерева. Использование стека и очереди для обхода дерева |
| Тип ответа: | Краткий ответ |
Ответ: 23
Решение.
Начальная позиция — (5; S), где 1 ≤ S ≤ 53. За ход меняется одна выбранная куча: к ней добавляют 1 камень или увеличивают её в 2 раза. Игра заканчивается, как только сумма двух куч достигает 59 или превышает это число. Петя ходит первым.
Из позиции (a; b) разрешены четыре перехода: (a + 1; b), (a; b + 1), (2a; b), (a; 2b). Порядок куч сохраняем во всех таблицах.
Рассматриваем позицию с точки зрения игрока, которому сейчас ходить. Введём четыре класса позиций. W₁ — можно закончить игру следующим ходом. L₁ — любой разрешённый ход передаёт сопернику позицию W₁, поэтому соперник гарантированно выигрывает своим первым ходом.
Для (a; b) условие W₁ проверяется по получающимся суммам: a + b + 1, 2a + b, a + 2b. Два хода добавления дают одинаковую сумму. Достаточно, чтобы хотя бы одна из этих сумм была не меньше 59.
W₂ — выиграть за один ход нельзя, но есть ход в L₁. После такого хода соперник вынужден передать позицию W₁, и игрок завершает игру своим вторым ходом. Проверка здесь состоит из существования одного подходящего собственного хода и проверки всех ответов противника.
L₂ — позиция не относится к L₁, а каждый разрешённый ход ведёт в W₁ или W₂. Тогда соперник гарантирует победу своим первым либо вторым ходом. Исключение L₁ необходимо: по условию задачи 21 победа первым ходом не должна гарантироваться. Терминальную позицию не относим ни к одному из этих четырёх классов: игра в ней уже закончилась.
Нужные начальные значения S — это позиции L₂, поскольку первым ходит Петя, а указанная в условии стратегия нужна Ване. Проверяем допустимые S по возрастанию и выбираем первое подходящее.
Результат последовательной проверки всех начальных S от 1 до 53 включительно. Для каждого перехода применяем правила выше; для двух куч проверяем и позиции с изменившейся первой кучей.
| Класс начальной позиции | Значения S |
|---|---|
| W₁ | 27–53 |
| L₁ | нет |
| W₂ | 24, 26 |
| L₂ | 23, 25 |
| Не входит в эти четыре класса | 1–22 |
Покажем гарантированную стратегию для найденных значений. Каждая строка таблицы — возможное развитие игры; на ходе противника перечислены все допустимые ответы, на ходе победителя выбран один обеспечивающий победу ход. Знак «—» означает, что игра уже закончилась.
При S = 23:
| Начало | Петя, ход 1 | Ваня, ход 1 | Петя, ход 2 | Ваня, ход 2 |
|---|---|---|---|---|
| (5; 23) | (6; 23) | (12; 23) | (13; 23) | (13; 46) |
| (5; 23) | (6; 23) | (12; 23) | (24; 23) | (48; 23) |
| (5; 23) | (6; 23) | (12; 23) | (12; 24) | (12; 48) |
| (5; 23) | (6; 23) | (12; 23) | (12; 46) | (13; 46) |
| (5; 23) | (10; 23) | (10; 24) | (11; 24) | (11; 48) |
| (5; 23) | (10; 23) | (10; 24) | (20; 24) | (40; 24) |
| (5; 23) | (10; 23) | (10; 24) | (10; 25) | (10; 50) |
| (5; 23) | (10; 23) | (10; 24) | (10; 48) | (11; 48) |
| (5; 23) | (5; 24) | (10; 24) | (11; 24) | (11; 48) |
| (5; 23) | (5; 24) | (10; 24) | (20; 24) | (40; 24) |
| (5; 23) | (5; 24) | (10; 24) | (10; 25) | (10; 50) |
| (5; 23) | (5; 24) | (10; 24) | (10; 48) | (11; 48) |
| (5; 23) | (5; 46) | (5; 92) | — | — |
Победу Вани именно первым ходом гарантировать нельзя: Петя может начать переходом в (6; 23). Все возможные ответы Вани из неё: (7; 23), (12; 23), (6; 24), (6; 46). Ни один из них не завершает игру. При этом таблица показывает, как Ваня выигрывает не позднее своего второго хода при любом выборе Пети.
Проверка: все переходы в таблицах разрешены условием, игра нигде не продолжается после достижения порога, а каждая конечная позиция получена ходом нужного игрока. Независимый перебор дерева игры до второго хода каждого игрока подтвердил те же классы для всех проверенных S и все ветви приведённых стратегий.
Следовательно, минимальное подходящее значение S равно 23.
Ответ: 23.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINFEF6C0A.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.