Белорусская республиканская олимпиада 2018

Revision ru9, by wilcot, 2018-03-28 13:10:37

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

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

Первый тур

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

Условие

Ссылка by gepardo.

Решение

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

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

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

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

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

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

Условие

Ссылка by gepardo.

Решение

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

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

Условие

Ссылка by gepardo.

Решение

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

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

Условие

Ссылка by gepardo.

Решение

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

Второй тур

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

Условие

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

Решение

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

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

Условие

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

Решение

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

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

Условие

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

Решение

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

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

Условие

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

Решение

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru18 Russian wilcot 2018-03-28 23:18:06 0 (опубликовано)
ru17 Russian wilcot 2018-03-28 23:12:37 0 (сохранено в черновиках)
ru16 Russian wilcot 2018-03-28 23:11:06 89
ru15 Russian wilcot 2018-03-28 22:14:54 196
ru14 Russian wilcot 2018-03-28 22:13:47 806
ru13 Russian wilcot 2018-03-28 14:27:20 400
ru12 Russian wilcot 2018-03-28 14:25:30 2771 Мелкая правка: 'n * $H_{R_1C_1}$\n\nОбр' -> 'n * $H_{R_{1}C_{1}$\n\nОбр'
ru11 Russian wilcot 2018-03-28 13:53:47 325
ru10 Russian wilcot 2018-03-28 13:52:03 2124 Мелкая правка: ' summary="Условие">\n' -> ' summary="Текстовое условие">\n'
ru9 Russian wilcot 2018-03-28 13:10:37 17 Мелкая правка: ' \le 10^9$. К сожал' -> ' \le 10^9$ за $O(N \log M)$. К сожал'
ru8 Russian wilcot 2018-03-28 13:09:58 161
ru7 Russian wilcot 2018-03-28 13:06:15 402 Мелкая правка: ' (x^2 - 2 * x * X_i + X_i' -> ' (x^2 - 2 \cdot x \cdot X_i + X_i'
ru6 Russian wilcot 2018-03-27 22:35:58 1 Мелкая правка: 'о больше $frac{5}{4}' -> 'о больше $\frac{5}{4}'
ru5 Russian wilcot 2018-03-27 22:35:33 319 Мелкая правка: 'о больше $5/4$\n\n### З' -> 'о больше $frac{5}{4}$\n\n### З'
ru4 Russian wilcot 2018-03-27 22:15:27 796
ru3 Russian wilcot 2018-03-27 16:04:22 96
ru2 Russian wilcot 2018-03-27 00:20:04 932 Мелкая правка: 'льникам!**' -> 'льникам!**\n\nПервый тур\n=================='
ru1 Russian wilcot 2018-03-26 21:14:13 406 Первая редакция (опубликовано)