Разбор задач
- 1. Разбор задач 3 тура школьного этапа Кормышов Михаил http://krasprog.ru
- 2. Задача А. Время года Условие Дан номер месяца, определить время года. Ограничение N < 101
- 3. Задача А. Время года Решение Для решения задачи достаточно воспользоваться оператором ветвления if.
- 4. Задача В. Футбол Условие Дана сумма чисел после каждого изменения счёта в матче. Найти количество забитых мячей. Ограничение S < 103 + 1
- 5. Задача В. Футбол Наблюдение Очевидно, что после каждого забитого мяча, сумма счёта увеличивается на 1: 1+0=1, 1+1=2, 1+2=3, 2+2=4, 2+3=5. Таким образом мы имеем дело с арифметической прогрессией.
- 6. Задача В. Футбол Решение Сумма арифметической прогрессии равна: S = (1 + n) * n / 2 Откуда n = (sqrt(1 + 8S) – 1) / 2
- 7. Задача С. Игра с пешкой Условие Двое играют на квадратной доске. Определить гарантированный выигрыш первого игрока. Ограничение N < 101
- 8. Задача С. Игра с пешкой Идея решения Воспользуемся динамическим программированием. Будем вести подсчёты, начиная с последнего хода. Если ход из mi,j совершает второй игрок, то он выберет клетку со значением равным min(mi+1,j, mi,j-1). Если первый, то – максимум.
- 9. Задача С. Игра с пешкой Продолжение Определять очерёдность хода можно по чётности суммы номеров столбца и строки текущей клетки. Время работы алгоритма O(N2).
- 10. Задача D. Доказательство теоремы Условие Дано дерево. Надо выбрать минимальное множество вершин (включая первую), чтобы у каждой выбранной вершины выбранными было не меньше половины потомков. Ограничение N < 104 + 1
- 11. Задача D. Доказательство теоремы Решение Применим к графу топологическую сортировку и будем рассматривать вершины в этом порядке. Тогда, при рассмотрении вершины i, все её потомки будут уже рассмотрены. А значит не трудно составить из них список с минимальной суммой.
- 12. Спасибо за внимание Ваши вопросы?