Разбор задач 3-го квалификационного раунда Russian Code Cup 2015
В воскресенье 31 мая прошел последний 3-й квалификационный раунд RCC 2015. Первым за 1 минуту и 49 секунд решил задачу A (Покупка велосипеда) Григорий Резников (grikukan), он же раньше всех справился с задачами B (Цифровые корни) и C (Две улитки) — 7:26 и 18:39 соответственно. Адам Бардашевич (subscriber) раньше всех решил задачу D (Игровые автоматы) за 14 минут и 20 секунд.
Олег Меркурьев (Merkurev) стал первым при решении последней задачи E (Интернетопровод) — 1 час и 1 минута. По итогам 3-го раунда первую строчку в турнирной таблице занял Евстропов Глеб (GlebsHP) из Москвы.
Немного фактов: в раунде сразились 3762 программиста, из них хотя бы одно правильное решение прислали 664. Всего за раунд было прислано 3536 решений. 202 лучших участника было квалифицировано (200-е место поделили 3 участника). 3 участника были дисквалифицированы жюри. 604 участника, прошедшие квалификацию в трех раундах, сразятся 14 июня за звание финалиста. Все участники отборочного раунда получат онлайн-сертификаты, а 200 лучших из них получат футболки RCC 2015.
Идея: Виталий АксёновРеализация: Дмитрий ФилипповРазбор: Дмитрий ФилипповПо условию задачи нужно сказать, можно ли по данным числам a, b, c найти такие числа a1, b1, что a1 ≤ a, b1 ≤ b и a1 + 2 · b1 = c.
Решение у этой задачи простое: почти всегда достаточно проверить, что суммарный номинал наших монет не меньше c: a + 2 · b ≥ c. Исключение — когда c нечётное. Тогда ещё нужно проверить, что a ≥ 1.
Идея: Григорий ШовкоплясРеализация: Григорий ШовкоплясРазбор: Григорий ШовкоплясВ этой задаче нужно по числам a и b определить, какие из значений цифрового корня встретятся на этом отрезке наибольшее количество раз. Заметим, что у цифрового всего девять значений, а также они циклически повторяются. Таким образом, нужно вычислить только цифровые корни от a и b, а чаще всего встречаются цифры между значениями этих цифровых корней. Единственное, что нужно было дополнительно учесть — это случай, когда цифровой корень a больше, чем цифровой корень b. Также нужно было не забыть, что ответ нужно выводить по возрастанию.
Идея: Дмитрий ФилипповРеализация: Николай ВедерниковРазбор: Николай ВедерниковВ этой задаче две улитки днём поднимаются на ai, а ночью опускаются на bi. Требуется определить, сколько по времени первая улитка обгоняла вторую. Задача решается моделированием. Рассматриваем часы последовательно. Для начала узнаем, сейчас день или ночь. Посмотрим положение улиток до начала этого часа и после. Если до начала часа одна была выше другой, а после окончания часа также была выше, то обгона не было. Тогда, если выше была первая, то к ответу добавим один час. Если же в начале часа была выше, а потом ниже, следовательно, одна обогнала другую. Для того чтобы узнать время, когда одна обгонит другую, надо посчитать расстояния между ними и поделить на разницу скоростей. После этого добавить к ответу время, когда первая улитка была выше второй в этот час.
Идея: Анна МаловаРеализация: Виталий АксёновРазбор: Виталий АксёновНам даны кнопки, которые умеют выключать какой-то набор из лампочек, и кнопки, которые умеют включать какой-то набор лампочек. Задача: с помощью кнопок перевести лампочки из выключенного состояния в заданное или сообщить, что такое сделать нельзя.
Сначала поймём, что дважды нажимать одну и ту же кнопку не имеет смысла, так как мы всегда можем оставить только последнее её нажатие, и конечное состояние не изменится. Далее рассмотрим задачу с конца. У каждой лампочки будет три состояния: включена, выключена и неизвестно. Когда мы обращаем нажатие кнопки, помечаем все лампочки, которые изменили состояние, что их состояние неизвестно.
Мы могли нажимать кнопку, если:
кнопка выключает лампочки, то состояния изменённых лампочек должны быть или выключены, или неизвестны; кнопка включает лампочки, то состояния изменённых лампочек должны быть или включены, или неизвестны. Смотрим на последнее состояние и нажимаем кнопки (каждую по одному разу, если это возможно). Пусть ни одну кнопку нажать нельзя, тогда нужно проверить, действительно ли лампочки или выключены, или неизвестны, что соответствует стартовому состоянию. Если правда, мы можем последовательностью нажатий перейти в заданное состояние, иначе — нельзя. Идея: Виталий АксёновРеализация: Илья ЗбаньРазбор: Илья ЗбаньВ задаче дано n точек, и нужно найти некоторую прямую l и расстояние d такие, что количество точек, расположенных ровно на расстоянии d от прямой l, было бы максимальным.
Любая прямая задается тройкой коэффициентов a, b и c таких, что ax+by+c=0. Две прямые (a1, b1, c1) и (a2, b2, c2) параллельны, если коллинеарны векторы (a1, b1) и (a2, b2).
Проведем прямые через все пары точек и приведем их к нормальному виду: GCD (a, b)=1, и a>0 или a=0 и b>0. Такое представление единственно для любой прямой. Перебрав все прямые, проходящие через пару точек, мы получим все углы, под которыми есть смысл проводить прямую-ответ (в случае, когда ответ больше двух, какие-то две точки из ответа будут лежать на одной прямой). Зная угол, под которым проходит прямая-ответ, несложно указать оптимальное d: для фиксированных a, b, задающих угол наклона прямой, нужно выбрать два самых часто встречаемых с этими значениями a, b значения c, и мы получим две прямые, параллельные искомой, находящиеся от нее на расстоянии d. В случае если такое значение c всего одно, то если не все точки лежат на одной прямой, можно добавить к ответу еще одну точку.
