Всем привет.
В эту субботу, 19 декабря в 16:00 по московскому времени, пройдет второй отборочный тур олимпиады Университета Иннополис.
Участие могут принимать школьники, условия задач на русском языке. Олимпиада проводится по правилам Всероссийской олимпиады школьников по информатике. Для участия в отборочном туре нужно зарегистрироваться на сайте до 23:59 18 декабря. В отборочном туре могу участвовать все зарегистрированные, в том числе и те, кто уже получил приглашение на финал. Те, кто уже прошли, учитываться в подведении результатов второго отборочного не будут.
В подготовке второго отборочного тура приняли участие: Нияз Нигматуллин (niyaznigmatul), Павел Маврин (pashka), Ильшат Сафиулин (ilsaf13), Дарья Яковлева (Devushka), Дмитрий Якутов (YakutovDmitriy), Нияз Валидов (FireZi), Денис Архипов (disa), Тимур Хисматуллин (Timur_Keks), Илнар Сабирзянов (iilnar).
Финальный этап состоится в середине февраля в университете Иннополис, более точные даты будут известны позже. Все финалисты олимпиады будут также приглашены в зимнюю школу олимпиадной подготовки, которая пройдет c 13 по 20 февраля 2016 года перед финальным этапом олимпиады, стоимость участия в школе 8500 рублей. Победителям финального этапа олимпиады, которые участся в выпускном для себя классе, будут вручены гранты на обучение в Университете Иннополис.
Первый отборочный прошел две недели назад, его можно порешать в тренировках: 2015-2016 Открытая олимпиада Университета Иннополис, первый отборочный тур.
Решайте задачи!
Печаль. Е'шку не успел отдебагать.
у меня так с прошлой E получилось
У меня так на отборе на ВКОШП с задачей K. Тоже ДПшка была. :D
тебе кстати вначале E нужно было решать, там же простая динамика была.
Как решать D?
UPD: Ок, видимо, я неправильно прочитал условие :):
Комбинаторика.
Назовём "плохими" числа, которые есть и в первом и во втором массиве, "хорошими" — противоположные. Посчитаем кол-во "плохих" и "хороших" чисел в первом массиве (у которого размер N). Ответом будет сумма,
.
Чтобы загнать на 100 нужно быстро считать сочетания.
Как быстро считать сочетания? :P
UPD Понял. Ступил.
Код можно ?
http://codeforces.com/contest/575/submission/12864730
http://pastebin.com/QDuiuKep — на 85.
Можешь объяснить ??
Следовательно мы можем предпосчитать факториалы по модулю 109 + 7 до MAX(N, M) и использовать теорему Ферма для деления по модулю.
Так как M простое,
Значит,
Используя вышеописанную формулу + бинарное возведение в степень можно легко загнать на 100.
Для крайних оптимизаций — можно пойти дальше и за линию предподсчитать обратные факториалы. Тогда одна C-шка считается за O(1)
Кто В — wku решил можете код скинуть
http://pastebin.com/9WgwV5FW единственная проблема, нужно было использовать long double
http://pastebin.com/0mZ83unH
А объяснить В — wku можете
Решается за линию. Для каждого знаменателя возможно два случая:
1 есть один числитель максимально приближенный к изначальной дроби a/b
2 есть два числителя максимально приближенных к изначальной дроби a/b
Для того чтобы найти эти числители составляем уравнение: x — числитель, который мы хотим найти, i — текущий знаменатель
x/i=a/b
x=(a*i)/b
отсюда находим x, и так как X в большинстве случаев будет дробным, то наш ответ будет либо в верхнем округлении, либо в нижнем. Округляем и вверх и вниз, дальше находим разницу между получившимися дробями и изначальной, если разница лучше чем была раньше, то к ответу прибавляем 2, если разница равна между двумя дробями или 1, если не равна. Изначально минимальную разницу заполняем каким-нибудь большим числом.
Выложено в тренировки
2015-2016 Открытая олимпиада Университета Иннополис, второй отборочный тур
Пороговый балл? :]
думаю будет 300 для 11 класса, как после первого отборочного тура