На этой неделе (26-30.03.2018) проходит республиканская олимпиада в г. Минске. Как обычно будет два тура, на которых будет предположительно по 4 задачи. К сожалению задачи будут, наверное, сильно сложными для меня, поэтому предлагаю обсудить решения в комментариях к этому посту. А можно обсудить не только задачи :)
Желаю удачи всем участвующим школьникам!
Первый тур
Задача 1. Галактика
Условие
Решение
Чтобы решить исходную задачу, необходимо решить три более простые задачи для каждой отдельной координаты.
Решим задачу для координаты X.
Пусть мы выбрали x, тогда ответ будет равен: 
. Предподсчитав 
и 
, можно за O(1) перебрать все координаты.
Сложность по времени: O(N + M), по памяти: O(1).
Бонус: попробуйте решить задачу для M ≤ 109 за 
. К сожалению придется использовать __int128, но самое интересное — это идея, а не детали реализации.
Задача 2. Поиск в перестановке
Условие
Решение
Можно получить легкие баллы воспользовавшись std::nth_element(). К сожалению, у данного алгоритма константа количества сравнений точно больше 
, поэтому полные баллы не удастся получить, но 90 баллов — запросто.
Задача 3. Спортивная трасса
Условие
Решение
{{ Решение задачи }}
Задача 4. Дерево удачи
Условие
Решение
{{ Решение задачи }}
Второй тур
Задача 1. Несложная задача
Условие
Решение
{{ Решение задачи }}
Задача 2. Город художников
Условие
Решение
{{ Решение задачи }}
Задача 3. Реорганизация
Условие
Решение
{{ Решение задачи }}
Задача 4. Лабиринт
Условие
Решение
{{ Решение задачи }}
Comments (0)
