Разбор

Олимпиады для 6-8 классов

Подготовили Матвей (Ирпаччи), Арсений (Хайфаев) и Дарина(Шуька)

A. Гарри Поттер и волшебный банк "Гринготтс"

​

Условие задачи - набрать N денежных единиц при помощи купюр номиналом 100, 20, 10, 5 и 1, используя как можно меньше купюр.

Задача решается жадно.

Будем брать купюры по 100, пока можем, затем поступаем точно так же с купюрами по 20, 10 и т.д.

Чтобы не делать это в явном виде, будем пользоваться операциями деления и взятия остатка по модулю.

Итоговая асимптотика - приблизительно О(1).

Посылка - https://pastebin.com/HekKyTyr

В. Гарри Поттер и Хогвартс-экспресс

​

Условие задачи - есть поезд, состоящий из вагонов. Каждый вагон имеет K мест в нем. Нужно узнать количество вагонов между вагоном, в котором есть место с номером X, и вагоном, в котором есть место с номером Y.

Задача решается формулами.

Номер вагона, в котором есть место с номером X, считается по формуле (X + K - 1) / K. Такая же формула для места с номером Y: (Y + K - 1) / K.

К номеру места мы прибавляли K - 1, чтобы реализовать округление вверх.

Осталось вывести разницу между (Y + K - 1) / K и (X + K - 1) / K

Итоговая асимптотика - O(1)

Посылка - https://pastebin.com/UKSpvvAQ

C. Гарри Поттер и очень секретное сообщение

​

Условие задачи - дано некоторое количество строк. Необходимо взять по первому элементу каждой строки и составить из них новую строку, которая и будет являться ответом.

Задача решается в лоб.

Единственная проблема, которая может возникнуть - ввод. Если пользоваться while(cin >> s), мы введём все строки по одной, как и нужно. Альтернативный вариант - использовать getline(cin, s) и добавлять в строку все элементы, перед которыми стоят пробелы (и первый).

Итоговая асимптотика - О(ввод), т.е. О(100).

Посылка - https://pastebin.com/R6YXD6j4

D. Гарри Поттер и "исчезательное" заклинание

Условие задачи - есть массив из N элементов. Мы можем сколько угодно раз удалить любой элемент, заплатив за него стоимость, равную любому из соседних элементов. Необходимо вывести минимальную стоимость для того, чтобы превратить массив в один элемент.

Задача решается в лоб.

Заметим, что мы не можем удалить элемент за стоимость меньше минимального элемента в массиве. Тогда давайте будем просто удалять элементы рядом с минимальным, чтобы платить именно эту стоимость. В итоге получаем, что все элементы были удалены за К, где К - минимальный элемент массива.

Итоговая асимптотика - О(N).

Посылка - https://pastebin.com/qs96EJEC

E. Гарри Поттер и лифт в Министерстве магии

Условие задачи - есть N этажей и N сотрудников, по одному на этаж. Лифт стоит на 0 этаже, и один раз поднимается на любой этаж со скоростью С секунд на этаж. Сотрудник поднимается на 1 этаж за А секунд, спускается за В секунд. Необходимо вывести номер этажа, на который должен подняться лифт, чтобы сотрудники вернулись на свои этажи как можно быстрее.

Решение задачи:

Заметим, что нам имеет смысл смотреть только на тех сотрудников, которым нужно на первый и последний этаж. Тогда, если мы поднимаемся на этаж X, затрачивается время

x * c + max(b * (x - 1), a * (n - x)).

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

Тогда b * (x - 1) ≈ a * (n - x).

Путём выражения получаем, что x ≈ (na + b) / (a + b).

Проверим на ответ этажи Х и Х + 1 и выберем минимальный по ответу.

Итоговая асимптотика - О(1).

Посылка - https://pastebin.com/QVbnbfwV