Открытая олимпиада университета Иннополис по программированию 2015-2016

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	166
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	160
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

text

Привет всем!

Рад вам объявить, что в этом сезоне состоится вторая олимпиада университета Иннополис по программированию для школьников.

Олимпиада пройдет в два этапа: два отборочных тура и финальный. Отборочные этапы нужно будет писать через интернет, результаты отборочных туров будут подводиться независимо. По результатам каждого из отборочных туров лучшие участники будут приглашены в финальный этап Открытой олимпиады университета Иннополис. Участвовать можно в любом из двух туров и даже в обоих турах, если у вас не получилось пройти в финал с первого. Туры проходят по правилам заключительного этапа Всероссийской олимпиады школьников по информатике. В олимпиаде могут принимать участие только школьники, условия задач всех этапов на русском языке.

Первый отборочный тур состоится в воскресенье, 6 декабря в 10:00 по московскому времени.

Второй отборочный тур пройдет в субботу, 19 декабря в 16:00 по московскому времени.

Для участия в первом отборочном туре нужно зарегистрироваться на сайте до 23:59 5 декабря. В подготовке первого отборочного тура приняли участие: Нияз Нигматуллин (niyaznigmatul), Павел Маврин (pashka), Ильшат Сафиулин (ilsaf13), Дарья Яковлева (Devushka), Айдар Гизатуллин (lightning), Дмитрий Якутов (YakutovDmitriy), Илнар Сабирзянов (iilnar), Максим Корчагин (zclimber).

Финальный этап состоится в середине февраля в университете Иннополис, более точные даты будут известны позже. Все финалисты олимпиады будут также приглашены в зимнюю школу олимпиадной подготовки, которая продлится около 7-10 дней перед финальным этапом олимпиады.

Участвуйте. Всем удачи!

UPD: Результаты и материалы первого отборочного тура.
Контест в тренировках: 2015-2016 Открытая олимпиада Университета Иннополис, первый отборочный тур.

Комментарии (37)

Написать комментарий?

-emli-

9 лет назад, # |

Олимпиада ориентировано для школьников?

→ Ответить

Lord_F

9 лет назад, # ^ |

← Rev. 2 →

Вот да.

"Туры проходят по правилам заключительного этапа Всероссийской олимпиады школьников по информатике." — единственное предложение, которое намекает на "школьность" олимпиады.

UPD: обновлено :)

niyaznigmatul

Да, для школьников. Почему-то совсем не подумал про это, пока писал пост. Добавил пару фраз.

the_art_of_war

+11

первый отбор закончился. Но я нигде не могу найти количество участников, которые пройдут дальше.

Ralsei

Вряд ли это будет известно до окончания второго отбора.

"и даже в обоих турах, если у вас не получилось пройти в финал с первого."

Думаю, нет.

Elibay

Я не могу зарегистрироваться Upd оказывается в пароле не должно быть символов типа точки извиняюсь

craborac

Сколько по времени длится тур (5 часов)?

Да, 5 часов

kshj78

Как решать D?

← Rev. 7 →

Надо написать бинпоиск по количеству штурмовиков в ответе. Чтобы проверить, возможно ли такое количество штурмовиков, надо промоделировать "бой". Чтобы задача зашла на полный балл, надо использовать оптимизации:

1) Надо стрелять по врагам в порядке от человека с самым низким здоровьем и по возрастанию, не стреляя по следующему, пока жив предыдущий.

2) Надо предподсчитать количество выстрелов, которые надо сделать, чтобы убить всех врагов с 1 по i (в отсортированном порядке) (динамикой). Затем узнавать количество мёртвых врагов на данный момент можно за O(n) суммарно за весь бой — хранить указатель на первого живого, после, зная количество совершённых выстрелов (оно каждый раз увеличивается на количество союзников), сдвигать его вправо при надобности.

3) Точно также можно узнать количество живых союзников в конце хода, но, учитывая, что у них всех h здоровья, можно написать короче.

Соответственно, если в какой-то момент врагов становится 0, то возвращаем true, а если их больше 0, а союзников — 0, то false.

Это заходит на 70 баллов. Оптимизация для 100:

4) Надо перед каждым ходом посчитать, в течение скольки ходов никто не будет умирать, т.е. минимум из количества выстрелов, нужных для убийства хоть кого-нибудь из союзников, и нужных для убийства кого-нибудь из врагов. И затем "оптом" совершать такой ход.

Na2a

Двоичный поиск по ответу. Проверяем за (N+M), просто убивая по одному. Я просто находил через сколько ходов умрет след. человек и моделировал. Несложно понять, что оптимальное действие — убивать сначала слабых. #code

Badalyan_Shavarsh

разбор по Е пожалуйста тоже.

Я не знаю сколько там максимально ребер может быть, но я генерировал все ребра и поиском в ширину находил путь. Более подробно, каждый прямоугольник разбивал на два отрезка (вертикальный и горизонтальный). Далее, добавлял ребра между вертикальными отрезками и между горизонтальными отрезками отдельно. Генерацию для вертикальных отрезков делал так: сортировал сначала по X, дальше для каждого отрезка находил ближайший отрезок который с ним пересекается, убирал это пересечение и отрезок делился на два. Дальше спускался рекурсивно. Аналогично делал для горизонтальных отрезков.

Самый ближайший отрезок находил деревом отрезков (но перед этим сжал все координаты).

#code

P.S. Там не будет не больше 8 * N ребер.

nezametdinov

+22

Будет ли разбор от авторов?

deleteeeeeeeeed

deleted...

Karaev_Marik

Кто может объяснить почему мое решение по задаче 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) -