Странно, что никто еще не написал (С) AlexErofeev
Давайте обсудим здесь, собственно, интернет-тур сей олимпиады
UPD упс, заметил запись о всесибе постарше, ну да ладно, там вроде особо нет обсуждения пока
Странно, что никто еще не написал (С) AlexErofeev
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
да уж, не успел я додебажить с этой поправкой чуть-чуть :(
Наличие мостов мы проверяем обычным дфсом за M. log получается из бинпоиска по ответу.
То есть мы просто удаляем пребро, строим граф без него, проверяем наличие мостов?
А как тогда быть с тестом
3 5
1 2
1 2
2 3
2 3
2 3
Когда мы удалим последнее ребро, мостов не будет, но ответ -1 вроде бы.
Список ребер, где у обычного ребра номер 2*i и у обратного ему 2*i+1.
Тогда обратное ребро легко найти взяв xor 1 от номера текущего: j^1 (обратно) j.
Кто-нибудь может объяснить, почему решения 5 и 8, которые заходят под mingw падают под visual C++? (tl34 и wa2 соответственно)
Как сдать такое?
я в курсе, да)
просто у меня в шаблоне уже давно стоит typedef long double ld , поэтому привык так называть
Вопрос по
B2. Верна ли следующая эвристика?Как-только вступили на оранжевый участок, ускоряемся по нему до конца. Как-то только вступаем на синий, немедленно прыгаем и летим до ближайшего оранжевого участка. Если оранжевых нет, то до ближайшего синего и снова прыгаем.
Закодить просто не успел.
Имеется в виду, что рациональные дроби нужны только для проверки, что точка лежит на кривой. Ибо мы ведь не можем навскидку сказать, насколько близко кривая, заданная тремя целочисленными точками, может проходить от другой целочисленной точки. Но, видимо, либо не слишком близко, либо тесты дырявые. Скорее первое.
http://pastebin.com/z5qdAFGc
ну в принципе да, но как минимум на приоритетных очередях вроде нужно было писать
Ну понятно, что пока шарф не окажется на касательной к дереву, Остап бежит по окружности, это считаем отдельно.
Далее веселая спираль.
В любой маленький отрезок времени dt он бежит по дуге окружности. За это время шарф проворачивается на угол d(alpha).
Угол шарфа - полярный угол вектора из начала шарфа в конец шарфа.Он изменяется на d(alpha) за промежуток времени dt, при этом Остап пробегает расстояние L*d(alpha). Мы можем найти, с какого полярного угла шарф начала движение, и каким углом закончил, это несложно (upd: можем, но, конечно, не надо).
Остается проинтегрировать по углу
integral(alpha1 to alpha2) (L(alpha)*d(alpha))
L(alpha) линейно убывает от L0 до 0
поэтому ответ - (alpha2-alpha1)*L0/2.
Наверное есть более изящное объяснение такой простой формулы.
Пишем положение конца шарфа через угол, учитывая укорочение этого шарфа с увеличением угла. Далее дифференцируем эти x и y по углу (там много что сокращается), берем сумму квадратов и ее интегрируем (под интегралом - линейная функция). А вообще-то я сам был немало удивлен, когда после численного интегрирования при написании решения примерно неделю тому назад (сначала предполагал, что потребуется preculc и интерполяция) совершенно случайно обнаружил, что ответ описывается простой формулой l*l/(2*r). Так что задача совершенно случайно превратилась из одного жанра (численные методы) в немного другой - математический анализ.
Гена так решил.
Причем геометрическая часть, действительно, становится совершенно тривиальной.
Да и вряд ли кто-нибудь решил эту задачу из числа тех тех, кто еще не знает интегрирование.
Да нет тут никакой дискуссии.
Меня самого заинтересовала эта задача, и я попытался вывести подинтегральную функцию для движения Остапа по дуге. Увидел, что все становится очень громоздко и плюнул. У Вас, как я понимаю, это тоже было непросто, если изначально предполагалось численное интегрирование.
А здесь я просто озвучил красивую, по-моему мнению, идею.
Вопрос по задаче №5. Мы пробовали решать так:
1) Первый критерий: ответ первое ребро при котором граф стал связен. Если такого нет - ответ на задачу "-1 -1"
2) Второй критерий. Переберем бинарным поиском ответ. Пускай мы рассматриваем некоторые mid ребер. Добавляем их в сеть. Теперь пускаем поток от первой вершины ко всем остальным(по очереди, каждый раз добавляя ребра по новой). Если хотя бы для одного стока поток меньше 3, наш текущий mid нас не устривает. Сложность выходит порядка (N*N*sqrt(M)*logM).
Я ожидал вердикт ТЛ, но мы получали ВА тест 7. Кто-то может обьяснить почему?
а кто из школьников занял место выше 71го?
SpbSU Belka_Strelka_Koleso - двое из 3 - школьники
Заставило во время контеста понервничать:
Задача 6.
"Им надо знать два числа — минимально допустимую и достаточную длины лестницы. Минимально допустимой длины, может быть, и хватит, чтобы снять похитителя колбасы, но уж меньшей-то точно не хватит."
Кто-нибудь объяснит мне, как это надо интерпретировать, чтобы получить верное решение?
По-моему, в семпл тесте, например, лестницы длины 2 может быть и хватит, так как Федор может сидеть на скале высотой 2 - самой левой.
Мы сдали ее забив на условие и угадав решение по семпл-тесту.
Охщи. А вот этих слов мы не заметили. Про самую высокую.
y'=cos(t)*r-cos(t)*r-(l-r*t)*sin(t); sqrt(x'^2+y'^2)=(l-r*t)(cos^2(t)+sin^2(t)); Интегрируем, пока функция >0,
получаем ответ l*l/(2*r).