Предлагаю здесь обсуждать задачи.
Предлагаю здесь обсуждать задачи.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3857 |
| 2 | jiangly | 3810 |
| 3 | maroonrk | 3534 |
| 4 | tourist | 3528 |
| 5 | Kevin114514 | 3510 |
| 6 | turmax | 3411 |
| 7 | Um_nik | 3387 |
| 8 | Radewoosh | 3367 |
| 9 | heuristica | 3322 |
| 10 | strapple | 3317 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | maspy | 150 |
| 3 | Um_nik | 144 |
| 3 | nik_exists | 144 |
| 5 | Errichto | 139 |
| 6 | adamant | 136 |
| 7 | maroonrk | 134 |
| 8 | DNR | 132 |
| 9 | AmShZ | 131 |
| 10 | Dominater069 | 129 |
Задача 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. Кажется, так можно делать.