В субботу 24 мая прошел третий квалификационный раунд RCC 2014. На участие в раунде зарегистрировалось 5483 человека, приняло участие более 1500, из них хотя бы одно решение прислали 893 участника.
Прищенко Богдан (LeBron), студент Львовского национального университета им. Ивана Франко, первым на 2:25 минуте решил задачу А (Треугольники). Задачу В (Оригами) на 4:44 минуте первым решил Юлдашев Марат (snowbear), задачу С (Митя и граф) первым на 10:34 минуте решил Ахмедов Максим (Zlobober), правильное решение задачи D (Призы) на 26:45 минуте прислал Копелиович Сергей (Burunduk1), а последнюю задачу E (Криптостойкие ключи) быстрее всех решил Пономарев Павел (pperm) на 54:38 минуте.
По итогам 3 квалификационного раунда не было ни одной дисквалификации за списывание, а 200 лучших спортивных программистов перешли в отборочный раунд.
Участники, не прошедшие квалификацию в течение прошедших трех квалификационных раундов, еще имеют возможность пройти в отборочный раунд, приняв участие в четвертом квалификационом раунде, который состоится 1 июня в 13:00 по московскому времени.
Напоминаем, для того, чтобы принять участие в Russian Code Cup, нужно зарегистрироваться на сайте (регистрация будет открыта до начала последнего квалификационного раунда).
Еще в преддверии третьего раунда мы обновили версии компиляторов почти всех языков программирования, использующихся в RCC. Добавили возможность отправлять решения на C++11 под GNU C++ (Visual C++ 2013 и так поддерживает C++11) и добавили Java 8 (Java 7 тоже пока остается). Актуальные версии компиляторов и строки компиляции вы можете посмотреть на странице с правилами чемпионата <www.russiancodecup.ru/rules/>.
Задача А. Треугольники.
Идея: Андрей Станкевич.
Реализация: Анна Малова.
Разбор: Анна Малова.
В задаче требуется определить количество треугольников каждого типа, которые можно составить из четырех отрезков.
Переберем все возможные тройки отрезков. Из трех отрезков можно составить треугольник, если выполнено неравенство треугольника, то есть сумма любых двух сторон больше длины третьей стороны.
Рассмотрим отрезки a, b, c в порядке возрастания длины. Если выполнено равенство c2 = a2 + b2, то треугольник является прямоугольным, если c2 < a2 + b2 — остроугольным, и если c2 > a2 + b2 — тупоугольным
Задача B. Оригами.
Идея: Георгий Корнеев.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.
В задаче требуется проверить, существует ли в прямоугольнике a на b подпрямоугольник площадью S, у которого стороны параллельны исходным.
Для этого переберём все x-делители числа S и проверим, является ли x ≤ a и S ⁄ x ≤ b. Если существует хотя бы одна такая пара x и S ⁄ x, удовлетворяющие ограничениям, то решение существует.
Время работы на один тестовый случай O(sqrt(S)).
Задача C. Митя и граф.
Идея: Жюри.
Реализация: Виталик Аксёнов.
Разбор: Виталик Аксёнов.
Первое наблюдение заключается в следующем: граф должен быть рёберным кактусом. Если он не получился таковым, то обязательно найдётся чётный цикл. Раз это кактус, то количество циклов равно m — (n — 1). А так как каждый цикл содержит в себе минимум 3 вершины, то 3·(m — (n — 1)) ≤ m. Отсюда получаем, что максимальное число рёбер равно 3·(n — 1) / 2.
При нечётных n это мельница, то есть набор циклов длины 3, пересекающихся по 1 вершине, а при нечётных n почти то же самое, но еще одна висячая вершина соединена ребром с любой другой.
Задача D. Призы.
Идея: Виталик Аксёнов.
Реализация: Виталик Аксёнов.
Разбор: Виталик Аксёнов.
Мы знаем, что количества конфет, выданных участникам, должны убывать в зависимости от номера группы. Несложно убедиться, что любое удовлетворяющее разбиение конфет можно представить следующим способом:
В первой группе дети получают n конфет, во второй — n-1 конфет, ..., в последней — 1 конфету. Далее мы можем прибавлять по одной конфете всем детям на префиксе групп. Это значит, что мы можем выбрать число p и увеличить ai на единицу для любого i ≤ p.
Так как мы выбрали изначальное распределение, то из общего числа конфет можно сразу вычесть n·a1+...+1·an. Несложно заметить, что операция распределения вычитает bp = a1+...+ap. То есть нам надо проверить, можем ли мы представить d в виде какой-то суммы b1, ..., bn, а это стандартная задача про рюкзак.
Время работы O(nd).
Задача Е. Криптостойкие ключи.
Идея: Виталий Демьянюк.
Реализация: Виталий Демьянюк.
Разбор: Виталий Демьянюк.
Дано множество чисел a1, a2, ..., an. Его замкнули относительно операций НОД и НОК. Требуется выяснить, принадлежит ли заданное число v замкнутому множеству S.
Представим v в виде p1q1p2q2… pkqk, q i > 0, где p1, p2, ..., pk — простые числа. Чтобы v принадлежало S, необходимо, чтобы для каждого i, 1 ≤ i ≤ k существовало j, 1 ≤ j ≤ n, такое, что piqi ∣aj и piqi+1 ∤aj. Этот факт следует из того, что мы можем любое число представить в виде НОК(НОД(...), НОД(...), ..., НОД(...)), так как min(a, max(b, c)) = max(min(a, b), min(a, c)) и max(a, min(b, c)) = min(max(a, b), max(a, c)). Положим ci равным наибольшему общему делителю чисел aj, таких что piqi ∣aj. Если все ci делят v, то v принадлежит S. Оно может быть получено как наименьшее общее кратное всех ci. В противном случае v не принадлежит S (это следует из свойств операций НОД и НОК).
Время работы O(nk + sqrt(v) ), где k — количество простых делителей числа v.
Автор: TeamMRG
