Давайте обсудим задачи. =) Очень интересует геометрия. (5ая задача)
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 2 | atcoder_official | 162 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | nor | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.12.2024 04:42:54 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
у нас там ошибка в 5 знаке была из-за погрешности ((
На ответ влияли только радиус, расстояние от центра сферы до человека, от центра сферы до источника света, и угол между этими лучами. Поэтому мы можем свести задачу к плоской: в (0,0) — центр сферы, в (r1,0) человек, в (r2cos(φ), r2sin(φ)) источник. Угол, под которым из центра выходит луч, проходящий через точку отражения переберем бинопоиском. По нему считается альфа. Бета считается очевидно.
а что делать, если wa2?
Я так понял, что в этом тесте может упасть только по точности. Например, если использовать в бинарном поиске какие-нибудь попытки сравнения с eps. Или, например, если делать условие остановки вещественного бинпоиска вместо фиксированного числа итераций.
делался for(it=0;it<300;++it). ниодного епсилона в коде нет.
Может проблема, когда между векторами тупой угол?
а что это даёт? то, что бинарный поиск нельзя применять?
Можно, просто у меня в баг был в этом, который давал ва2
У нас прошло вот такое:
Нужно учесть случай когда все три точки лежат на одной прямой (вроде 3 тест)
UPD: почти тоже самое, что сверху :)
А можно посмотреть код? Писал то же самое решение, постоянно получал WA2.
У нас было WA3, но, возможно, что проблема та же: аргумент для acos по модулю был больше 1 на 1e-19, что вело к nan.
UPD: Помогло отправить под VS вместо MinGW.
http://pastebin.com/RFhZQx0t A — the observer, B — the light source, C — the center of the circle. a = BC, b = AC, c = AB. Мы перебирали бинпоиском АО (О лежит на АВ) — расстояние от А до пересечения АВ и прямой СI, где I — точка на окружности, через которую отражается луч. Функция для бинпоиска основывается на том, что биссектриса делит сторону в отношении, пропорциональном отношению прилежащих сторон (типа отношение либо меньше одного, либо больше одного)
Ловили WA3, пока не рассмотрели случай А, В, С лежатъ на одной прямой.
Кто как решал, например, задачи 9-ю и про цепную молнию?
Девятая: динамика БФСом. Состояние (до какой вершины дошли, сколько времени провели под солнцем ровно до этого). Кроме очевидных переходов, пытаемся уменьшить время проведённое под солнцем путём прохода по какому-нибудь ребру до тени и обратно.
А как такое бфсом делать вместо Дейкстры? Длины же разные.
Ага. Я неправильно выразился. Получается что-то дейкстро-подобное: достаём из очереди, смотрим все рёбра, если получилось прорелаксировать какое-нибудь состояние, то добавляем его в очередь.
А это случайно не Форда-Беллман с очередью? Я не писап, но ребята говорят у них зашел Форда-Беллман с брэйком.
Пожалуй, нет. Если мне не изменяет память, в Форд-Беллмане на каждой итерации просматриваются все рёбра. А у меня только инцидентные текущей вершине, которая берётся из очереди.
Так это и называется вроде Форд-Беллман с очередью.
А не Левит ли это?..
Его при желании какой-то Бурундук всегда сломать может. Так что, по аксиомам Эскобара — это так себе алгоритм :)
"Если обычный Форд-Беллман не проходит, пишите Форд-Беллмана с брэйком. Если и он не проходит, пишите с очередью."
Бурундук (с)
Я не понимаю. Если видно, что Дейкстра (даже за квадрат) проходит, зачем писать Форда-Беллмана?...
Ну динамика у парней была вроде
dp[V][T] = distance, где V-вершина, Т — изнеможденность. Ну и насколько я понял, они гоняли Форда-Беллмана по ней. Ты не мог бы объяснить свое решение поподробней?Есть состояния (V,T). Мы для каждого состояния знаем, в какие другие мы можем из него попасть, и сколько нам для этого надо пройти (исходя из смысла задачи).
Получается граф на состояниях (V;T). Переход есть, если он есть в динамике, вес равен увеличению distance. Веса неотрицательны, значит Дейкстра работает. Естественно, граф строить явно необязательно.
Обычно в динамике граф зависимостей без циклов, поэтому там всё проще. В данной задаче есть циклы, так что это и динамикой сложно назвать...
Можете скинуть код? Писали ровно это, но упорно ловили WA10
Код
Правда, чуть выше говорят, что если пишешь такой код, то следует опасаться Бурундуков.
Пользуясь случаем, реквестирую метод взлома.
/blog/entry/3793
Тут Бурундук1 как раз советует алгоритм, который отличается от моего только одним ифом.
И даже без этого ифа, у меня не получилось его сломать приведённым генератором.
По ссылкам в той же теме нашёл ещё один метод, но и с ним ничего не получилось.
Вот код
Было бы интересно узнать, как решаются задачи 1, 6 и 7.
6: Если забыть про то, что буквы должны идти в том порядке на ломанной, в котором они идут в слове, то можно просто взять ближайшую точку для каждой буквы. Теперь вспомним про порядок букв. Идея в том, что интересных точек на ломанной мало. А именно, посмотрим на подстроку в строке. Найдем для каждого звена ломанной точку, которая минимизирует сумму расстояний до подстроки(там получается кусочно-выпуклая функций, поэтоу можно найти интевалы выпуклости и запустить на каждом тернарник). Запомним все такие точки(по всем звеньям и всем подстрокам). Упорядочим их. Дальше простая динамика: состояние — последняя точка и последняя взятая буква, значение — минимальная возможная сумма. Утверждается, что в другие точки ломанной ничего никогда не надо ставить.
1: Если β составляет угол меньше 45 градусов с направлением на Солнце, то просто ускоряемся одним манёвром в направлении Β. А иначе -- двумя манёврами, как на картинке:
Странно, что так мало команд её решило. Хехе.
(дубликат)
Почему в 7 нельзя написать что-то совсем тупое? У нас есть состояние d[t][x][y][dir], t — текущее время, от этого параметра можно избавиться, чтобы сэкономить память, х, у — координата, dir — направление, по которому сделали последний ход. Заметим, что монстр как бы разрастается до какого-то большого квадрата возможных местоположений, и нам, видимо, надо провести лучи из углов квадрата и как-то проверить, смогли ли мы прийти в это состояние. Вроде должно укладываться в ТЛ 7 секунд, но писать это, видимо, не очень приятно
Наверное, если в состоянии хранить текущее время в чистом виде, то будут проблемы с тестами, где оно очень большое (ходьба по спирали). Достаточно для каждого остатка от деления времени на (Speed+1) найти минимальное t.
dir можно не хранить в состоянии. Можно не считать ходы элементаля ходами вообще, просто при выполнении шага непосредственно перед его ходом проверять, не убьёт ли он нас.
Да, элементаль становится квадратным =) Точнее, в общем случае прямоугольным: за пределы поля он не выходит. Если провести лучи из углов квадрата, то получится некий сектор. Утверждается, что все клетки в этом секторе в опасности. Получается необходимая проверка уклонения за O(1).
Писать не очень. К тому же, легко забыть какое-нибудь мелкое условие среди длинного текста. Типа "на выходе сразу убегаем" и "по элементалю нельзя ходить" и пр.
Между тем вышел список команд, приглашенных на очный тур: http://olympic.nsu.ru/files/Invited_teams_0.pdf
Ограничение на число команд от вуза радует, однако