Странно, что еще нет этой темы, ведь соревнование уже почти началось.
Надеюсь вы не забыли и уже готовитесь его написать. Удачи.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
25:27:40
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
25:27:40
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 16:07:21 (l2).
Десктопная версия, переключиться на мобильную.
При поддержке
Так все-таки, сколько будет идти контест? В системе 5 часов, а по идее должно быть 3 часа?
уже исправили
объясните, пожалуйста последние две
Как решать 4ую, 5ую, 6ую?
P.S. И вторую еще, пожалуйста.
я делал 4 так, вроде правильно: найдем все локальные максимумы и минимумы. На все макс. поставим самые большие числа, на миним. самые маленькие. Порядок значения не имеет. На концах надо ставить аккуратно.
Делал примерно так же, 96
120 у меня, это фулл?
PS по зиме 20, печалька
Да, это фулл
У меня тоже по зиме 20 :( Даже непонятно из-за чего.
как делали? Я двумя фенвиками сначала плюсовал отрезки, которые надо считать. Потом пробовал каждый из макс. отрезков увеличить до 3Т и выбирал тот, где больше всего не отмеченных клеток.
Делал по-тупому, за O(N).
P.S. Попозже расскажу.
Порядок имеет значение в одном месте — на краях. Поскольку крайние числа войдут в сумму только один раз, то туда надо ставить наименьшие из группы наибольших (для максимума) и наибольшие из группы наименьших (для минимума).
да, я так и написал, что особенного внимания стоят только края
Тогда ещё можно обломаться на заполнении неэкстремумов, а так вроде всё то же самое — 120.
Моё решение 5й (из-за бага не взяло 3 группы, потом допилил):
На самом деле, задача — найти N-ое число, у которого при разложении нет простых сомножителей < P. Поскольку все числа, которые интересуют нас представимы в форме P * X, где Х — не содержит в разложении нет простых сомножителей < P, то найдём такое число и умножим на Р — получим ответ.
Итого, если P >= 19, то можно запустить простое решето для поиска простых чисел (итерации < P, числа до (10^9)/P). Во время влазит. Если P < 19, то у решета период не будет большим (произведение всех простых чисел до Р включительно), и посчитав для периода, можно легко найти нужное.
Для P = 2 и P = 3 — формулки. Для P > 17 — тупой перебор(для каждого числа от P^2, P^2 + 2 * P, P^2 + 4 * P, ... просто смотрим, делится ли оно на какое-нибудь простое меньшее P) Для P = 5, 7, 11, 13, 17 — небольшой предпосчет, и опять же, перебор.
5я у меня так — если p >= 1000, то ответ — произведение p и (n — 1) го простого если считать с p (случай n = 1 разбирается в начале). Просто сгенерируем все эти простые и возьмем n-1 е. Если p < 1000, то будем искать бинарным поиском по ответу, а затем просто дфсом по формуле включения-исключения искать, сколько до данного подходят 6я — будем считать следующий хеш — если токен больше не встречается в строке, то на этом месте ставим 0, иначе расстояние до следующего вхождения. Посчитаем хеши всех подстрок нужной длины и сравним с хешом образца. У меня не прошли 2 последних теста по ML, вот код
double post
По зиме есть у кого 100? Как-то подозрительно...
да, у меня 100
расскажи же, что там такого?
ну незнаю, вроде никаких подвохов.
Для начала вычеркиваем те дни, которые лежать хотя бы в одном интервале 2T. Очевидно что эти дни точно войдут в ответ. Пусть их количество — res. Это можно делать как online за O(N log N), так и offline за O(N).
Теперь посчитаем ДП ff[i] — количество вычеркнутых дней с 1 до N. Тогда для каждого периода наибольшей длины мы сможем узнать сколько не вычеркнутых дней находиться в интервале от 3T до 2T. Запомним максимум. Пусть он равен plus.
Тогда ответ — res + plus.
Осталось это аккуратно написать=)
The time limit for Q5 seems to be very tight :S I wrote PIE + DP but I still got TLE ...
Does anyone have any idea how to do Q6? I think you use something like KMP, but I have trouble trying to construct the recursion.
А тема то была создана мной :)
извиняюсь, что отнял у вас пару единиц вклада, просто я не увидел тему в прямом эфире и решил, что ее нет.