Всем привет!
Начался заочный этап VII Открытой олимпиады школьников по программированию! Он продлится ориентировочно до середины января 2013 года. В марте 2013 состоится финальный этап олимпиады, на который будут приглашены около трёхсот лучших школьников по итогам заочного этапа.
В течение трёх месяцев будет предложено около десяти-двенадцати задач. Они будут появляться порциями на сайте олимпиады. Вы найдёте задачи различного уровня сложности, как для только начинающих изучать основы программирования, так и для профессионалов, уже достигших успехов на опимпиадах выского уровня.
В этом соревновании ежегодно принимают участие школьники разных стран. Допускается участие вне конкурса всех желающих, не только школьников.
(05.11.12) UPD1: Добавлены задачи E — G.
(06.11.12) UPD2: Напоминаем, что данный пост также не является местом для какого-либо обсуждения содержательной части задач. Все вопросы задавайте жюри в тестирующую систему.
(15.11.12) UPD3: Произошёл реджадж по задаче C. Результаты могли измениться не в лучшую сторону :-)
(12.12.12) UPD4: Красивая дата. Тем временем постепенно были добавлены последние шесть задач. Обратите внимание: изменилось условие задачи L.
(19.12.12) UPD5: Сервер временно недоступен. В течение суток всё должно подняться.
(19.12.12) UPD6: Всё починилось.
(29.12.12) UPD7: Задача M была перетестирована. Обратите внимание, изменился порядок тестов и на некоторых тестах результаты ваших программ могли ухудшиться.
(05.01.13) UPD8: Как вы многие заметили, ночью прошёл полный реджадж всех посылок, который производился с целью тестирования возможностей новой версии ejudge. Также был удалён некорректный тест по задаче L. Результаты могли улучшиться :-)
(10.01.13) UPD9: Традиционным образом жюри олимпиады приняло решение продлить заочный тур аж до 23:59 26 января!
Принимайте участие и приглашайте всех знакомых :-)
На финальный этап приглашают школьников из других стран?
да. В прошлом году один из призеров был гражданином Болгарии, например :)
например, в прошлом году всем известный школьник из Беларуси выиграл эту олимпиаду: http://olympiads.ru/zaoch/2011/final/res.shtml
Да, конечно. Последние два года школьник из другой страны эту олимпиаду выигрывал :-)
А оплата дороги и/или проживания предусмотрена?
Дорогу никогда не оплачивали, примерно топ200 обычно предоставляется место в общежитии МФТИ за разумную плату. Посмотри на сайте, как было в прошлых годах, там все написано.
Ну как в общежитии... Иногда кого-то селят в студенческий клуб внутри общежития, получается как в лагере — >>6 человек в комнате на двухэтажных кроватях (вроде даже не все заняты), рояль в комнате, туалет на этаже.
Главное ведь атмосфера :)
мне всегда это нравилось)
Мы жили в 9ке:)
В прошлом году вроде туда приоритетом селили тех, кто выше
Ни фига. Чуть-чуть рандома тоже было. Меня как раз поселили в клуб.
По-моему, никогда не было приоритета. Просто селили определенных людей в порядке регистрации на месте. Вот в прошлом году мы приехали в конце, вот организаторы нашли свободное место в клубе с роялем.:)
Мне казалось, что иностранцам не оплачивали, но лучше уточнить в оргкомитете.
Оп. Спасибо за анонс. Олимпиада длинная, но спокойно могла пройти мимо)
а когда будут следующие задачи?
в прошлом году должны были быть 10 ноября, вроде, но появились в начале декабря.
в прошлом году в стартовом паке задач было 6 штук, а здесь всего 4.
Будут ли учитываться попытки при отборе?
Нет.
Какая-то фигня, зарегал себе нового пользователя , появилось сообщение о том , что придёт письмо с паролём на почту , но ничего нет. Такая же фигня и у одного пацана. 100% гарантия того , что адрес эл. почты написан правильно.
Проверьте спам. 657 участников как-то смогли зарегистрироваться.
нда , действительно , в папке "Спам" лежит письмо от ejudge с паролём и ссылкой для подтверждения регистрации. Благодарю)
ех...спс тебе у меня тоже была такая проблема, но потом я нашёл то письмо прочитав здесь :)
Что мне делать если я новичок из новичков?
все текущие задачи как раз для тебя
Задача E
и зачем?
На них, все равно, разборы довольно сложно найти. А там просто ссылка на такую же задачу. Не думаю, что это сильно поможет.
Для 99% это не баян, а задача красивая.
А когда появaтся новые задачи???
Задачи E-G появились сегодня ночью.
Спасибо!!!
Задачи E,F,G последние или еще появутся новые задачи???
Они пишут, что будет опубликовано 10-14 задач
Спасибо!!!
Поднимите сервер, злыдни.
А по-моему, F не должна предстать в таком виде.
Предположим, что вы участвуете в той самой олимпиаде, открыли задачи, пребывая в хорошем настроении. Тут говорится, что числа надо прочитать в зеркале, читаются они также. Первая мысль говорит о том, что в примере "что-то не так". Вы ищете зеркало. Ходить в ванную с ноутбуком, чтобы усиленно высматривать что-то на экране — плохой вариант: тут и вода, и можно уронить в керамическую раковину, да и тесно. Шкафа купе у вас нет или у вас ремонт, и этот шкаф разобран. Ничего не остаётся, как включить зеркало на HTC/... (или довольствоваться рассуждениями в уме), повернув переднюю камеру к ноутбуку. Для этого приходится в слепую наводить эту камеру на циферки, поскольку ваше лицо находится в том же полупространстве, что и ноутбук. Поскольку вы не расположили камеру волшебным образом, вы будете фрустрированы. К сожалению, телефон и ноут можно расположить единственным адекватным образом, поэтому вы даже и не пробуете неадекватные расстановки. Ещё куча нервов, поиск в косметичке сестры/мамы/бабушки/... зеркальца — и вот, наконец-то даже и поняли условие.
Но разве задача должна проходить такой великий путь? Да, у нас много времени, и это заочный этап, и у нас много попыток, но как мне кажется, что решение задач должно вызывать хотя бы маленькое подобие решение задач на онлайн-соревнованиях и не использовать дополнительных ресурсов. И соответственно хотелось в этом разобраться самостоятельно, быстро и как бы без "штрафа".
Главное свойство условия — оно должно быть понятным для всей широкой аудитории. А пара лишних строчек смогла бы сэкономить время, как и участников, так и отвечающих на вопросы в тестирующей системе.
Надеюсь, я ничего такого не спалил, меня не заминусуют, всем лучей добра ^^
Чувак, прости, но, по-моему, ты гонишь. Представить, как выглядит число в отражении зеркала, можно абсолютно спокойно и без этого самого зеркала. А зеркало в доме надо иметь, вещь полезная :)
Если вы читали сей рассказ, то должны были понять, что их у меня дома их как минимум 4 :) И да, это очень полезная вещь, знаю.
К сожалению, я пришёл к ложному выводу, который мне казался очевидно верным. Понадобился ресурс, и этот рассказ — абсолютная правда (зачем мне писать неправду?).
мне кажется, жюри хотело дать интересную нетепичную задачу, ведь обычные задачки они везде, в расчете на то, что участники оценят весь прикол этой задачи. иногда стоит и такие уметь решать.
Мда. Посмотрел задачу. Похоже, что мне не зачет по телепатии.
Предлагаю всё-таки оставить обсуждение этой задачи в форме "это эксперимент, посмотрим, что будет".
Ну, по поводу нашумевшей задачи F. Надо сказать, что она сложна не только в понимании, но и в реализации. Автор точно будет гореть в Аду за неё.
Это нормально, что судьи не отвечают на вопросы?
Жюри тоже не железные, чтобы за всеми вопросами постоянно следить. Как правило в течение одного, максимум двух дней вам должен прийти ответ.
когда планируется добавление новых задач?
В декабре наверное. Точнее сказать не могу.
как найти задачи, тесты и разбор очного тура 2011-2012?
http://olympiads.ru/mosolymp/2011-12/info.shtml — вторая ссылка в гугле по вашему же запросу ;)
Не, это Московская олимпиада. Она проводится теми же людьми, но на ней куда проще задачи.
Ок, тогда вот: http://olympiads.ru/zaoch/2011/index.shtml Разбора там нет.
Мне одному кажется странным, что на простые (ну скажем так, не самые сложные) задачи дается практически 2 месяца (на 7 штук), а на "гробы" (а я так понимаю, что в оставшихся задачах (а их 4-5 штук, судя по предыдущим годам и тому, что на сайте написано), они непременно будут) месяц?
Когда уже добавят очередные задачи? Крайне алогично давать на более сложные задачи (те, что будут), меньше времени, чем на более простые (те, что сейчас).
выкладывайте идейные задачи, а не фигню алгоритмическую!
Да, спасибо, что прислушались. Спасибо за задачи I J, а дополняет картину L.
А чем I и J не нравятся-то? Интересные задачи..
I — безыдейная реализация боянистого алгоритма.
По-моему это должно расцениваться, как подсказка в решении.
По-вашему, идея задачи заключается в ее безыдейности?
Отличная попытка, составители условий...
Про идею я ничего не говорил. Просто теперь каждый, кто не может решить задачу, но прочитает пост про "боянистый алгоритм", получает преимущество.
наверное, стоит сказать, что очередную партию задач выложили.
Всегда хотел такую задачу, как L!
что в ней хорошего?
Технику тоже надо уметь писать. Да и на контесте длиной в пару месяцев, такое смотрится лучше, чем на обычном.
Маленькая поправка на то, что на месяц дали 5 задач. Давали бы лучше идейные, чтобы хоть интересно решать было.
Ну надо все таки понимать, что хорошие идейные задачи тяжело придумывать. И они с большим приоритетом пойдут на финал заочки, либо на этапы всероссийской или ВКОШПа, которые делают примерно те же люди.
PS. Мои сообщения не следует понимать как официальную позицию жюри одной из перечисленных выше олимпиад, или чего-либо еще. В частности к заочному этапу открытой я вообще не имею никакого отношения.
Чувствую себя настоящим мужиком, когда пишу задачу на 500+ строк кода.
заочка уже не та...
Походу ещё и M добавят!
Что с заочкой? OK
Всего тестов: 39, пройдено: 39, не пройдено: 0.
Получено баллов: 60 (из 0).
Причем в протоколе на последнем Неправильный ответ, и баллов 0 поставили.
UPD. Приятно, когда так быстро реагируют. А если несколько решений прошли онлайн тесты, в офлайн будет тестироваться последнее?
Просто ejudge не поверил, что кто-то так быстро сдал задачу L на полный балл.
Пожалуйста, поднимите сервер :)
Неполадки с интернетом на ВМК МГУ, где расположен сервер. К завтрашнему дню должно всё подняться.
UPD: Fixed.
А в задаче M сообщается результат взаимодействия только по первой группе?
По первым двум.
А почему тогда не видны результаты взаимодействия во второй группе(в протоколе мне доступны только первые 13 тестов — это первая группа)?
Теперь всё видно, спасибо за комментарий. В некоторый момент что-то поломалось в настройках.
Какова продолжительность олимпиады и сколько человек проходят?
По текущей версии олимпиада длится до 11 января. Но традиционно заочный тур продлевается на пару дней.
Проходит ориентировочно 300 человек, следите за объявлениями на сайте.
А с чем связано такое глобальное перетестирование? UPD Кажется, перепроверяются попытки с ошибкой компиляции
Мы исследуем новые возможности 26 версии ejudge.
Вы добавили новые тесты в L? С чего это вдруг она с полных двух групп падает на ноль баллов?
Подобные вопросы задаются только в тестирующую систему, так как касаются только вас.
Туда задано тоже, и потом, я же не знаю, актуально это или нет для других.
В систему вы задали после того, как написали комментарий в этом посте. Ещё раз, это не вопрос для вынесения на общественность, ждите ответа в тестирующей системе.
Ну не знаю, для многих, думаю, вопрос о перетестировании актуален. Да и вы каждый раз обновляли пост, когда перетестировали задачу.
Повторяем, вопросы по проверке ваших решений задавайте в тестирующую систему. И ещё раз, проблема относится только к вам.
Ладно. Скажу так: хорошо, что проблема только у меня, было бы прискорбно, если бы у всех внезапно падали рабочие решения. Больше писать сюда не буду, дабы не вызывать интересной реакции.
И ещё, спасибо жюри таки за быстрое решение возникших проблем.
странная дискуссия
по-моему, Zlobober чётко отметил, что твоя проблема — это единичная проблема, которая должна быть решена в индивидуальном порядке
а обо всех влияющих на результаты изменениях и режаджах сказано (или будет сказано) в тексте поста
Всем привет! Глядите, какое замечательное сообщение мне сегодня пришло во ВКонтакте:
Эдуард (http://vk.com/id189014219 ): Здравствуйте, Кирилл. Вас беспокоит апелляционная комиссия города Москвы. От 05.01.13 в наше отделение поступило множество заявлений о рассмотрении ликвидности олимпиадных работ интернет-олимпиады (http://olympiads.ru/zaoch/2012-13/index.shtml ). До сих пор не было выявлено ни одной проблемы, поэтому Вам нечего бояться. Нами уже рассмотрено 248 работ из которых лишь 2 были признаны нелегетивными. Но также 123 человека дали нам отказ. В связи с этим работы участников не будут допущены к проверке. Рекомендуем Вам отправить олимпиадные работы в электронном виде сообщением лично мне в ближайшее время. Ответ о ликвидности мы обязаны предоставить в течение трёх дней... С уважением, сотрудник ОМБЦУ "Московский центр апелляционных тяжб" Э.В.Крюков
Как думаете, высылать решения? :D
Высылай что-нибудь в таком стиле. Потом все вместе посмеемся.
Было бы круто :) Но, во-первых, я вероятно уже раскрылся перед Э.В.Крюковым, запостив здесь, во-вторых, побаиваюсь гнева жюри.
Вам не одному пришло такое. Естественно это следует игнорировать :-)
Эдуард стал Максимом, и он подписан на МДК
Вопрос к жюри: будет ли в этом году традиционное продление заочного этапа? Если нет, то может быть стоит поставить в системе время окончания олимпиады (сейчас там в строчке "продолжительность" написано "не ограничена")?
Традиционное продление произошло до 23:59 по московскому времени 26
февраляянваря.А не долго ли? Может, января?
Хотя даже если и января, то все равно как-то долговато. С чем это связано?
Опечатка, января конечно. Порешать интересные задачи можно подольше.
Вынуждаете решать мерзкие L и M >__<
Предлагаю не разивать диспут на тему этих задач.
Технические задачи тоже писать полезно, им самое место на заочном туре.
Иээх, а так хотелось побыстрее увидеть финальную табличку :(
А какого уровня данная олимпиада?
второго, в том году была первого, но теперь увы
Вообще-то уровень олимпиад определяется после их проведения. И важнейшим фактором служит число участников.
на данный момент она вторая, не надо умничать, я тоже это не с потолка взял
видимо, потому что в ней участвует ~250 человек (столько же, сколько во всеросе) ее сделали второго уровня, да, да
по мне так, эти уровни определяются людьми далекими от программирования, и, зачастую, необъективно
"Об утверждении уровней олимпиад школьников, включенных в Перечень олимпиад школьников на 2011/2012 учебный год"
ну тогда мне непонятно, почему в предыдущем году ее сделали 2м, недостаточно сложная или что?
Вроде как раз из-за количества участников. Причем какая-то не особо интеллектуальная олимпиада (там были задачи не по программированию, а всякий excel и т.п.) получила тогда первый уровень.
Скорее недостаточное лоббирование..
Ибо ВКОШП+ИОИП и открытая — топ-2, который я вижу.
кстати, насколько я слышал, ВКОШП в этом году исключили из списка ректорских олимпиад, по причине того что она командная
В этом есть логика.
I уровень — не менее 3000 человек из 30 и более регионов. II — не менее 1500 школьников из 15 регионов. III — не менее 300 человек из 3 и более субъектов РФ.
Участники заочных туров являются обычными участниками олимпиады.
В прошлом году в заочном туре олимпиады 2011-2012 приняло участие 1619 человек.
То есть сложность никак не учитывается? Похоже, сейчас все модно мерить количеством, а не качеством...
А как Вы измерите это самое качество?
Ну по математике первого уровня вроде таки адекватные олимпиады(более менее). По крайней были, в тот год, когда я поступал
Первое что приходит в голову: есть же группа людей, которая проводит всеросы по предметам. Я думаю, никто не будет спорить, что она состоит на 90% из профессионалов, понимающих, какие должны быть задачи/задания. Их можно было бы попросить оценить задачи/задания олимпиад из списка
Сложность задач тоже оценивается. Там есть группа каких-то странных людей которые этим занимаются. Но по факту смотрят на количество. А по математике адекватно, потому что там массовые олимпиады нормальные.
По информатике единственное что есть достаточно массовое — ИТМОшная олимпиада по школьному курсу, которая мало чем отличается от ЕГЭ. Насколько я знаю они и сами уже ей не рады.
[double]
Как скоро будут результаты? Когда будет разбор задач?
p.s. Обидно, когда время в системе и время на Пк различаются в 57 секунд...
Могу сказать, что разборы задач готовятся, онт точно будут через некоторое время. Результаты — после некоторого количества формальностей, в частности — проверки на списывание.
А сколько времени это займет?
Считается ли копипаст с емакса списыванием?
Скорее всего нет, так как сам e-maxx ответил на вопрос о копипасте с его сайта.
Главное, чтобы скопированный алгоритм доделали напильником сами.
А правда, что уже можно начинать делиться впечатлениями и узнавать решения(или опять же делиться)?
Да! Этот момент настал! :-)
Крутотень) Кто-то может рассказать как решать E на 100?
Не ?
Можете поподробнее расписать, как применить его к данной задаче? Ведь здесь у нас предметы доступны только в определенный промежуток времени, а пересчет на каждом отрезке работает долго.
Назовем событием предмет или запрос. Отсортируем события по началу их отрезка влияния. Будем поддерживать dp[i] — последний момент времени, когда доступна сумма i. Пересчитывается эта штука за O(k) понятно как при появлении предмета. На запроc теперь можно ответить за O(1) сравнив конец отрезка запроса с моментом смерти данной суммы dp[sum].
Асимптотика —
Как скоро можно ждать балы (по конкретнее, если возможно)?
Кстати, выложите ли вы потом задачи и тесты в открытый доступ или в codeforces.тренировки? Хотелось бы все же узнать тесты по задаче L и добить её.
Выложим.
Объясните кто-нибудь F и J. По этим двум задачам сделал овермного попыток — всё в пустую. Не проходит несколько тестов и всё....
ну в F у нас есть 2 случая:
1)Зеркало находится сверху листочка с числами, тогда у нас зеркально отображаются числа 0, 1, 3, 8.
2)Зеркало находится сбоку, тогда нам подходят числа 0, 1, 2(отображается в 5), 5(отображается в 2) и 8(при этом 2 и 5 подходят, если они равноудалены от центра и их префиксы(с начала и конца строки) совпадают).
Разберем оба случая, вспомним, что числа не начинаются с 0 и все,победа)
Рассматривал оба случая. Писал всё — от жутких формул до перебора. Неужели набажил во всех попытках?
проверяли, что для теста '*' ответ 4?(у 0 нет ведущих 0).
Да. Падаю на последних тестах 18 и 27. Обидно, что убрали тестирование на всех тестах. Так можно было бы адекватнее оценить ситуацию.
Насчёт задачи J.
Верно ли, что диагональ лежит внутри полигона, если она не пересекает ни одной его стороны и центр диагонали лежит в полигоне?
Верно. Доказывается же очевидно, нет? Так как нет пересечений, то вся диагональ лежит либо вне многоугольника, либо в нем. Значит, если какая-то точка диагонали (за исключением концов, конечно) лежит внутри многоугольника, то и вся диагональ лежит внутри.
Вопрос к жюри: все-таки, как скоро начнется тестирование? Я все понимаю: проверка на списывание, возможно, нет готовых тестов по некоторым задачам(и такое бывает:) ) или какие-то технические проблемы...Но прошло уже 2,5 дня с момента конца контеста
UPD вопрос снят
Можно заметить, что, например, в прошлом году тестирование заняло 15 дней, судя по постам на http://olympiads.ru/zaoch/2011/index.shtml
Из сообщений на доске новостей очевидно, что сначала решения тестируют, а затем проверяют на похожесть. Может разумно показывать текущее положение?
Открыты протоколы тестирования и предварительная таблица результатов.
Выложите пожалуйста чекеры и тесты.
Выложены тесты и чекеры
Не ожидал, что в L заходит питоновский exec на 100.
Блин, а я честно все писал...Имхо, честный способ был все-таки полезнее для получения навыков писать парсеры и разбор арифметических/логических выражений
Но не полезнее в умении выбрать инструмент для задачи;)
Чтобы научиться забивать гвозди микроскопом, микроскоп тоже удобнее молотка:)
Выбирать инструмент — это конечно хорошо. Но, во-первых, питон всяко работает медленней, чем решения, его не использующие, а во-вторых, если бы у вас хоть чуть-чуть поменялся синтаксис(другие обозначения логических операторов, например), что бы вы стали делать?
Написали бы на руби) Я не знал руби и за неделю выучил его на 30 баллов, зато код был в 30 строк. Так что просто признайте, что вы не использовали такую возможностью и теперь вам обидно.
Обидно? )С чего бы? Я просто обсуждаю и сравниваю разные пути решения, только и всего. А вы вот сможете без руби, и прочих питонов-фигонов ) написать решение? Это, мне кажется, несколько сложнее, чем нагуглить что-то про руби
ох, ох, ох, тебе просто надо похлопать, ты говоришь так, как будто ты сдал ее на 100, какой молодец, на 30 сдал и учит жить
неделю учил? не лень было? уж проще было сильно меньше чем за неделю сесть, разобраться, и аккуратно все самому написать 300-400+ строк на 100. если уж мы говорим о выборе нужного инструмента, то он должен давать выигрыш в скорости, а так, что толку что у тебя код в 30 строк (возьми пряник с полки).
Это была бы другая задача. Другая задача — другой инструемент.
Кстати, формат явно был бы дан довольно строгий, я думаю, тогда бы можно было попробовать replac'ами к своему любимому скриптовому языку свести.
Ну в любом случае exec просто так на голом коде не запустишь. Нужно изменять имена переменных, бороться с объявлениями внутри условий (области видимости короче), да и подсчет операций exec сам не ведет. То есть все равно код обрабатывать надо, другое дело, что меньше, это да. А арифметика в питоне (длинная) довольно шустрая.
А не могли бы вы выложить исходники? Желательно, чтобы выложил кто-нибудь, кто писал на других скриптовых языках(особенно интересен ruby).
Просто хочется узнать, как можно красиво написать и не говнокодить.
большой код != говнокод, да, да.
Я не говорю именно про размер кода, я говорю только про свой, у меня написан говнокод и я точно также бы наговнокодил на сишке. Сейчас мне интересно как можно написать красиво и лаконично.
Как решать E на 100?
так
Спасибо. Интересное решение=)
Еще один способ: посортим предметы по времени их исчезновения. Теперь напишем рюкзак, для каждого состояния в нем будем хранить максимальное время, начиная с которого мы можем получить данную сумму при использовании i первых предметов(т.е самый поздний момент, когда мы можем прийти, чтобы получить эту сумму). Теперь для каждого запроса ищем самый поздний предмет, который мы успеем купить(бинпоиском, назовем его позицию pos). Тогда достаточно сравнить момент прихода в магазин и dp[pos][sum].
Почему неверно в К делать BFS и удалять стулья, разделяющие компоненты связности (после удаления — объединяем компоненты) ?
Верно!
Как решать геометрию на 100?
Пусть мы определили для всех диагоналей являются ли они хорошими (это значит что полностью лежат в многоугольнике). Тогда пусть dyn[i][j], где i < j, — это кол-во триангуляции многоугольника с вершинами i, i+1,..., j-1, j. Тогда dyn[i][j] = сумма dyn[i][k] * dyn[k][j] для всех i < k < j и при этом диагональ i-k и k-j — хорошие.
Проще решать рекурсивно. Начальные значения — если i+1 == j или i+2 == j, то ответ 1.
Запускаем с параметрами 0 и n-1.
http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0
Здесь рассказывается про числа Каталана и как они связаны с триангуляциями. Там это утверждается. Это тривиально доказывается. Пусть у нас есть n+2 многоугольник. Пусть Tn+2 — кол-во триангуляции. Возьмем за основу какую-нибудь из сторон. Так как мы "триангулируем" многоугольник, то в итоге эта сторона будет стороной треугольника. Найдем оставшуюся вершину. После проведения двух оставшихся сторон треугольника, у нас получается три фигуры — многоугольник1, треугольник и многоугольник2. Тогда к ответу прибавим произведение кол-ва триангуляции многоугольника1 на кол-во триангуляции многоугольника2. Tn+2 = сумма Ti * Tn+2-i+1 по всем i от 2 до n+1. Теперь пусть Cn = Tn+2, тогда Сn = сумма Сi * Сn-i-1 по всем i от 0 до n-1.
Хорошие диагонали определяются просто. Должно выполняться условие, что никакая сторона не пересекает диагональ и не касается. Если это нарушено, то диагональ плохая. Если нет, то должно выполняться следующее — обход вершин с i по j должно совпадать по ориентации с обходом от j до i. Это проверяется с помощью ориентированной площади. Если одинаковая ориентация — одинаковый знак площадей от i до j и от j до i.
Вот это решение:
http://pastebin.com/aTa3Sr8H
Вроде там понятно, что к чему.
почему-то не прошёл чистый куб в J на java, вердикт — TL35. у кого нибудь прошла? скачал 35ый тест, на нём отрабатывает за 0.800, очень странно.
Какое количество человек ориентировочно проходит на очный тур?
первые 150 точно пройдут
ИМХО не справедливо. В очный тур можно пропустить 35%. В очному туре призёрами можно сделать 35%. Зачем кого-либо лишать возможности? Мне кажется, что почти любой школьник, участвующий в олимпиадах как минимум увлекается предметом. Такие школьники в любом случае должны иметь привилегии по сравнению со стобальниками из Дагестан(я не стараюсь кого-либо принизить по национальному признаку — проблема есть и она всеми известна).
Про общежитие. При таком кол-ве участников хорошо было бы предоставить жильё 350-400 людям(~15-20%).
Нет проблем. Постройте здание общежития для университета и тогда обязательно предоставят места 350-400 людям.
А зачем вообще предоставлять общежитие? Тот же ИТМО его не предоставляет, насколько я знаю. Понятно, что предоставление общежития — вещь хорошая, но как напрямую зависит количество человек, которым предоставили общежитие, с теми кто участвует в очном туре?
У ИТМО олимпиада 1 день- встал примерно в 3 часа утра,сел на поезд,поспал,на метро в пункт проведения,поел,пописал,и также на поезд и всё. А тут 2 дня,надо бомжевать. Но лучше на 2 гстиницу снять,но быть на 600м месте и участвовать. но 1ым 400,конечно,общагу. Я уже участвовал в Москве,и могу сказать,что мотаться 3 часа туда,3 часа назад утомительно,и на результатах усталость сказывается
Я тоже думаю,что хотя бы 35% хоть прошло бы,хоть бы им бы и общагу не давали,гдавное-дать им хоть шанс,а то 300 из 1800 уж дюже мало (
Великий Список Копипастеров:
http://olympiads.ru/zaoch/2012-13/disqualify.shtml
А смысл в 35 процентах? Вы действительно думаете, что будет шанс у пришедших снизу таблицы на высокие результаты? Формат отборочных совсем отличается от реального контеста. А именно: есть оооочень много времени на мыслительный процесс, в отличии от онсайта, что слабым участникам должно только помогать. А сильные — просто сильнее. Следовательно, очень сомневаюсь, что 35 процентов что-то изменят, кроме как добавят лишних проблем организаторам.
Ну на самом деле изменят. Причём очень многое. А именно:
сейчас кажется участвовало около 1800
если пройдёт 300 призёрами и победителями станут не более 105
если пройдёт 630 (35%) — призёров и победителей будет 220
Т.е. по-вашему на этих 115 можно просто забить?
Кстати есть где-нибудь разбор прошлого онсайта? И какой смысл на нём использовать группы тестов? Писать хоть-какие нибудь решения всё равно лучше, чем никакие.
Здесь ведь не стоит задача всеми правдами и неправдами увеличить количество участников. Ведь диплом этой олимпиады дает 100 баллов за ЕГЭ — то есть значительную льготу для поступления. Поэтому и количество призеров должно быть соответствующее — такое, что ВУЗы готовы дать этим людям такую льготу. Понятно, что они заинтересованы в том, чтобы ее получили лучшие абитуриенты, и число 115 здесь вполне оправдано. Ведь пусть, например, у одного участника было 20-е место на олимпиаде, а у другого — 210-е. Зато второй лучше написал ЕГЭ по русскому, и у него сумма баллов больше. Это справедливо, что на бюджетное место попадет второй участник, а не первый?
Назовите хоть один вуз в котором финал открытой учитывается, как льгота второго порядка, при этом отсутствуют ДВИ?
пожалуйста, МФТИ
А это справедливо,когда тупицы на нубских олимпиадах(причём закрытых) получают 1 место и 100 баллов?
Ну это уже совсем чушь. Что, в таком случае, мешает вам пойти на такую "нубскую" олимпиаду, взять там диплом и не ныть тут?)
Организаторы олимпиады не берутся пригласить свыше тех, кто приглашен на сей момент (т.к. каждого человека нужно обеспечить столом и компьютером). По числу участников финал Открытой олимпиады уже превосходит финал всероссийской олимпиады.
Жюри олимпиады не берется пригласить участников, набравших меньшее число баллов, т.к. считает, что на очном туре им решать нечего.
Цель открытой олимпиады не только (и даже не столько) в том, чтобы выдать побольше дипломов РСОШ для 11-классников, поэтому аргументы типа "а вот тогда победителей и призеров будет на 115 больше" оргкомитет и жюри не принимает.
1) В МФТИ такой мало компьютеров — никогда не поверю
2) Почему бы не сделать задачи очного тура несколько проще? На вопрос зачем — http://mirror.codeforces.com/blog/entry/5662#comment-120532 Да и к тому же те, кому там делать нечего дадут шанс пройти опять же хорошим школьникам.
3) Тот же комментарий. Поступить в сильный ВУЗ хорошему (не лучшему), но не натасканному на ЕГЭ школьнику достаточно сложно.
Сильный вуз? Смотря что вы под этим подразумеваете...
МГУ, МФТИ, ВШЭ, СПБГУ, СПБГУ ИТМО хотя бы. Тут недавно слили человека с темой о поступлении ни за что
По 1 пункту, почитайте комментарии организаторов таких олимпиад, часто проскакивают на кодфорцах. Это отнюдь не простая задача организовать и собрать такое количество участников.
По 2 пункту, это самое нелепое оправдание, которое можно услышать. Если задачи будут легче, то они будут легче для всех, соответственно увеличится проходной балл и все равно пройдут приблизительно те же люди. Особенно при таком количестве задач это вряд ли что-нибудь поменяло.
По 3 пункту, в сильные ВУЗы идут сильные участники, если не можете поступать туда, ищите более "слабые" ВУЗы.
Хорошо, тогда немного другой вопрос. На чем основывается ваше понимание "сильного" вуза?
Компьютеров в МФТИ, может быть, и много — но они стоят по кафедрам, лабораториям и т.д. Суммарная вместимость компьютерных классов там не превосходит 200 мест. На самом деле, МФТИ — небольшой вуз, там немного студентов.
Какими будут задачи — решает методкомиссия олимпиады. Какой смысл делать задачи отборочного тура проще, если на очном туре задачи все равно будут очень сложные.
Представление о целях олимпиады у вас лично и у организаторов различные. Организаторы олимпиады не ставят целью выдать как можно больше дипломов. Для этого есть другие олимпиады, причем тоже первой категории.
Я предлагал сделать задачи проще на очном туре. Сделать допустим больше, но проще. Зачем? — ну уже говорил.
Если цель отобрать лучших — я никогда не смогу вас понять. Эти лучшие уже обеспечили себе поступление в ВУЗ. Дальнейший диалог бессмысленный, повторяется история с РОИ
Я прошёл, но учётом сложности очного тура и отсутствия жилья — я скорее всего просто не поеду... Nobody cares.
А я еще раз говорил, что у вас и у организаторов РАЗНЫЕ представления о целях олимпиады. И вы все пытаетесь мыслить в терминах поступления. На самом деле, даже большинство участников приезжает на открытую олимпиаду не ради поступления.
Ничто не мешает жюри(кроме отсутствия желания) удовлетворить и тех и других. Сделать задачи уровня "проверить, что писал сам простые задачи" + возможно немного посложнее. И сделать много много много более трудные задачи для выявления лучших.
Вы упомянули олимпиады, где легко взять диплом — какие же это?
Кажется вы там сказали нет, и переубедить вас было невозможно. Здесь также. Вы правы, я не прав. Нужно выявить лучших, а на остальных забить.
Очень легко взять диплом на этой олимпиаде, у меня в группе 6 человек по ней поступили без экзаменов (ВМК МГУ).
Удовлетворить всех сразу невозможно. Если тур разбавлять несложными задачами, то на их решение все равно уйдет время у опытных участников. Опять-таки, целью ЭТОЙ олимпиады не является раздать побольше дипломов. Эта олимпиада создавалась, как альтернатива финалу всероссийской олимпиады.
Олимпиада первого уровня на которой легко взять диплом — олимпиада "Информационные технологии". Организовывает ИТМО. Свыше 1000 участников очного тура только в 11 классах.
Также на других олимпиадах по информатике, например, ИОИП и Московской олимпиаде, диплом взять гораздо проще. Только в прошлом году они были второго уровня.
Нет, я не говорю, что надо выявить лучших, а на остальных забить. Для остальных есть другие олимпиады. Я их перечислил выше.
А я,например,только 2 января об олимпиаде узнал,программирую с 14 лет,правда олимпиадами только с 2 января занялся,и уже во многих в заключ. этап прошёл,а послушать лекции и разобрать все "сверх гениальные алгоритмы" диница,рюкзак и тд,думаю,время есть.
ну я сделал задач 4-5 на 100 баллов и прошёл бы в 630,но тут накладки произошли с 5ю олимпиадами-тяжело
Писать хоть-какие нибудь решения всё равно лучше-только для самоудовлетворения,что я,дескать,будущий гений )
Т.е. по-вашему на этих 115 можно просто забить! Идеально....
Мой комментарий был на вашу трогательную историю про занятие олимпиадами. Чем скорее вы поймете, что важен только результат вашей работы, а не процесс, тем будет лучше для вас.
Конечно можно. Что вы ерунду городите? А почему бы тогда всем 1800 участникам не выдать по диплому победителя? НЕУЖЕЛИ НА НИХ МОЖНО ПРОСТО ЗАБИТЬ!??!
Sultan — не моя история была
wackloner я говорил о том, что цель олимпиады — выявить школьников, интересующихся предметом. Выявить лучших — это отлично, но что делать просто хорошим ?
Для "просто хороших" есть другие олимпиады.
Открытая олимпиада по уровню задач и участников примерно соответствует финалу всероссийской олимпиады по информатике.
Становится лучше или смириться и остаться в нижней части таблицы.
А средних вузов нет-есть либо говно,либо ИТМО,МФТИ,МГУ
как я вижу,за 35% те,кто не прошёл,а те,кто против-всякие там натасканные лицеисты и гимназисты.
Появляется такое ощущение,что вузы хотят отобрать сразу истинных профессионалов,что бы их послать на ACM,а самим потом пиарится,что уровень какой преподавания высокий.
На самом деле то так и есть. Кто здесь отвечает? Кто отвечал в теме РОИ?
Им плевать на всех, кроме своих учеников(что вполне естественно). Какие есть возможности для учёбы в Москве, Питере и т.д. ? Людям из региона просто советуют — оставайтесь у себя дальше, не мешайтесь здесь под ногами. Посмотрите на список прошедших. Сколько человек из обычных провинциальных школ?
К списку крутых вузов добавь Саратов и Урал.
Есть ещё ННГУ с топкодер таргетом.
А средних тоже наберётся: УГАТУ, Челябинск, Волгоград, Пермь, НГУ, Самара, Ижевск и другие.
Любой из этих вузов гораздо лучше, чем ничего.
смотреть противно на твое нытье, плохо выступил, кто же виноват? сам и виноват, и клянчить тут не самая лучшая идея.
да и нет никакого преобладание москвы и питера, очень много участников из самых разных регионов страны
Почему же должны проходить ученики обычных провинциальных школ? Уж скорее сильные ребята учатся в лучших школах города\области, а не просто абы где. И люди из региона, которые недовольны своим положением, могут его улучшить, хорошо выступая где бы то ни было (как мне кажется) и действительно обучаясь, а не просто в погоне за дипломом разводя нытьё о количестве участников, проживании и прочей ерунде.
Возможностей есть много в "Москве, Питере и т.д.". Тем не менее, в вузах больших городов учаться не только их жители. Почему же так происходит? Наверное, потому, что если человек не тупой, то поступит по ЕГЭ (или получит диплом олимпиады).
К чему я клоню: вдруг ты не такой умный? Не тянешь планку "уверенных" дипломов сильных олимпиад? Зачем тебе МГУ, МФТИ? Мир на них клином не сошёлся, поверь. В Москве полно высших учебных заведений с общежитиями.
Подтверждение моих слов. Сине-фиолетовый уровень — явно уровень ВМК.
Хватит орать. Вы мне везде отвечаете одно и то же. Где я ною? На что я жалуюсь? Человек с пони на автарке, вы прочитали хоть половину из здесь написанного ?!
орать — звучит забавно) да, прочитал.
Проблема в том,что провинциалы имеют гораздо меньше шансов нежели Москвичи и тд-они должны спатиь перед олимпидой 5 часов и у них закрываются глаза,а москвичи приходят бодренькими,и думается им лучше.
Но это всё проблема рашки.
Разумеется,тут нам отвечают всякие задроты с 7 го класса,у которых родители сами тоже с именем,а не самоучки. Прияём,наверняка,они не умеют писать что-то другое,кроме олимпиад,и не используют Языфк программирования на всю катушку-кто хоть Union использовал? Хотя бы классы?
Насчёт задачи L-это нечто,вам ещё второй LUA или питон написать?! Спасибо,за свой язык можно получить гораздо больший достаток нежели 100 баллов ЕГЭ. у нас многие пишут информатику на 97 баллов,так что 100 баллов маловато
Я вот двух вещей не совсем понимаю: а) почему эта олимпиада должна использоваться для поступления? Для поступления есть олимпиады ИТМО, которые полностью соответствуют школьному курсу информатики, и, более того, имеют I уровень (я до сих пор не понимаю, почему). б) какое лично вам дело до того, как, кто и где получал образование?
<Режим иронии> Нет же, крутые ВУЗы намного больше заинтересованы в том, чтобы набирать алкоголиков из Мухосранска.</режим иронии> В любом случае, если брать тех, кто просто неплох, то места для лучших не останется. Пишите ЕГЭ по информатике на ~100 баллов, этому можно научиться за пару недель. Не понимаю, в чем проблема. Да и смысл отбираться на олимпиаду, если ты очевидно там ничего не займешь? Да, в 9-10 классе это приобретение опыта, но в 11 уже, как говорится, "поздняк метаться".
В том то и дело,чт оэто 1ая,где я пролетел,но в 35% я всё же вошёл.
Кстати, после этой олимпиады Отборочный ИОИП простым показался )
Как писалось выше, организаторы не могут предоставить больше, чем ~300 компов. С олимпиадами по математике и пр. попроще — но ты ведь не будешь компилировать программы на бумажке? В прошлом году итак была забита вся библиотека + комповники. Про общежитие и говорить нечего. На самом деле, 300 человек — это очень много. А 600 баллов, извини меня, набирать можно было с отрубленными руками, и тут только ты виноват.
ОМГ. В физтехе нельзя разместить три сотни человек? Ну так зачем размещать именно в физтехе?
Тут речь идёт о том, что можно было бы пропустить побольше народу, чтобы дать побольше дипломов призёров и победителей. Но жюри этого не хочет. Лично я не понимаю почему... Если хотят устроить очный тур, как финал РОИ, то одно другому то не мешает. Ничто не мешает сделать задачи многоуровневыми (кроме отсутствия желания) и тем самым удовлетворить всех участников.
...и не ценился бы диплом заочки. Знаешь, что-то(что бы это могло быть?) явно намекает на то, что ты вряд ли бы стал призером в любом случае.
Никак не могу найти очки прошлого года в тренировках...ее там попросту нет?
Здесь есть задачки прошлого года: http://informatics.mccme.ru/moodle/course/view.php?id=39
там нет задача предыдущего года, предыдущих годов — да
Есть где-нибудь чекеры финала прошлого года? Есть где-нибудь разбор?
И как я понял, на очном туре результат по первым группам сообщается сразу, как и на заочном туре?
Чекеров нигде нету, но задачки можно порешать здесь: http://informatics.mccme.ru/moodle/course/view.php?id=39 . Результат за группы тестов, которые отмечены как offline, проверяются после тура, результат по всем остальным сообщается сразу.
По ссылке же нет прошлогодних задач, зачем советуете?
Можете выложить отбор в тренировки?
У меня за F — 0 баллов. Здесь тот же самый код прошёл две группы тестов. Почему?
Скорее всего разные настройки языка. Попробуйте послать сюда с
{$H-}
первой строкой. Вроде больше уязвимых к таким вещам мест в коде сходу не нашел.1) Разве это не из delphi ?
2) Откуда я мог знать про эту директиву (что она выключена) ?
p.s. Я каким-то чудом прошёл, но всё равно немного обидно.
Ну надо знать свой язык. Выключено может быть все что угодно, поэтому все что надо, лучше руками включить.
А действительно в этом была проблема? Вроде строк длины больше 255 нигде не используется?
На финале можно ожидать подобных подлостей?
Таких — легко. Павел правильно сказал — надо знать язык, на котором пишите
А ты сам хоть знаешь сколько bool в памяти весит?
хоть знаешь как располагаются параметры при вызове функции? И знаешь воообще что представляет собой класс и функция? Это тоже знать надо,тогда от работы с памятью толку нет. В С++ тоже уйма всего,что надо включить,вдруг серв будет компиллировать int как int64,хотя ты этого не ожидал,а потом при копировании нескольких байт из числа,ты получишь не тот ответ?! Хотя последнее в олимпиадах не особо нужно
Хрена с два ты из кода навключаешь уйму всего под GCC.
Ну у меня GCC(MinGW),вот я и использую только bool ,char ,short ,long ,long long ,float,double
А в GCC bool 1 байт(помню как удивлялся sizeof-у struct буллов) А в VC вообще вроде б 32 бита,ужс
Так что для экономии памяти надо bool-ы в Union прятать
Это какая-то глупая оптимизация. У вас часто в коде больше ста булевских переменных?
Мне кажется или подобные вещи, даже зная язык предположить достаточно сложно? В таких случаях должна быть песочница. Конкретно на этом тесте я тестировал своё решение. Оно работало у меня, на CF, на Idoene корректно. Я посчитал, что этого достаточно.
По мнению жюри участник обязан прописывать в начале кода пару сотен директив? (с учётом того что по дефолту вроде {$H+})
По дефолту где? Я не думаю, что организаторы специально что-то выключали. Другая версия.
Я на паскале не пишу уже довольно долго. Когда писал, меня учили, что надо включать три-четыре флага. Не помню уже каких.
Но вообще да. Возможность запуска на сервере предоставлять надо. А там не было онлайн-групп?
Я не знаю что такое онлайн-группы. Показывали результат взаимодействия по тестам из условия. Я писал клар жюри о возможности поверки и тех. аспектах, но это не особо помогло.
Насчёт "по дефолту" — может и не прав. Но это следует из того что работает в других местах и на локальном ПК(на скачанном компиляторе без каких либо изменений). Но вообще здесь сказано:
А почему кстати с директивой ответ 58 ?
Как минимум, стоит знать про директивы B, H, I, O, Q, R, S. Полный список есть в документации, другое дело, что документация FPC не всегда соответствует реальности.
Necessary type conversions — это, скорее всего, значит, что, если объявить одну переменную AnsiString, а другую короткую String, то можно присваивать в обе стороны. Тем не менее, одна из них ограничена 256 байтами, так что гарантии того, что после присваивания они окажутся равны, нет.
Даже специально проверил. Результат на этих группах сообщался во время тура.
В этом году олимпиада вообще начнётся? Середина ноября уже.
Потерпите еще немного, последние тесты полируются и покрываются лаком. Скоро все будет.
Добавил оба тура очного этапа в тренировки: 2012-2013 Открытая олимпиада школьников по программированию, заключительный этап, тур 1 и 2012-2013 Открытая олимпиада школьников по программированию, заключительный этап, тур 2.
А что не так с этим сайтом?