796042 — Игры и выигрышные стратегии: ответ и решение

Задание №1. Впишите правильный ответ.

Правила игры

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней, такую позицию
в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6),
(10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 107. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 107 или больше камней.

В начальный момент в первой куче было 13 камней, во второй куче $-$ S камней, 1 ≤ S ≤ 93.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока $-$ значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

СВОЙСТВА ЗАДАНИЯ

КЭС:

2.13 Графы. Основные понятия. Виды графов. Описание графов с помощью матриц смежности, весовых матриц, списков смежности. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа)

2.14 Деревья. Бинарное дерево. Деревья поиска. Способы обхода дерева. Представление арифметических выражений в виде дерева. Использование графов и деревьев при описании объектов и процессов окружающего мира

3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность

3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат

3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве

3.11 Двумерные массивы (матрицы). Алгоритмы обработки двумерных массивов: заполнение двумерного числового массива по заданным правилам, поиск элемента в двумерном массиве, вычисление максимума (минимума) и суммы элементов двумерного массива, перестановка строк и столбцов двумерного массива

3.12 Словари (ассоциативные массивы, отображения). Хэш-таблицы. Построение алфавитно-частотного словаря для заданного текста

3.13 Стеки. Анализ правильности скобочного выражения. Вычисление арифметического выражения, записанного в постфиксной форме. Очереди. Использование очереди для временного хранения данных

3.14 Алгоритмы на графах. Построение минимального остовного дерева взвешенного связного неориентированного графа. Количество различных путей между вершинами ориентированного ациклического графа. Алгоритм Дейкстры

3.15 Деревья. Реализация дерева с помощью ссылочных структур. Двоичные (бинарные) деревья. Построение дерева для заданного арифметического выражения. Рекурсивные алгоритмы обхода дерева. Использование стека и очереди для обхода дерева

Тип ответа:

Краткий ответ

Номер: 796042

1 (E59F9F)

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINF796042

Ответ: 24

Решение.
Позицию обозначим (x; y): это числа камней в двух кучах. Цель хода — получить x + y ≥ 107.
За ход к одной из куч прибавляется 1 или её размер умножается на 2. Меняется только одна куча; первый ход делает Петя.
Здесь требуется возможность победы Вани после неудачного хода Пети. Значит, достаточно одной подходящей пары ходов; после первого хода игра ещё должна продолжаться.
Проверим S = 24. Начальная позиция (13; 24).
Петя получает (13; 48), сумма равна 61, что меньше 107.
Ваня отвечает ходом в (13; 96): сумма 109 ≥ 107. Победа наступает именно на первом ходе Вани.
Докажем минимальность. Каждая из четырёх команд не уменьшает число камней; состав любой пары команд также монотонен по S. Достаточно показать, что при предыдущем S никакие два хода не достигают цели.
Пусть S = 23. Для каждого первого хода перечислим суммы после всех четырёх возможных вторых ходов:
Первый ход в (14; 23): 38, 51, 38, 60; максимум 60.
Первый ход в (26; 23): 50, 75, 50, 72; максимум 75.
Первый ход в (13; 24): 38, 50, 38, 61; максимум 61.
Первый ход в (13; 46): 60, 72, 60, 105; максимум 105.
Общий максимум равен 105 меньше 107. При любом меньшем S все эти суммы только уменьшаются, поэтому выиграть вторым общим ходом невозможно.
Проверка: рассмотрены оба выбора кучи и оба вида команды у каждого игрока, то есть все 16 пар ходов; показанная партия достигает границы минимального S.
Ответ: 24.

Задание EGEINF796042: Игры и выигрышные стратегии

Правила игры

Решение задания EGEINF796042

Помочь улучшить сайт

Комментарии к решению