622A - Бесконечная последовательность

Вычтем из числа n единицу. Определим сначала номер блока в который попало n-е число. Для это сначала вычтем из числа n число 1, затем 2, затем 3 и так далее пока n не станет отрицательным. Количество вычитаний и будем номером блока, а позицией в блоке будет последнее неотрицательное число, которое мы встретим.

С++ solution

Сложность: .

622B - Время

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

А можно было просто посчитать ответ формулой: .

C++ solution 1

C++ solution 2

Сложность: O(a) or O(1).

622C - Не равный на отрезке

Эту задачу можно было решать по разному, например, с помощью структур данных или sqrt-декомпозиции. Но это, конечно, делать не требовалось. Мы предполагали следующее простое линейное решение. Сделаем сначала предподсчет: для каждого числа номер первого не равного ему слева. Теперь, чтобы ответить на запрос нужно сначала проверить число в правой границе на равентсво числу x, если они не равны то мы уже нашли ответ. Если же они равны проверим первое число слева не равное числу в правой границе.

C++ solution

Сложность: O(n).