374A — Инна и розовое пони

Рассмотрим задачу о перемещении конфеты из позиции (x₁, y₁) в позицию (x₂, y₂). Очевидно, что каждым движением мы увеличиваем или уменьшаем x₁ на a и y₁ на b.

Тогда несложно догадаться, что если |x₂ - x₁| не делится нацело на a или |y₂ - x₁| не делится нацело на a, то добраться не возможно.

Стоит также заметить, что числа |x₂ - x₁| / a и |y₂ - y₁| / b должны быть одинаковы по парности, так как увеличение или уменьшение происходит одновременно для обоих значений.

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

Теперь мы можем определить сложность пути позиции (x₁, y₁) в позицию (x₂, y₂) как max(|x₁ - x₂| / a, |y₁ - y₂| / b).

Посчитаем это для всех четырех углов и выберем максимум, либо определим, что добраться не возможно.

374B — Инна и девять

Очевидно, что мы можем разбить задачу на подзадачи, так как если рядом не стоят цифры с суммой 9, то число будет независимо изменяться, относительно позиции между этими числами. Это значит, что мы разделим задачу на подзадачи вида x либо xyxyxyx...xyxy причем x + y = 9. Ответ для таких отрезков нужно будет перемножить, так как мы ищем общее количество вариантов.

Для x ответ 1. Что же делать с xyxyxy? Пусть длинна ее s. Тогда, если s парное, мы однозначно получаем s / 2 девяток. Если же s не парное, одна цифра (причем любая) останется. Таким образом каждая последовательность xyxyxyxyx...xyxyxy непарной длинны s увеличивает ответ в s / 2 + 1 раз.

374C — Инна и Дима

По сути, задача сводится к нахождению цикла и поиску максимального пути, однако, решим ее без построения графа.

Запустим обход в глубину из каждой буквы D, запоминая уже обработанные позиции. Если мы попали в позицию, в которой уже были раньше (зашли в нее обходом из других D) тогда можем просто прибавить длину текущего пути к длине максимального пути из этой позиции. Длина пути, заметьте, растет нe с каждый переходом, а только с переходом в букву A. Если же мы попали в позицию, помеченную номером нашей буквы D (из которой мы начали), значит, имеет место цикл, и поиски можно заканчивать. Не забудьте также менять цвет позиции при выходе из рекурсии, иначе будет "ложный цикл", таким образом, помеченными "нашим" цветом должны быть только позиции, в которые мы зашли рекурсивно, но еще не вышли.

374D — Инна и последовательность

Заметим, что всего будет добавлено не более n чисел, а следовательно вылетов тоже будет не более n. Будем имитировать процесс с помощью структур данных, к примеру, деревом отрезков (можно и другими). Будем поддерживать количество чисел, которое есть на подотрезке. Соответственно добавление — спускаемся от корня до листа, увеличивая на единичку значения. Удаление — с точностью до наоборот. Если в левом поддереве не достаточно элементов, спускаемся в правое, иначе — в левой. Не забудьте также смещать позицию дырки на ее номер (так как вылеты у нас моментальные из всех дырок) и останавливать цикл при достижении первой дырки, позиция которой больше текущего количества элементов.

374E — Инна и пупсики

Будем делать бинпоиск по ответу (очевидно, что функция монотонная). Для каждого времени генерируем наши отрезки, и повернем их на 45 градусов так, чтобы они стали вертикальными и горизонтальными. Это можно сделать заменой (x, y) — (x + y, x - y). Не забудьте слить отрезки, стоящие на одной диагонали и имеющие пересечения в один. Для этого нужно отсортировать все отрезки, и пройтись подряд, обновляя правую или нижнюю границу соответственного отрезка. Теперь осталось проверить, можно ли из текущих отрезков сложить прямоугольник. К примеру, можно перебирать левый вертикальный отрезок, поддерживая множество всех горизонтальных, которые начинаются не позже него, затем, для каждого левого вертикального перебирать правый вертикальный, поддерживая уже множество горизонтальных, которые начинаются не позже левого, но и заканчиваются не раньше правого. Теперь осталось только убедится, что есть хотя бы два горизонтальных отрезка из множества, которые, к тому же удовлетворяют еще и неравенство по y-кам.