Предлагаю здесь обсуждать задачи.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
07:13:17
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
07:13:17
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 10:21:44 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Задача A. Подскажите пожалуйста, в чём ошибка (WA5):
// код под спойлером
Общая идея: классическая задача отображения доски на всю плоскость; переберём все возможные доски, так, чтобы количество пересечений прямой (между первой точкой и отражением второй) с прямыми — границами доски было равно n. Ну и выберем из всем таких минимум.
может потому что не предусмотрел случай когда прямая проходит через какие либо точки пересечения горизонтальной и вертикальной прямой, тогда нужно же это количество отнять от общего количества пересечений
В условии сказано, что углы за два пересечения считаются.
Нужно еще проверять, что вы не пересекли цель ранее, чем сделав n отражений. Тест: 4 4 2 2 3 3 2
Блииин :( Спасибо!
Думаю, то же, что и у меня: отрезок не должен проходить через точку финиша несколько раз (читаем условие внимательно, ага).
Задача B. Кто-нибудь ловил WA13? (вопрос решён, мой косяк)
Вроде всё норм делаю: вначале скалываю все разряды, потом пробегаю от младших к старшим и если текущий (i) и предыдущий (i-1) разряды больше 0, то увеличиваю следующий (i+1) разряд и уменьшаю текущий (i) и предыдущий (i-1), передвигаю текущий счётчик на 3 назад (на всякий случай), если текущая (i) ячейка больше 1, то уменьшаю её на два, следующую (i+1) ячейку увеличиваю на 1 и увеличиваю предпредыдущую (i-2) на 1, при этом если i=0, то не делаю увеличение (i-2) ячейки, а если i=1, то увеличиваю предыдущую (i-1) ячейку, и в этом случае тоже передвигаю на 3 назад на всякий случай, ну и конечно проверяю, чтобы i не стало равно 0 (всё, тут и понятно стало.. далее цикл идёт и увеличивает i на 1, пропуская случай, когда 0-ая ячейка стала равна 2).
Оказалось, что по TLE проходит такой алгоритм (by Slamur):
А почему так плохо порешали задачу D? Она же вроде простая совсем. Конечно набор задач и шраф у меня в результате совсем дурацкий получился. За упавшую B обидно.
Честно, не успел даже прочитать. Условие показалось мутным с этими действительными числами.
А как решалась, расскажи пожалуйста.
Оптимально, наверное, толпой одного бить, а неоптимально — бить почти до конца и перед последним выстрелом переключаться на другого. Конечно, из-за большого количества вложенных тестов просто так не смоделируешь...
E. Fleet of Byteland
Что-то совсем не могу найти баг в своем решении. Есть у кого идеи?
И такой вопрос — кто как обходил то, что 2 * k не влазит в unsigned long long или такого теста не было?
Там, вроде, количество всегда меньше К.
Да? А тест из 50 тире... есть 1, 2, 3 и 4 тире, то есть получается Фибоначчи с суммой последних четырех, а это точно не влезет...
Да там-же 2^50 < 2^63, даже если взять все разбиения строки.
Кажется это не совсем правильная логика, ибо по данному утверждению строк вида ?? будет 4, а при условии что ещё могут быть отдельные двойные символы, таких строк будет 8
Разве общее кол-во разбиений(не важно какой длины) не будет меньше-равно 2^50? Ведь мы либо клеим символ к предыдущему, либо создаем новую строку. Это в любом случае кол-во не меньше чем то, что нам нужно, вроде.
Да, действительно. Что-то я не то подумал.
Не вижу ничего плохого в этой логике. 2^50 — количество способов разбить строку длины 51 на подстроки.
хм, действительно, что-то меня понесло...
Видимо таких тестов нет, ибо у меня зашло без учёта переполнения за лонг лонг. Ошибка в другом.
На Java с long тоже зашло, хотя там 2^63 не влезает. Такого теста не было.
Тест: "...." 2
EEI, нет?
Ой.. Блин, верно. Какой-то косяк. Ща подберу.. я просто сверяю со своим AC.
Во:
.--.8 Ответ: "WE", а у тебя 0Ну и косяк в этом пробеле
вот же, хотел написать регекспу, которая пробелы завершающие поубирала, да посмотрел что нигде вроде нет такого... Огромное спасибо
И ещё вопрос: почему ты f не memset`ишь? Когда массив глобально объявляется, он сам обязательно нулями заполняется?
Я живу с мыслью что сам)
конечно сам, даже если у вас есть структура и в ней массив, и вы объявляете элемент структуры глобально, этот массив обнуляется
Спасибо за тест, нашёл баг и в своём решении.
Если значение динамки на каком-то этапе становилось больше чем 2^63, я делал его равным 2^63 и больше ничего не прибавлял. Таким образом, в сложении учавствовало два числа, одно из кторых строго меньше чем 2^63, а второе — не больше чем 2^63, значит сумма <=2^64-1. Кажется, так можно делать.