Предлагаю здесь обсуждать задачи.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
Предлагаю здесь обсуждать задачи.
Название |
---|
Задача 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. Кажется, так можно делать.