Задача A. Командная олимпиада.

Идея: Виталий Аксенов.
Реализация: Андрей Комаров.
Разбор: Виталий Аксенов.

Самое логичное в задаче сразу перебрать количество задач первого типа, которые решил Вася. Пусть он решил vn задач первого типа, тогда очевидно, что максимальное количество задач второго типа vm, которое мог решить Вася за олимпиаду, равно (n-vn·p)/q. Итого, у нас осталось n-vn задач первого типа и m — vm задач второго. Нужно не забыть сравнить эти количество с нулём.

Посчитаем, какое максимальное число задач первого типа и второго типа можно решить за олимпиаду. Первого типа получается maxn=t/p, а второго типа — maxm=t/q. Благодаря подсчитанным значениям, несложно уже посчитать ответ: 1 + (n — vn + maxn — 1) / maxn + (m — vm + maxm — 1) / maxm.

Задача B. Три ладьи.

Идея: Георгий Корнеев.
Реализация: Демид Кучеренко.
Разбор: Виталий Аксенов.

Заметим, что расставлять ладьи можно только в квадрате 3 на 3. Любая другая расстановка сводится к этой переносом ладей. Существует два различных решения. Первое из которых просто перебирает все возможные расстановки трёх ладей в квадрате 3 на 3.

Либо можно рассмотреть все различные варианты взаимных расстановок 3 ладей:

• (1, 1), (2, 2), (3, 3). Бьют 3 · n + 3 · m — 12 клеток.
• (1, 1), (1, 2), (2, 3). Бьют 2 · m + 3 · n — 9 клеток.
• (1, 1), (2, 1), (3, 2). Бьют 3 · m + 2 · n — 9 клеток.
• (1, 1), (1, 2), (2, 1). Бьют 2 · n + 2 · m — 7 клеток.
• (1, 1), (1, 2), (1, 3). Бьют m + 3 · n — 6 клеток.
• (1, 1), (2, 1), (3, 1). Бьют n + 3 · m- 6 клеток.

Во всех других случаях нужно выводить «IMPOSSIBLE».

Задача C. Король и королева.

Идея: Виталий Демьянюк.
Реализация: Павел Кротков.
Разбор: Павел Кротков.

Заметим, что максимальное количество регионов на доске равно восьми. Научимся находить размер одного из них, а размеры всех остальных найдем, отразив и повернув доску несколько раз.

Пусть королева стоит в клетке с координатами (x, y), строки и столбцы нумеруются с нуля, и мы хотим научиться находить размер региона, расположенного левее вертикали, на которой расположен ферзь, и выше диагонального луча, выпущенного налево вверх из клетки, в которой стоит королева. Заметим, что в случае, если этот луч упирается в верхний край доски (x ≥ y) , то ответом будет являться сумма всех чисел от одного до x — 1. В противном же случае из этой величины необходимо вычесть количество клеток, которые были бы биты королевой, если бы не край доски. Количество таких клеток равно сумме всех чисел от одного до x-y-1.

Задача D. Дерево.

Идея: Анна Малова.
Реализация: Артём Васильев.
Разбор: Виталий Аксёнов.

Дано дерево, которое нужно получить из одной вершины двумя операциями: отрезать ребро и добавить 2 вершины к листу. Чтобы решить данную задачу первым делом проверим, есть ли вершина степени не менее 4. Если она есть, то дерево получить нельзя.

В любом другом случае дерево построить можно. Для этого посчитаем количество вершин v2 степени 2 и v3 степени 3. Если есть вершина степени 2, то при выборе её начальной мы построим дерево за (v2 — 1)·2+(v3 + 1), иначе число действий равно (v2 + 1)·2+v3. Это верно потому что для получения внутренней вершину степени 3, нужно применить одну операцию второго типа, а для получения внутренней вершины степени 2 нужно применить 2 операции.

Задача E. Налог на проезд.

Идея: Борис Минаев.
Реализация: Борис Минаев.
Разбор: Борис Минаев.

Заметим, что полученный от налогов доход всегда четен, так как для любой пары городов существует два жителя, которые собираются проехать по пути, который их соединяет.

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

Посчитаем доход, который получит президент, если на всех дорогах цены на проезд будут минимально возможными. Вычтем эту сумму из необходимой. Если мы получили отрицательное число, то не существует ни одного удовлетворяющего набора налогов. Заметим, что если мы получили неотрицательное число, то общее количество дорог не превышает 600.

Теперь нам необходимо решить некоторую модификацию задачи о рюкзаке. Она решается методом динамического программирования. Будем рассматривать все дороги по очереди. Также будем поддерживать количество способов собрать некоторую сумму денег, используя только некоторый префикс дорог. Рассмотрим более подробно, как обрабатывать очередную дорогу. Пусть увеличение налога на проезд по этой дороге добавляет c денежных единиц в общую прибыль, а цена за проезд по дороге может находится в пределах от 0 до max. Как узнать, сколько существует способов получить суммарный доход ровно m? На самом деле это количество совпадает с количеством способов получить суммарную прибыль m — c за исключением двух слагаемых. Эти слагаемые соответствует тому, что мы можем назначить стоимость проезда равную 0, но не можем max + 1. То есть каждое значение динамического программирования можно посчитать с помощью трех уже посчитанных значений. Таким образом, очередную дорогу можно обработать за O(MAX), где MAX — прибыль, которую хочет получить президент.