Задача 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):
Будем называть k-клику B потомком k-клики A, если B можно получить из A последовательностью следующих операций: добавить в клику вершину, связанную со всеми вершинами кликами в описании графа и выкинуть ровно одну другую вершину. Посчитаем динамику по состояниям (k-клика, разбиение ее вершин на компоненты), означающую следующее — количество остовных лесов в графе, индуцированном самой кликой и всеми ее потомками таких, что клика разделится по разным компонентам связности согласно заданному разбиению вершин (а все остальные вершины будут связаны с какой-нибудь из этих компонент). Для этого предпросчитаем все разбиения из k и k+1 элементов и переходы:
1) (разбиение k+1 вершин) x (разбиение k+1 вершин) -> (разбиение k+1 вершин | null), переводящее пару разбиений — лесов в набор компонент связности их объединения, или null если появится цикл
2) (разбиение k+1 вершин) x (вершина) -> (разбиение k+1 вершин | null), переводящее лес в новый лес, образованный добавлением ребра из вершины в вершину k+1 (или null, если образуется цикл)
3) (разбиение k+1 вершин) -> (разбиение k вершин | null), проецирующее разбиение на первые k вершин (или null, если k+1-ая вершина образовывает отдельную компоненту)
Детали реализации можно посмотреть в решении автора.
