В воскресенье 18 мая прошел второй квалификационный раунд RCC 2014. На участие в раунде зарегистрировалось 5451 человек, приняло участие более 1500, из них хотя бы одно решение прислали 886 участников. Всего в течение раунда было прислано 4890 решений.
Короткевич Геннадий (tourist), один из победителей RCC 2013, уверенно занял первую строчку в таблице участников 2-го квалификационного раунда, решив все 5 задач с наименьшим штрафным временем. Также Геннадий первым из всех участников раунда решил задачи A, В, С и Е на 4:22, 9:40, 16:25 и 50:29 минутах соответственно. Первым на 30:17 минуте задачу D решил Сутыгин Дмитрий (morojenoe). По итогам 2 квалификационного раунда 200 лучших спортивных программистов перешли в отборочный раунд, а 11 человек были дисквалифицированы судьями за списывание.
Участники, не прошедшие квалификацию в первых двух раундах, могут принять участие в 3-м и 4-м квалификационных раундах, которые состоятся 24 мая в 19:00 и 1 июня в 13:00 по московскому времени.
Напоминаем, для того чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте (регистрация будет открыта до начала последнего квалификационного раунда).
Задача 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), то ответом будет являться сумма всех чисел от 1 до x — 1. В противном случае из этой величины необходимо вычесть количество клеток, которые были бы биты королевой, если бы не край доски. Количество таких клеток равно сумме всех чисел от 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 — прибыль, которую хочет получить президент.
Автор: TeamMRG
