РАЗБОР ЗАДАЧ ОЛИМПИАДЫ И ПРАКТИКА
ОСНОВНЫЕ УЧЕБНЫЕ РЕСУРСЫ
Существует множество различных ресурсов, на которых вы можете легко поучаствовать в олимпиадах и попрактиковаться в решении задач. Я могу порекомендовать codeforces.com, informatics.msk.ru и acm.timus.ru
В этой главе мы разберем пару задач, взятых из школьного этапа ВсОШ 2022 года. Найти больше вы можете на сайте: https://olimpiada.ru/activity/73/tasks
ЗАДАЧА №1
ЛЯГУШКА И КУЗНЕЧИК
В крайних клетках полоски шириной в одну клетку и длиной в N клеток сидят лягушка и кузнечик: лягушка в клетке № 1, кузнечик в клетке № N. Каждую секунду лягушка прыгает в сторону кузнечика, и одновременно кузнечик прыгает в сторону лягушки. Лягушка может прыгать только на две или на три клетки, кузнечик, только на одну или на две клетки. За какое наименьшее время они смогут оказаться в одной клетке?
ФОРМАТ ДАННЫХ
Входные данные
N - длина клетчатой полосы (целое число, 2 < N < 2 * 10^9)
Выходные данные
Вывод - минимальное количество секунд, через которое лягушка и кузнечик встретятся (целое число). Если они не смогут оказаться в одной клетке, вывести число -1
ТЕСТЫ
N = 5,
Вывод = 1
N = 9,
Вывод = 2
РЕШЕНИЕ
Расстояние между лягушкой и кузнечиком N = 1 клеток. За одну секунду это расстояние может сократиться на 3, 4 или 5 клеток. Поэтому если N − 1 = 1 или N − 1 = 2 (то есть при N < 4) лягушка и кузнечик не смогут встретиться и нужно вывести -1. Во всех остальных случаях им понадобится (N − 1) / 5 прыжков, округленное вверх. Это значение можно вычислить по формуле (N - 1 + 4) // 5 (где // - операция целочисленного деления)
ЗАДАЧА №2
Заказ в магазине
Решив запастись ручками на весь новый учебный год, Игорь подсчитал, что ему нужно M ручек. В его любимом интернет-магазине есть удобная функция - он может сразу добавить в заказ упаковку из любого числа ручек от 1 до N. Правда, оказалось, что нельзя добавить в заказ две упаковки одного размера. Например, если Игорю нужно купить M = 12 ручек, а максимальное число ручек в упаковке N = 10, то Игорь может добавить в заказ упаковку из 7 ручек и упаковку из 5 ручек, но не сможет добавить две упаковки из 6 ручек. Сформируйте заказ на M ручек, используя минимальное число различных упаковок.
ФОРМАТ ДАННЫХ
Входные данные
N - максимальный размер одной упаковки (1 <= N <= 10^9)
M - обходимое количество ручек в заказе (1 <= M <= 10^9)
Выходные данные
Вывод - размеры выбранных упаковок (одно или несколько чисел от 1 до N) в любом порядке. Есть имеется несколько возможных решений, то выведите любое из них. Если решения не существует, необходимо вывести одно число 0
ТЕСТЫ
N = 10,
M = 12,
Вывод = 5; 7
N = 2,
M = 5,
Вывод = 0
РЕШЕНИЕ
Сначала проверим, существует ли решение. Максимальное количество ручек, которое можно заказать, равно 1 + 2 + 3 + ... + N = N (N + 1)/2 (по формуле суммы арифметической прогрессии), и если M > N (N + 1)/2, то решения не существует. Если эту сумму вычислять не по формуле, а при помощи цикла, то цикл длины N можеть не уложиться в ограничение по времени. В этом случае стоит прервать цикл, если сумма превысит M, либо заметить, что если N > √2 · 109 ≈ 44721, то 1 + 2 + 3 + ... + N > 109 и решение существует. Если решение существует, то воспользуемся жадным алгоритмом: будем выбирать упаковки мак- симально возможного размера: N, N − 1, N − 2 и т.д. Если размер рассматриваемой упаковки s больше или равен M, то выведем значение s и уменьшим M на s