Пару дней назад завершился заочный этап Открытой олимпиады по программированию, результаты уже известны, и вы можете порадоваться собственным результатам в тестирующей системе. Тем временем, мы решили восстановить славную традицию Московских Олимпиад публиковать текстовый разбор задач, в результате чего вашим покорным слугой был составлен следующий документ: Разбор!
Обсуждение решений задач и вопросы к жюри можно продолжить в комментариях к этому посту.
Int128 был доступен на контесте? Иначе метод Лемана, Полларда не катил бы на с++. А на питоне Лемана не заходил
Во-первых, длинка на C++ заходит (я Полларда писал).
Во-вторых, особые волшебники умеют складывать unsigned long long по модулю. Например, можно сложить с переполнением, если результат получился меньше слагаемых, то переполнение действительно произошло, иначе — нет. А если можно складывать, то умножать можно бинарным умножением (как возведение в степень, только умножение).
Задачи отличные и интересные... Прочитал разбор и узнал очень много... Если честно в первый раз написал такой контест с частичными баллами(если не понимаешь как решать на 100, а ну-ка попробуй сначала на 50, а вось потом поймешь как на 100 решать). Очень понравились задачи G(решил на 80) и F(решил на 60). Ну в прочем в сумме набрал 791 и считаю, что неплохо для новичка...Спасибо авторам за замечательные задачи и отличный разбор!!!
У меня есть вопрос по поводу задачи 7 олимпиады. Допустим, у нас в очереди Х человек. Между каждыми двумя встало по А человек.
Тогда (Х — 1) — количество промежутков, куда вставали люди, а (Х — 1) * A — всего количество добавленных. Значит, теперь в очереди станет
Х + (Х — 1) * А человек, а отнюдь не 1 + (Х — 1) * А, как у вас написано.
Может быть так:
X + (X - 1) * A
<=>
X - 1 + (X - 1) * A + 1
<=>
(X - 1) * (A + 1) + 1
Ну хорошо. Видите, все равно формула другая, чем в разборе.
Исправили.
А будет ли эта олимпиада выложена в раздел ТРЕНИРОВКИ на Codeforces?