Задача A (div2):

Очевидно, что нам необходимо делать последовательность ходов вида: 1, 2, 1, 2, ...

Ответ будет примерно равен 2 * n / 3. После этого у нас останется 0, 1 или 2 камня. Если у нас осталось 0 камней, то все закончилось, иначе у нас осталось либо 1, либо 2 камня и очевидно, что мы можем в этих случаях взять только 1 камень.

Итоговый ответ: (2 * n) / 3 + (n % 3 != 0 ? 1 : 0);

Задача B (div2):

Мы можем просто симулировать поведение кузнечика и отмечать все позиции, на которых он был. Очевидно, что таких различных позиций будет O(n). Если кузнечик попадет на клетку, где он уже был, то мы попали в цикл, и ответ — INFINITE. Иначе — FINITE.

Задача A(div1)/C(div2):

Давайте заведем 2 матрицы: a, idx. В матрице a мы будем хранить NULL для ячеек, о которых мы ничего не знаем или значение, если мы уже его определили. idx будет инициализировано как idx[i][j] = {i, j}; Затем просто просимулируем процесс для матрицы idx. Для запросов 3-его типа мы можем просто присвоить значение в матрице a, так как мы знаем исходную позицию по матрице idx.

Задача B(div1)/D(div2):

Основная идея задачи в том, что относительный порядок элементов в четных позициях и в нечетных позициях не меняется при выполнении команд с точностью до циклического сдвига.

Давайте хранить позицию для 1ого и 2ого мальчика. После 1ой операции мы сдвинем эти позиции на X или -X. Вторая операция просто поменяет позиции местами (поменяются местами все четные и нечетные позиции, но мы нам это не важно, так как по 1ому и 2ому мальчику можно все восстановить). В конце просто восстановим четные и нечетные позиции независимо и объединим ответ.

Задача C(div1)

Сперва решим обратную задачу: найдем минимум (максимум) от двух распределений. Воспользуемся формулами:

P(a = k) = P(a <= k) — P(a <= k-1) P(max(a, b) <= k) = P(a <= k) * P(b <= k)

Соответственно для минимума:

P(min(a, b) >= k) = P(a >= k) * P(b >= k) = (1 — P(a <= k-1)) *(1 — P(b <= k-1))

Теперь в наших формулах из условия минимум и максимум определяют систему квадратных уравнений для каждой пары P(a <= k), P(b <= k).

Если решить эти уравнения, мы получим P(a<=k), P(b<=k) = (u + v ± sqrt((u + v)^2 — 4u)) / 2, где u = P(max(a,b) <= k), v = P(min(a,b) <= k). Теперь можно заметить, что если ответ существует, то мы тогда существует ответ, когда мы выберем знаки для каждой пары одинаково. (смотри комментарий)

Задача D(div1)/E(div2)

Существует много способов решать задачу. Один из них — SQRT-декомпозиция. Сперва сожмем все времена. Для каждого блока в декомпозиции мы будем хранить баланс для каждого элемента независимо. Ответ вычисляется просто как сумма балансов в блоках меньше того, где находится наше время плюс все балансы в текущем блоке до нашего времени для данного элемента.

Другой способ — воспользоваться структурой данных описаной здесь. Для каждого элемента будем хранить два дерева — дерево времен удалений и добавлений. Тогда по порядковому номеру времени запроса в этих деревьях легко найти ответ.

Задача E(div1)

Построим для обеих формул граф импликаций и найдем компоненты сильной связности в графе. Если обе формулы несовместны, то ответ SIMILAR. Если только одна формула несовместна, то ответ — ответ для второй формулы.

Допустим обе формулы совместны. Построим транзитивное замыкание для графов. Будем называть переменную X фиксированной в формуле F, если существует путь из -> x или (x -> ). Если есть фикированная переменная в одной формуле, но не в другой (или фиксированная, но имеет другое значение) мы можем найти ответ для второй формулы с противоположным значение этой переменной — это и будет ответом. Если мы не смогли найти эти переменные — удалим их все. В оставшемся графе нет фиксированных переменных. Найдем такое ребро u->v, которе есть в одном графе, но отсутствует в другом. Найдем решение для формулы без этого ребра, когда u = 1 и v = 0 (мы всегда можем найти решение). Это и будет ответ.

Задача F(div1)

Разбор появится скоро.