Добрый день, дорогие пользователи Codeforces!
9 ноября начался заочный этап XIV Открытой олимпиады школьников по программированию. В контест уже добавлены все задачи!
Те из вас, кто знает что такое Открытая олимпиада (она же "заочка") и её правила, могут не читать дальше и сразу переходить на сайт олимпиады :)
Те, кто раньше в данной олимпиаде не участвовал, могут так же пойти на сайт и прочитать полную информацию там, а в этом посте будут обозначены лишь основные моменты. Олимпиада состоит из трёх этапов: длинного заочного тура, короткого заочного тура и очного.
Длинный тур заочного этапа проходит с 9 ноября по 15 января, и традиционно состоит из 10 задач различной сложности, тематики и формата. Мы подбираем задачи таким образом, чтобы они были интересны как совсем новичкам, так и "зубрам" олимпиадной информатики. Лучшие $$$n$$$ участников будут сразу приглашены на очный этап олимпиады. Следующие $$$k$$$ участников будут приглашены на короткий тур.
Короткий тур заочного этапа проходит с 24 по 27 января в формате пятичасового виртуального контеста. Это означает, что в течение этих четырёх дней каждый участник должен выбрать пять часов и написать тур в режиме реального соревнования. Итоговый список приглашённых на очный этап формируется именно по сумме баллов в двух турах, кроме участников, приглашённых непосредственно по результатам длинного тура.
Очный этап пройдёт в Москве, ориентировочные даты проведения — 5-7 марта. Площадка проведения — учебный центр нашего генерального спонсора 1С на м. Тимирязевская. Также, благодаря нашему спонсору, участникам оплачивается проживание в гостинице на время проведения олимпиады. Очный этап состоит из двух туров, уровень участников немного превосходит уровень Всероссийской олимпиады по информатике за счёт приезда сильных школьников из ближнего зарубежья. Возможно это прозвучит слишком пафосно, но на наш вкус качество задач олимпиады в последние годы превосходит Всероссийскую олимпиаду и сравнимо с IOI. Олимпиада имеет первый уровень и даёт соответствующие льготы при поступлении.
Призеры заочного этапа олимпиады никаких льгот не имеют — поступить, не выходя из дома, всё-таки не получится.
Для тех, кто не является школьником и хочет просто порешать задачи, доступно внеконкурсное участие.
Жюри олимпиады призывает всех участников действовать честно, не обсуждать друг с другом решения задач длинного и не делиться написанным кодом до окончания тура. Так же Особенно хотим отметить, что любое обсуждение задач запрещено, в частности, и в комментариях на Codeforces (в том числе, и к этому посту). Все интересующие вас вопросы по задачам вы можете и должны задавать через тестирующую систему. К сожалению, каждый год некоторые участники заочного этапа не допускаются к участию в очном этапе из-за выявления случаев списывания с их участием.
Любые оставшиеся вопросы смело задавайте в комментариях.
Задачи длинного тура, под руководством vintage_Vlad_Makeev, ch_egor, для вас готовили:
A) Автор идеи vintage_Vlad_Makeev, подготовил ch_egor.
B) Автор идеи vintage_Vlad_Makeev, подготовил KiKoS.
C) Автор идеи V--o_o--V, подготовил voidmax.
D) Автор идеи V--o_o--V, подготовил ch_egor.
E) Авторы идеи meshanya, vintage_Vlad_Makeev, ch_egor, подготовил ch_egor.
F) Автор идеи glebushka98, подготовили GreenGrape, Sehnsucht.
G) Автор идеи vintage_Vlad_Makeev, подготовил cdkrot.
H) Авторы идеи vintage_Vlad_Makeev, vintage_Vlad_Makeev, подготовил Sehnsucht.
I) Автор идеи и разработчик voidmax.
J) Автор идеи и разработчик isaf27.
UPD1:
Длинный тур закончился, доступны предварительные результаты длинного отборочного тура. Результаты будут объявлены окончательными после проведения проверки на списывание.
Решением жюри на очный тур соревнований приглашаются все конкурсные участники, набравшие в длинном отборочном туре не менее 800 баллов. Конкурсные участники, набравшие не менее 350 и не более 799 баллов, приглашаются к участию в коротком отборочном туре. Напоминаем что короткий тур пройдет с 24 по 27 января в формате пятичасового виртуального контеста.
После окончания короткого тура будет организовано отдельное соревнование, в котором могут принять участие все желающие написать короткий тур вне конкурса.
UPD2:
Опубликовано описание правил короткого тура и ссылка на вход в соревнование. Если вы проходите на короткий тур по указанным выше границам баллов, но не можете зайти в соревнования — напишите об этом в оргкомитет.
Начать виртуальный тур можно будет с 00:00:00 24 января до 23:59:59 27 января (московское время).
Wow, such vintage_Vlad_Makeev so vintage_Vlad_Makeev very vintage_Vlad_Makeev
And vintage_Vlad_Makeev also!
Огромное спасибо voidmax за задачу I :)
Одобряю
Самая топовая задача среди всех, на мой взгляд)
Лучшая олимпиада.
Будет ли разбор?
Как решать F и H?
H: Заметим, что любое число, которое можно получить на калькуляторе, описанном в условии задачи, делится на $$$p_i$$$. Тогда, мы можем проверить делимость $$$n$$$ на $$$p_i$$$, разделить его на $$$p_i$$$ и свести задачу к случаю, когда $$$p_i$$$ = $$$1$$$.
Понятно, что в этом случае число $$$n$$$ можно получить хоть как-то, например разложим его в системе счисления с основанием $$$q_i$$$. Тогда количество умножений, которое нужно использовать, равняется максимальной степени числа $$$q_i$$$ в разложении. Разберёмся в начале с условием на число умножений. Если их было использовано больше, чем $$$b_i$$$, то необходимо какие-то старшие степени убрать, заменив их на $$$q_i$$$ копий степени на 1 меньше. А именно, давайте пока старшая степень больше чем $$$b_i$$$, будем заменять её на $$$q_i$$$ раз сложенную степень на 1 меньше.
Отметим, что если умножений было использовано меньше, чем $$$b_i$$$, то ответ всё равно существует — достаточно лишь дописать нужные умножения в начало ответа, каждый раз домножая ноль на что-то.
Теперь мы получили какое-то разложение числа, которое использует не больше $$$b_i$$$ умножений и наименьшее число сложений, назовём такое разложение — базовым. Если в нём сложений больше чем $$$a_i$$$, то ответ на задачу No. Проверим, можем ли мы сделать ровно $$$a$$$ сложений.
Наибольшое возможное число использованных операций сложения — $$$n$$$. Если $$$a$$$ больше $$$n$$$, то ответ $$$No$$$.
Посмотрим, как возможно увеличить число использований операции $$$+$$$, в сравнении с базовым ответом. Мы можем заменить какой-то член суммы на $$$q_i$$$ копий со степенью на 1 меньше. Заметим, что каждая такая операция увеличивает число использований операции плюс на $$$q_i - 1$$$. Тогда, $$$a_i$$$ должно иметь такой же остаток по модулю $$$q_i - 1$$$, как и наше базовое разложение.
Если это не выполняется, то ответ $$$No$$$, а иначе $$$Yes$$$.
Соревнования имеют гораздо большую пользу когда к ним можно увидеть разборы, а так получается кто умеет решать тот решает, кто не умеет — не решает. Образовательный эффект нулевой.
Я, наверное, слишком поздно пишу об этом, но всё же: где-нибудь можно сделать дорешивание задач заочного этапа?