Div2 A. Для решения данной задачи достаточно вывести "0 0 n".

Автор задачи — Alex_KPR .

Div2 B. Для каждой окружности одного кольца нужно определить — имеет ли она пересечения с другим кольцом (касаться можно). Итого 4 проверки.

Возможны 3 случая:
1. окружность внутри кольца;
2. окружность вне кольца и кольцо находится вне окружности;
3. окружность вне кольца и кольцо находится внутри окружности.
Если хотя бы одно из этих условий выполняется, то окружность хорошая.

Проверку легко сделать следующим образом. Пусть d — расстояние между центрами кольца и окружности, r₁ и R₁ — внутренний и внешний радиусы кольца, r — радиус окружности. Тогда условия запишутся как
1. d + r ≤ r₁.
2. r + R₁ ≤ d.
3. d + R₁ ≤ r.
Эти проверки удобно проводить в целых числах, используя квадраты расстояний.

Автор задачи — Alex_KPR

Div2 C. Div1 A.
Первый вариант решения. Рассмотрим последовательность a₀ = 1, a_i = a_i - 1k + b:
a₀, a₁, a₂, ..., a_n = z.
Заметим, что для всех чисел из отрезка [a₀, a₁ - 1] ровно за n преобразований мы получим число не меньше z, однако за n - 1 преобразование мы получим число строго меньше z. Это верно из соображений монотонности функции преобразования. Аналогичные рассуждения можно применить и к числам из отрезков [a₁, a₂ - 1], [a₂, a₃ - 1] и так далее, только там будет n - 1, n - 2 шагов и так далее. Значит, для решения задачи, нам нужно узнать к какому из отрезков принадлежит число t. Это можно сделать просто сгенерировав несколько первых членов последовательности a. Не более чем через t шагов найдется подходящий отрезок.

Второй вариант решения. Запишем уравнения в лоб:
tk^x + b(k^x - 1 + k^x - 2... + 1) ≥ kⁿ + b(k^x - 1 + k^x - 2... + 1)
Воспользуемся формулой для геометрической прогрессии:

Далее считаем k ≠ 1, случай k = 1 удобно рассмотреть отдельно в самом начале (его разбирать не будем, он тривиален).
t(k - 1)k^x + bk^x - b ≥ (k - 1)kⁿ + bkⁿ - b

k^x(t(k - 1) + b) ≥ kⁿ(k - 1 + b)

Итак, величину n - x можно найти простым возведением в степень "пока не переполнится".

Авторы — Gerald и Ripatti

Div2 D. Div1 B. Заведем граф, в котором вершинами являются участки стен, ребрами — возможные перемещения ниндзя и запустим на нем поиск в ширину (BFS) с одной модификацией: если мы добрались до некоторой вершины позже, чем до туда добралась вода, то оттуда не делаем ходов.

Решение имеет сложность O(n).

Автор — Ripatti

Div2 E. Div1 C. Заметим, что если мы можем достичь планеты за некоторое время t, то мы можем достичь ее и за любое большее время (для этого достаточно достичь ее за время t, а затем просто перемещаться вместе с планетой). Понятно, что существует некоторое t₀, для которого для всех t > t₀ достичь планету можно, а для всех t < t₀ — нельзя. Будем искать t₀ при помощи бинпоиска.

Проверку каждого из t внутри бинпоиска можно осуществлять следующим образом. Вычислим положение планеты через время t и найдем расстояние от корабля до этого нового положения.

Задача свелась к следующей "классической" задаче: есть две точки A и B и круг с центром в O радиуса R (точки вне круга), нужно найти расстояние между точками, при этом в круг заходить нельзя.

Возможны 2 случая:
1. Можно пройти напрямую
2. Следует огибать круг

Второй случай выполняется тогда и только тогда, когда верны оба утверждения:
a. Углы OAB и OBA острые
b. Высота OH меньше R
Все проверки можно сделать в целых числах.

Теперь поймем как обработать случаи:
1. Очевидно
2. Пусть C и D — точки касания (т.е. мы должны двигаться по линии ACDB). Треугольники OAC и OBD — прямоугольные, там можно легко вычислить все углы, откуда легко найти угол COD. Дальше вычислить длину линии несложно. Заметим, что находить положения точек C и D совсем не обязательно.

Автор — Ripatti

Div1 D. Суть авторского решения в том, чтобы рекурсивно строить решения в виде параллелепипедов размера k × k × (k + 1), содержащих нужные 2 куба размера k × k × k. Для k = 2 решение очевидно. Далее решение расширятся в соответствии с картинкой:

Красный и синий кубики — начало и конец цепи. Сначала мы надстраиваем один этаж сверху, а затем 2 слоя по бокам. Построения зависят от четности текущего k.

Чтобы получить решение для n построим n × n × (n + 1), а потом просто отбросим один слой.

Автор — Ripatti

Div1 E. Расположим все захваты как точки на плоскости с координатами (расстояние, масса). Тогда, пользуясь некоторым захватом, мы можем собирать все захваты внутри некоторого прямоугольника с углом в начале координат. Будем собирать захваты и помещать их в очередь. Тогда для текущего захвата все захваты в прямоугольнике собраны — будем доставать следующий захват из очереди и делать манипуляции с ним. Осталось научиться делать запросы быстро.

Заведем дерево отрезков (например, удобно использовать дерево Фенвика) по координате "расстояние", в каждой вершине которого будем хранить стек из точек, упорядоченных по координате "масса". Каждая вершина дерева отрезков есть некоторый диапазон координат, именно точки из этого диапазона будут храниться в данной вершине. На вершине каждого стека будет захват с наименьшей массой. Положим вначале все точки в это дерево отрезков. Так как каждая координата покрыта не более чем отрезками, всего это дерево будет использовать памяти.

При выполнении запроса мы извлекаем из некоторых стеков точки с массой, не превышающей некоторого значения и помещаем их в очередь. Следует отметить, что одна и та же точка может находиться в разных стеках и мы можем случайно положить в очередь одну и ту же точку дважды. Чтобы избежать этого, можно вместе с точкой складывать в дерево отрезков ее номер. А при извлечении точки проверять первое это извлечение или нет в некотором массиве флагов по номеру.

Итого решение имеет сложность .

Автор — Ripatti ; описанное выше решение предложил RAD