Привет всем!
Рад вам объявить, что в этом сезоне состоится вторая олимпиада университета Иннополис по программированию для школьников.
Олимпиада пройдет в два этапа: два отборочных тура и финальный. Отборочные этапы нужно будет писать через интернет, результаты отборочных туров будут подводиться независимо. По результатам каждого из отборочных туров лучшие участники будут приглашены в финальный этап Открытой олимпиады университета Иннополис. Участвовать можно в любом из двух туров и даже в обоих турах, если у вас не получилось пройти в финал с первого. Туры проходят по правилам заключительного этапа Всероссийской олимпиады школьников по информатике. В олимпиаде могут принимать участие только школьники, условия задач всех этапов на русском языке.
Первый отборочный тур состоится в воскресенье, 6 декабря в 10:00 по московскому времени.
Второй отборочный тур пройдет в субботу, 19 декабря в 16:00 по московскому времени.
Для участия в первом отборочном туре нужно зарегистрироваться на сайте до 23:59 5 декабря. В подготовке первого отборочного тура приняли участие: Нияз Нигматуллин (niyaznigmatul), Павел Маврин (pashka), Ильшат Сафиулин (ilsaf13), Дарья Яковлева (Devushka), Айдар Гизатуллин (lightning), Дмитрий Якутов (YakutovDmitriy), Илнар Сабирзянов (iilnar), Максим Корчагин (zclimber).
Финальный этап состоится в середине февраля в университете Иннополис, более точные даты будут известны позже. Все финалисты олимпиады будут также приглашены в зимнюю школу олимпиадной подготовки, которая продлится около 7-10 дней перед финальным этапом олимпиады.
Участвуйте. Всем удачи!
UPD: Результаты и материалы первого отборочного тура.
Контест в тренировках: 2015-2016 Открытая олимпиада Университета Иннополис, первый отборочный тур.
Олимпиада ориентировано для школьников?
Вот да.
"Туры проходят по правилам заключительного этапа Всероссийской олимпиады школьников по информатике." — единственное предложение, которое намекает на "школьность" олимпиады.
UPD: обновлено :)
Да, для школьников. Почему-то совсем не подумал про это, пока писал пост. Добавил пару фраз.
первый отбор закончился. Но я нигде не могу найти количество участников, которые пройдут дальше.
Вряд ли это будет известно до окончания второго отбора.
"и даже в обоих турах, если у вас не получилось пройти в финал с первого."
Думаю, нет.
Я не могу зарегистрироваться Upd оказывается в пароле не должно быть символов типа точки извиняюсь
Сколько по времени длится тур (5 часов)?
Да, 5 часов
Как решать D?
Надо написать бинпоиск по количеству штурмовиков в ответе. Чтобы проверить, возможно ли такое количество штурмовиков, надо промоделировать "бой". Чтобы задача зашла на полный балл, надо использовать оптимизации:
1) Надо стрелять по врагам в порядке от человека с самым низким здоровьем и по возрастанию, не стреляя по следующему, пока жив предыдущий.
2) Надо предподсчитать количество выстрелов, которые надо сделать, чтобы убить всех врагов с 1 по i (в отсортированном порядке) (динамикой). Затем узнавать количество мёртвых врагов на данный момент можно за O(n) суммарно за весь бой — хранить указатель на первого живого, после, зная количество совершённых выстрелов (оно каждый раз увеличивается на количество союзников), сдвигать его вправо при надобности.
3) Точно также можно узнать количество живых союзников в конце хода, но, учитывая, что у них всех h здоровья, можно написать короче.
Соответственно, если в какой-то момент врагов становится 0, то возвращаем true, а если их больше 0, а союзников — 0, то false.
Это заходит на 70 баллов. Оптимизация для 100:
4) Надо перед каждым ходом посчитать, в течение скольки ходов никто не будет умирать, т.е. минимум из количества выстрелов, нужных для убийства хоть кого-нибудь из союзников, и нужных для убийства кого-нибудь из врагов. И затем "оптом" совершать такой ход.
Двоичный поиск по ответу. Проверяем за (N+M), просто убивая по одному. Я просто находил через сколько ходов умрет след. человек и моделировал. Несложно понять, что оптимальное действие — убивать сначала слабых. #code
разбор по Е пожалуйста тоже.
Я не знаю сколько там максимально ребер может быть, но я генерировал все ребра и поиском в ширину находил путь. Более подробно, каждый прямоугольник разбивал на два отрезка (вертикальный и горизонтальный). Далее, добавлял ребра между вертикальными отрезками и между горизонтальными отрезками отдельно. Генерацию для вертикальных отрезков делал так: сортировал сначала по X, дальше для каждого отрезка находил ближайший отрезок который с ним пересекается, убирал это пересечение и отрезок делился на два. Дальше спускался рекурсивно. Аналогично делал для горизонтальных отрезков.
Самый ближайший отрезок находил деревом отрезков (но перед этим сжал все координаты).
#code
P.S. Там не будет не больше 8 * N ребер.
Будет ли разбор от авторов?
deleted...
Кто может объяснить почему мое решение по задаче B НЕ ВЕРНО? Мое решение: Во первых, расставить очередь требуемым образом нельзя, если n<9*m(т.е. на каждого мальчика должно приходится хотя бы 9 девочек иначе он не сможет получить сдачи). Теперь,если n>=9*m решаем так: 1) Расположим сначала в очередь всех девочек 2) Теперь посмотрим куда мы можем поставить 1-го мальчика, его можно поставить после 9-й, 10-й и т.д после n-ой девочки, всего n-8 вариантов 3) Теперь посмотрим сколькими способами мы можем расположить 2-го мальчика, для него кол-во способов равно n-9*(2-1)-8 вариантов(т.к первые 9 девочек должны следовать до 1-го мальчика) 4) Теперь для k-го мальчика кол-во способов его поставить в очередь равно n-9*(k-1)-8 5) Получаем ответ на задачу: ans=произведение по всем k от 1 до m: n-9*(k-1)-8 6) выводим ans%(10^9+7) -
"т.к первые 9 девочек должны следовать до 1-го мальчика"
Можно сначала всех девочек а потом всех мальчиков.
Это была задача не на разбор случаев, а на обычную динамику.
И как решить?
fi, j — количество способов сделать так, что нужно еще обслужить i девочек и j мальчиков
Понятно, что ответ — это f0, 0
Изначально, все в нулях, кроме fn, m = 1.
Пересчет простой, мы всегда можем обслужить одну девочку.
fi - 1, j += fi, j.
Так же, зная сколько было изначально мальчиков и девочек, а так же зная кого обслужили мы легко можем определить хватит ли на текущего парня.
Если да, то fi, j - 1 += fi, j.
Все операции делаем по модулю.
Ну вот, собсна, и все.
Дает ли данная олимпиада какие-нибудь льготы при поступлении в вуз?
дает при поступлении в университет Иннополис. в остальные сомневаюсь.
Не даёт, так как олимпиады нет в перечне на 2015-2016 год.
Увидим ли мы эту олимпиаду в тренировках?
++++ добавьте в тренировки
Объясните кто-нибудь, как E на полный решать? Идеи есть, но немного сырые...
Na2a уже рассказал идею чуть выше.
А где условия прошедшего тура? Результаты? Архив с тестами?
У меня есть условия Условия
Результаты
http://olymp.innopolis.ru/informatics/ooi-2015-2016/
Кто может объяснить почему у меня WA 8? вот код http://pastebin.com/uLevbE0b
pastebin.com
Понял больше не буду добавлять код в комментариях...
Вы проверяете последнюю последовательность битов с нулевой, а вам надо с первой, так как у вас массив с единицы.
Если пройдешь на очный этап, то заезд и поселение за свой счет?
И еще вопрос: саму программу (что-то типо зимней школы и олмпиадка) нужно оплачивать?
Или для всех приглашенных участие бесплатное?
Опишите, пожалуйста, за что нужно платить.