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

1.

Разбор
Олимпиады для 6-8
классов
Подготовили Матвей (Ирпаччи), Арсений
(Хайфаев) и Дарина(Шуька)

2.

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

3.

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

4.

Задача решается жадно.
Будем брать купюры по 100, пока можем, затем
поступаем точно так же с купюрами по 20, 10 и т.д.
Чтобы не делать это в явном виде, будем
пользоваться операциями деления и взятия остатка по
модулю.

5.

Итоговая асимптотика - приблизительно О(1).
Посылка - https://pastebin.com/HekKyTyr

6.

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

7.

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

8.

Задача решается формулами.
Номер вагона, в котором есть место с номером X, считается по формуле
(X + K - 1) / K. Такая же формула для места с номером Y: (Y + K - 1) / K.
К номеру места мы прибавляли K - 1, чтобы реализовать округление
вверх.
Осталось вывести разницу между (Y + K - 1) / K и (X + K - 1) / K

9.

Итоговая асимптотика - O(1)
Посылка - https://pastebin.com/UKSpvvAQ

10.

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

11.

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

12.

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

13.

Итоговая асимптотика - О(ввод), т.е. О(100).
Посылка - https://pastebin.com/R6YXD6j4

14.

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

15.

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

16.

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

17.

Итоговая асимптотика - О(N).
Посылка - https://pastebin.com/qs96EJEC

18.

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

19.

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

20.

Решение задачи:
Заметим, что нам имеет смысл смотреть только на тех
сотрудников, которым нужно на первый и последний
этаж. Тогда, если мы поднимаемся на этаж X,
затрачивается время
x * c + max(b * (x - 1), a * (n - x)).

21.

Необходимо заметить, что для лучшего ответа нам нужно максимально
приблизить друг к другу две части, из которых берём максимум.
Тогда b * (x - 1) ≈ a * (n - x).
Путём выражения получаем, что x ≈ (na + b) / (a + b).
Проверим на ответ этажи Х и Х + 1 и выберем минимальный по ответу.

22.

Итоговая асимптотика - О(1).
Посылка - https://pastebin.com/QVbnbfwV