Almaty Code Cup

Задача G: Выпишем строку по кругу и для каждой пары соседних символов посчитаем количество шагов чтобы перейти из одного в другой по клавиатуре (манхеттенское расстояние). Ответом будет сумма всех таких расстояний минус расстояние из s[l] в s[1]. Циклический сдвиг строки позволяет переместить этот отнимаемый переход куда угодно, поэтому оптимально переместить его в позицию с максимальным расстоянием до следующего символа.

Задача H: Если вторая атака наносит больше урона, чем первая, то делаем её всегда когда можем, иначе всегда делаем первую атаку.

Задача I: Так как в вершинах можно останавливаться, то логично для каждой вершины посчитать dp[v] --- самый маленький момент времени когда мы сможем в неё приехать. Если аккуратно посмотреть, то такое dp подходит для алгоритма Дейкстры и нужно просто его применить.

Задача J: Если x = 1, то p >= 2 и все дроби просто равны нулю. Пусть x >= 2. Заметим, что floor(x / y) = (x - (x mod y)) / y. Следовательно floor(1 / p) + floor(x / p) + ... + floor(x^n / p) = (1 - (1 mod p)) / p + (x - (x mod p)) / p + ... + (x^n - (x^n mod p)) / p = ((1 + x + ... + x^n) - (1 mod p) - (x mod p) - ... - (x^n mod p)) / p. Сумму 1 + x + ... + x^n можно найти по формуле сокращенного умножения (x^{n + 1} - 1) / (x - 1). Заметим, что x^k mod p по малой теореме Ферма циклично с периодом p - 1, следовательно достаточно для каждого 0 <= k <= p - 1 посчитать вклад остатка x^k mod p в общую сумму и найти ответ.

Задача K: Нарисуем точки на прямой и ограничение p[i] <= x сделаем в виде полуинтервала [p[i], inf), а p[i] >= x в виде полуинтервала (-inf, p[i]]. Тогда нам надо найти точку, которая не лежит на минимальном количестве полуинтервалов. Отсюда понятно, что можно считать все запросы в оффлайн и сжать координаты до [1, n + m]. Теперь для каждого p[i] в дереве отрезков сделаем += 1 на все точки, которые не входят в соответствующий интервал (то есть буквально скажем, что им надо изменить знак одного дополнительного неравенства); для p[i] <= x нужно сделать tree.update(l = 1, r = p[i] - 1, val += 1) например. Теперь пройдем по запросам постепенно обновляя дерево отрезков и делая запрос tree.getmin(1, n + m).

🤯3🥰1

1.3K views16:05