Никто не подскажет ссылку на условия задач с прошедшей олимпиады ICL? Вообще достаточно весело — на opencup.ru дорешка есть, но условия не выкладывают)) Заранее спасибо

Задача "Доктор" (B в div1, D в div2).
Если сумма всех количеств приемов в очереди меньше чем K, то ответ -1.
Этапом назовем процесс, когда каждый из очереди сделал ровно один прием (то есть очередь пошла заново).

Сделаем бинарный поиск по количеству этапов X. Посчитаем могло ли пройти столько этапов - для этого достаточно пробежать по всем животным из очереди и просуммировать min(a{i}, X) (каждый прошел либо X приемов, либо сколько хотел). Если это число не превзошло K - то могло. Так мы нашли максимальное количество этапов X_max, которое прошло до конца приема доктора.

После этого из всех a{i} вычтем X_max, и выкинем всех животных у которых a{i} стало не положительным. Очевидно, что до конца приема осталось не более чем N этапов - теперь мы их можем просто промоделировать указателем, вычитая 1 из соответствующего a{i}, и удаляя его если оно становиться не положительным.

Асимптотика O(N * log N). Также существуют решения, использующие сортировку, сет и дерево отрезков. Они все имеют такую же асимптотику.

Задача "Трасса" (C в div1, E в div2).
Переберем все возможные комбинации букв, через которые мы пройдем. После это запустим обход в ширину из конечной клетки поля, в учетом того, что можем ходить только по выбранным буквам.
Если начальная клетка недостижима, то пути нету (для данных выбранных букв). Иначе найдем минимальный лексикографический путь, проходящий по зафиксированным буквам.

Это можно сделать моделируя следующим образом - будем идти из текущего множества клеток (первоначально только начальная вершина) во все клетки с минимальной лексикографически буквой, но при условии что путь до конечной клетки уменьшается (для этого пускали бфс из конечной вершины) при этом запоминая букву.

Ответом будет являться минимальная по длине (а при равенстве - минимальная лексикографическая) строка-ответ, полученная среди всех комбинаций букв.
Асимптотика решения O(C{k, 26} * N * M) или O(C{k, 26} * N * M * log max(N, M)) в зависимости от реализации. И то, и другое авторское решение работает не больше секунды.

Задача "Числа" (D div1).
Первый шаг: проверка К на простоту. Если К составное, то ответ 0.
Второй шаг: разбиваем задачу на отрезке [l, r] на две подзадачи на отрезках [1, r] и [1, l - 1].
Вычитаем решение второй из решения первой и получаем ответ.

Теперь рассмотрим два возможных решения подзадачи на отрезке [1, N]:
I) Строгое решение:
Вспомним, как на отрезке [1, N] для всех чисел найти минимальный простой делитель за O(N * log log N) времени и O(N) памяти (на самом деле лучше искать за O(N) но задача прекрасно работает и без этого). Это легко делается с помощью решета Эратосфена, просто для каждого числа запомним минимальный делитель, которым мы вычеркнули это число.

Если N / K int-ов помещается в память то решение элементарно: ответ это количество чисел на отрезке [1, N / K], таких, что их минимальный простой делитель не меньше, чем К (тут можно считать что у 1 минимальный делитель бесконечность).
Имеем количеcтво операций O(N / K * log log (N / K))

Иначе, можно понять, что К небольшое. В частности К не превосходит 100 (на самом деле граница ниже). Пусть P - количество простых чисел не превосходящих К. Среди первых 100 натуральных чисел 25 простых, следовательно P <= 25. А теперь попробуем восстановить ответ с помощью формулы включения-исключения. Переберем все 2^P комбинаций простых чисел меньших К.
Для каждой комбинации определим, сколько существует чисел <= N, которые делятся на каждое простое число из комбинации.
Если в комбинации s чисел, то таких ровно N / K / (p{1} * ... * p{s}), причем если s нечетно то это количество надо вычесть, иначе прибавить к ответу (это и есть суть формул включения-исключения)
С помощью пересчета эту часть можно реализовать за O(2^P) операций и O(2^P) памяти.

II) Без строго обоснования асимптотики:
Для всех чисел до S = sqrt(N) посчитаем минимальных простой делитель. Также выпишем все простые числа до S. Построим рекурсивную функцию F(n, k), которая будет отвечать на поставленную подзадачу для n и k.
Если n / k <= S, то просто пробежимся по всем числам до n / k и просуммируем те, у которых минимальный делитель >= k.
Иначе заметим, что ответ можно вычислить как res = n / k - F(n / k, p{1}) - ... - F(n / k, p{w}),
то есть вычесть все такие числа из диапазона [1, n / k], у которых минимальный делитель меньше чем k.

Точную оценку асимптотики привести не могу) Это работает быстро. Пишется легче, чем предыдущее решение и многие писали что то похожее.
Работает примерно O(sqrt(N) * log(N)), но это эмпирическая оценка без доказательства.