На этой неделе (26-30.03.2018) проходит республиканская олимпиада в г. Минске. Как обычно будет два тура, на которых будет предположительно по 4 задачи. К сожалению задачи будут, наверное, сильно сложными для меня, поэтому предлагаю обсудить решения в комментариях к этому посту. А можно обсудить не только задачи :)

Желаю удачи всем участвующим школьникам!  

Первый тур

Задача 1. Галактика

Условие

Ссылка by gepardo.

Решение

Чтобы решить исходную задачу, необходимо решить три более простые задачи для каждой отдельной координаты.

Решим задачу для координаты X.

Пусть мы выбрали x, тогда ответ будет равен: . Предподсчитав и , можно за O(1) перебрать все координаты.

Сложность по времени: O(N + M), по памяти: O(1).

Бонус: попробуйте решить задачу для M ≤ 10⁹ за . К сожалению придется использовать __int128, но самое интересное — это идея, а не детали реализации.

Задача 2. Поиск в перестановке

Условие

Ссылка by gepardo.

Решение

Можно получить легкие баллы воспользовавшись std::nth_element(). К сожалению, у данного алгоритма константа количества сравнений точно больше , поэтому полные баллы не удастся получить, но 90 баллов — запросто.

Задача 3. Спортивная трасса

Условие

Ссылка by gepardo.

Решение

{{ Решение задачи }}

Задача 4. Дерево удачи

Условие

Ссылка by gepardo.

Решение

{{ Решение задачи }}

Второй тур

Задача 1. {{Название задачи}}

Условие

{{ Условие задачи }}

Решение

{{ Решение задачи }}

Задача 2. {{Название задачи}}

Условие

{{ Условие задачи }}

Решение

{{ Решение задачи }}

Задача 3. {{Название задачи}}

Условие

{{ Условие задачи }}

Решение

{{ Решение задачи }}

Задача 4. {{Название задачи}}

Условие

{{ Условие задачи }}

Решение

{{ Решение задачи }}