Как стать автором
Обновить

Комментарии 20

Высший пилотаж!

PS: Спасибо за разбор полётов топикстартеру.
Фотография с финала прошлого года.
Конечно, финала этого года еще не было, а фото сидящих по домам участников онлайн-тура опубликовывать нельзя ну никак ;-)
Получился бы интересный колаж: )
Там все в FAR кодят? Я нашел единомышленников!!!
Это я про картинку к посту
Почти все. В Саратовском Государственном Университете в центре олимпиадной подготовки почти насильственно пересаживают на FAR.
Это не FAR, а Borland С/C++©
Это действительно Far :)
Так уж получилось, что человек на переднем плане — это я :)

В Far кодят не то чтобы почти все, но около 50% знакомых сильных олимпиадников точно. Я пишу в Far практически с самого начала занятия олимпиадами.
Я чего-то не понимаю, но ведь FAR — это файловый менеджер?
Если у Вас FAR под рукой, нажмите F4 на любом понравившемся текстовом файле и наслаждайтесь созерцанием текстового редактора. Плагин Colorer сделает созерцание кода более удобочитаемым.
А ещё в меню File associations можно настроить, например, компиляцию файла под курсором по нажатию Enter. Очень удобно и быстро.
<grumble-mode>
Молодой человек, если бы Вы видели своими глазами продукты Borland начала девяностых, то не забыли бы расцветку оконной системы Turbo Vision, использовавшейся как C++, так и в Pascal. Про то, что на экране изображено окно, вмещающее по ширине более 80 символов, я вообще молчу.
</grumble-mode>
Задачи отличные. Жаль, что решать их могут единицы, во всяком случае в регионах. Увы, но качество образования у нас не то… теперь понимаешь, почему многие хотят попасть в МФТИ, МГТУ им Баумана или в СПбГУ, а не учится в местных «университетах». Хотя с другой стороны для 80% работодателей такого уровня программеры и не нужны.
ACM ICPC, Google Code Jam, Russian Code Cup, VK Cup, Abbyy Cup и другие подобные олимпиады, по-моему, не связаны с качеством образования. Это отдельное направление. Насколько я слышал, например, в Бауманке оно не очень развито. Список и рейтинг вузов-участников ACM-ICPC ACM-ICPC — самое крупное соревнование по программированию, часто называемое Чемпионатом Мира.
Ну и вообще, я учусь в относительно провинциальном ВУЗе (г. Саратов) и занял 7-е место в отборочном туре Russian Code Cup.
Я бы не назвал провинциальным город, в котором уже сложилась отличная программистская школа, поставляющая каждый год команды в финал ACM ICPC.
Вы-таки не поверите, но в наше время в свободном доступе есть куча ресурсов для изучения теории (классический труд Кормена, распиаренный трехтомник Кнута, замечательный сайт e-maxx.ru) и отработки практики (TopCoder, CodeForces, Timus Online Judge). Если в регионе есть хотя бы диалапный интернет, остальное – дело желания. При надлежащем желании провинциалы проходят на региональные/всероссийские этапы олимпиады, берут свой диплом и поступают в желаемый вуз. Прелесть спортивного программирования в том, что учитель здесь играет более слабую роль, чем в других учебных дисциплинах.
Думаю, описанное решение задачи о принце слишком сложное. Проще поддерживать набор интервалов коридора, где может находиться принц в определённый момент времени.
Структура данных — массив, в котором хранятся интервалы (начало и конец x1, x2), и ловушки. На ловушку отводится два элемента один на начало, другой на конец, у обоих x1=x2, плюс в элементе должен быть номер ловушки, чтобы отличить ловушку от интервала, для интервала он будет невалидный, например -1.
Элементы в массиве не пересекаются и отсортированы по возрастанию x.
В момент времени t=0 в массиве один интервал x1=x2=0. Далее обрабатываются моменты времени появления и исчезания ловушек.
За прошедшее с последнего момента время каждый интервал увеличивается влево и вправо на это время, если упираются в границы ловушек (предыдущий и следующий элементы массива), то ограничивается ими, если пересекается с другим интервалом — объединяется с ним. При этом, если конечная точка попадает в интервал — то решение найдено, нужно только рассчитать время, по верхней границе интервала.
При появлении ловушки в массив добавляются две её границы, при этом какие-то один или два интервала обрезаются ей, или какой-то один может поделиться на две части, те, что попадут в неё полностью — удаляются.
При исчезании ловушки из массива удаляются две ещё границы (по её номеру).
Если к моменту, когда исчезла последняя ловушка, цель так и не достигнута, то время её достижения можно рассчитать по верхней границе последнего интервала.
Если в какой-то момент в массиве не оказалось ни одного интервала — значит цель недостижима.
Верхняя оценка времени работы алгоритма — квадрат от количества ловушек N. Для 2N моментов времени (появление и исчезание ловушки) нужно обработать массив с O(N) элементами — максимум 2N элементов для ловушек и максимум N+1 для интервалов.
Ага, я сдал в точности такое решение на самом соревновании :)
А неужели нельзя как-то «вне конкурса» tourist и других пропустить? Интересно же посмотреть, как они выступят.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.