ФИПИ · ЕГЭ · все форматы ответа · 2475 заданий
Тип задачи: Игры и выигрышные стратегии.
| КЭС: | 2.13 Графы. Основные понятия. Виды графов. Описание графов с помощью матриц смежности, весовых матриц, списков смежности. Решение алгоритмических задач, связанных с анализом графов (построение оптимального пути между вершинами графа, определение количества различных путей между вершинами ориентированного ациклического графа) 2.14 Деревья. Бинарное дерево. Деревья поиска. Способы обхода дерева. Представление арифметических выражений в виде дерева. Использование графов и деревьев при описании объектов и процессов окружающего мира 3.2 Оценка сложности вычислений. Время работы и объём используемой памяти, их зависимость от размера исходных данных. Оценка асимптотической сложности алгоритмов. Алгоритмы полиномиальной сложности. Переборные алгоритмы. Примеры различных алгоритмов решения одной задачи, которые имеют различную сложность 3.3 Определение возможных результатов работы простейших алгоритмов управления исполнителями и вычислительных алгоритмов. Определение исходных данных, при которых алгоритм может дать требуемый результат 3.10 Массивы и последовательности чисел. Вычисление обобщённых характеристик элементов массива или числовой последовательности (суммы, произведения, среднего арифметического, минимального и максимального элементов, количества элементов, удовлетворяющих заданному условию). Линейный поиск заданного значения в массиве. Алгоритмы работы с элементами массива с однократным просмотром массива. Сортировка одномерного массива. Простые методы сортировки (метод пузырька, метод выбора, сортировка вставками). Сортировка слиянием. Быстрая сортировка массива (алгоритм QuickSort). Двоичный поиск в отсортированном массиве 3.11 Двумерные массивы (матрицы). Алгоритмы обработки двумерных массивов: заполнение двумерного числового массива по заданным правилам, поиск элемента в двумерном массиве, вычисление максимума (минимума) и суммы элементов двумерного массива, перестановка строк и столбцов двумерного массива 3.12 Словари (ассоциативные массивы, отображения). Хэш-таблицы. Построение алфавитно-частотного словаря для заданного текста 3.13 Стеки. Анализ правильности скобочного выражения. Вычисление арифметического выражения, записанного в постфиксной форме. Очереди. Использование очереди для временного хранения данных 3.14 Алгоритмы на графах. Построение минимального остовного дерева взвешенного связного неориентированного графа. Количество различных путей между вершинами ориентированного ациклического графа. Алгоритм Дейкстры 3.15 Деревья. Реализация дерева с помощью ссылочных структур. Двоичные (бинарные) деревья. Построение дерева для заданного арифметического выражения. Рекурсивные алгоритмы обхода дерева. Использование стека и очереди для обхода дерева |
| Тип ответа: | Краткий ответ |
Ответ: 34
Решение.
Пусть x — число камней перед ходом. Допустимые действия: прибавить 1, прибавить 4, а также умножить на 3.
Игра завершается сразу после хода, если число камней становится не меньше 103.
Сначала определим позиции, из которых можно выиграть одним ходом. Для прибавления a требуется x + a ≥ T, для умножения — m · x ≥ T.
Наименьшие целые x для разрешённых команд: 102, 99, 35. Поэтому возможность немедленной победы равносильна x ≥ 35.
Петя не должен выигрывать первым ходом, значит S ≤ 34.
Среди его команд есть прибавление 1. После такого хода Ваня обязан иметь немедленную победу: S + 1 ≥ 35, откуда S ≥ 34.
Обе необходимые границы дают единственного кандидата S = 34. Осталось проверить все ходы Пети, а не только прибавление единицы.
Петя: 34 → 35; Ваня: 35 → 105, и игра заканчивается.
Петя: 34 → 38; Ваня: 38 → 114, и игра заканчивается.
Петя: 34 → 102; Ваня: 102 → 103, и игра заканчивается.
Ни один перечисленный первый ход Пети сам не завершает игру. После каждого из них указан допустимый завершающий ответ Вани.
Проверка: список содержит каждую разрешённую команду Пети; Ваня выбирает ответ после того, как видит ход соперника. Получено именно требуемое «при любом ходе», а минимальность или единственность установлена предварительными границами.
Ответ: 34.
Напишите пожелание к сайту или решению либо сообщите о найденной неточности в задании EGEINF17A122.
Сообщение увидит только команда сайта: на странице оно не публикуется.
Комментарии к решению
Комментарии видны всем посетителям сайта.
Комментариев пока нет. Будьте первым.
Чтобы оставить комментарий, войдите или зарегистрируйтесь.