982A - Row

И двух, описанных в условии правил, следует, что рассадка является <<максимальной>> тогда, когда в ней не встречаются две единички рядом или три нолика. Также необходимо аккуратно обработать концы данного ряда — надо проверить, что нельзя посадить человека на самый правый или самый левый стул.

982B - Bus of Characters

Заметим, что финальные пары интроверт-экстраверт определяются однозначно, а также, что с помощью стека, можно восстановить, какой экстраверт к какому интроверту подсядет (заметим, что нолики единички будут образовывать правильную скобочную последовательность). Тогда одним из решений может быть такое:

1. Сортируем массив длин рядов по возрастанию
2. Для каждого интроверта пишем номер очередного свободна ряда и добавляем его в стек
3. Для каждого экстраверта пишем последнее число из стека и удаляем его оттуда

982C - Cut 'em all!

Заметим, что если есть какое-то ребро, которое можно удалить, то мы можем сделать это, без каких-либо последствий. Рассмотрим такое ребро, что в одном из полученных поддеревьев уже точно нельзя удалить больше, а его удаление возможно. Что произойдет, если мы его оставим в дереве? Относительно другого конца ребра четность поддерева не изменилась, что означает, что на дальнейшие удаления это ребро не повлияло. А значит, если мы его удалим, то ответ улучшится. Отсюда следует жадное решение: в дфс-е насчитываем для каждой вершины размер поддерева, включая текущую вершину, и если он четен, то ребро в потомка (если он существует), можно удалить.

982D - Shark

Давайте посортируем массив и будем вставлять числа в порядке сортировки от меньшего к большему. Используя структуру данных "Система непересекающихся множеств" можно легко поддерживать информацию о текущем количестве отрезков, а также используя map внутри функции объединения, и информацию о текущих размерах отрезков (локаций). Тогда остается лишь обновлять ответ, когда это требуется.

982E - Billiard

Если симметрично отражать прямоугольник на плоскости относительно своих сторон, то новая траектория движения шара окажется куда проще. А именно — прямой. Одно из возможных решений такое:

1. Если вектор направлен под углом в 90 градусов к осям, то пишем if-ы.
2. Иначе поворачиваем поле таким образом, чтобы вектор удара стал (1, 1).
3. Выписываем уравнение прямой движения шара —  – 1·x + 1·y + С = 0. Если подставим изначальное положение шара, то найдем коэффициент C.
4. Заметим, что в бессконечно замощенной плоскости координаты любой лузы представимы в виде (k₁·n, k₂·m).
5. Подставим координаты лузы в уравнение прямой шара. Получается диофантово уравнение A·k₁ + B·k₂ = C. Оно разрешимо в случае, если C | gcd(A, B). В противном случае решений нет.
6. Из всех решений данного диофантово уравнения нас интересует наименьшее на положительной полуоси.
7. По найденным k₁, k₂ легко получить координаты соответствующей им лузе
8. Повернуть поле обратно, если требуется.

982F - The Meeting Place Cannot Be Changed