Комментарии 20
Высший пилотаж!
PS: Спасибо за разбор полётов топикстартеру.
PS: Спасибо за разбор полётов топикстартеру.
Фотография с финала прошлого года.
Там все в FAR кодят? Я нашел единомышленников!!!
Это я про картинку к посту
Это не FAR, а Borland С/C++©
НЛО прилетело и опубликовало эту надпись здесь
ACM ICPC, Google Code Jam, Russian Code Cup, VK Cup, Abbyy Cup и другие подобные олимпиады, по-моему, не связаны с качеством образования. Это отдельное направление. Насколько я слышал, например, в Бауманке оно не очень развито. Список и рейтинг вузов-участников ACM-ICPC ACM-ICPC — самое крупное соревнование по программированию, часто называемое Чемпионатом Мира.
Ну и вообще, я учусь в относительно провинциальном ВУЗе (г. Саратов) и занял 7-е место в отборочном туре Russian Code Cup.
Ну и вообще, я учусь в относительно провинциальном ВУЗе (г. Саратов) и занял 7-е место в отборочном туре Russian Code Cup.
НЛО прилетело и опубликовало эту надпись здесь
Думаю, описанное решение задачи о принце слишком сложное. Проще поддерживать набор интервалов коридора, где может находиться принц в определённый момент времени.
Структура данных — массив, в котором хранятся интервалы (начало и конец x1, x2), и ловушки. На ловушку отводится два элемента один на начало, другой на конец, у обоих x1=x2, плюс в элементе должен быть номер ловушки, чтобы отличить ловушку от интервала, для интервала он будет невалидный, например -1.
Элементы в массиве не пересекаются и отсортированы по возрастанию x.
В момент времени t=0 в массиве один интервал x1=x2=0. Далее обрабатываются моменты времени появления и исчезания ловушек.
За прошедшее с последнего момента время каждый интервал увеличивается влево и вправо на это время, если упираются в границы ловушек (предыдущий и следующий элементы массива), то ограничивается ими, если пересекается с другим интервалом — объединяется с ним. При этом, если конечная точка попадает в интервал — то решение найдено, нужно только рассчитать время, по верхней границе интервала.
При появлении ловушки в массив добавляются две её границы, при этом какие-то один или два интервала обрезаются ей, или какой-то один может поделиться на две части, те, что попадут в неё полностью — удаляются.
При исчезании ловушки из массива удаляются две ещё границы (по её номеру).
Если к моменту, когда исчезла последняя ловушка, цель так и не достигнута, то время её достижения можно рассчитать по верхней границе последнего интервала.
Если в какой-то момент в массиве не оказалось ни одного интервала — значит цель недостижима.
Верхняя оценка времени работы алгоритма — квадрат от количества ловушек N. Для 2N моментов времени (появление и исчезание ловушки) нужно обработать массив с O(N) элементами — максимум 2N элементов для ловушек и максимум N+1 для интервалов.
Структура данных — массив, в котором хранятся интервалы (начало и конец x1, x2), и ловушки. На ловушку отводится два элемента один на начало, другой на конец, у обоих x1=x2, плюс в элементе должен быть номер ловушки, чтобы отличить ловушку от интервала, для интервала он будет невалидный, например -1.
Элементы в массиве не пересекаются и отсортированы по возрастанию x.
В момент времени t=0 в массиве один интервал x1=x2=0. Далее обрабатываются моменты времени появления и исчезания ловушек.
За прошедшее с последнего момента время каждый интервал увеличивается влево и вправо на это время, если упираются в границы ловушек (предыдущий и следующий элементы массива), то ограничивается ими, если пересекается с другим интервалом — объединяется с ним. При этом, если конечная точка попадает в интервал — то решение найдено, нужно только рассчитать время, по верхней границе интервала.
При появлении ловушки в массив добавляются две её границы, при этом какие-то один или два интервала обрезаются ей, или какой-то один может поделиться на две части, те, что попадут в неё полностью — удаляются.
При исчезании ловушки из массива удаляются две ещё границы (по её номеру).
Если к моменту, когда исчезла последняя ловушка, цель так и не достигнута, то время её достижения можно рассчитать по верхней границе последнего интервала.
Если в какой-то момент в массиве не оказалось ни одного интервала — значит цель недостижима.
Верхняя оценка времени работы алгоритма — квадрат от количества ловушек N. Для 2N моментов времени (появление и исчезание ловушки) нужно обработать массив с O(N) элементами — максимум 2N элементов для ловушек и максимум N+1 для интервалов.
А неужели нельзя как-то «вне конкурса» tourist и других пропустить? Интересно же посмотреть, как они выступят.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Russian Code Cup 2012: подробный разбор задач с отборочного раунда (полуфинал)