Hello!

Tomorrow (the 3rd of November) will held the Nothern Subregion Quarterfinal 2012 in the Northeastern European Region.

I think, it will be very interesting to watch the "battle" between teams, because in our quarterfinal participate 3 persons from the top10 in Codeforces rating. And jury made all to make this quaterfinal very interesting and unpredictable.

Also, don't forget, that you can participate in Yandex.Contest.

Здравствуйте!

Скоро состоится событие, которого некоторые с нетерпением ждали, а, именно, финал второго по счёту соревнования "Russian Code Cup". Сможет ли Petr защитить своё звание? Нам пока неизвестно. Известно только то, что победитель будет один.

А для того, чтобы выделить этого самого единственного, работала целая толпа членов жюри. И я практически уверен, что большему числу участников и зрителей понравится проблемсет.

А пока — удачной дороги всем участникам.

Похоже, все участники доехали. И ценным призом оказался "АВТОМОБИЛЬ", шутка. Каждому достались "Заметки о мотивации" Анатолия Абрамовича, а также "Lego: Mindstorm".

P.S.: Не забывайте про онлайн-трансляцию на сайте, она обещает быть достаточно интересной.

Здравствуйте!

И вот ОН грядёт! В эту субботу — 16 июня в 11-00 по московскому времени состоится эпическая битва, которая должна всем надолго запомниться — 550 человек падут, и останется только 50. Может быть, это будете вы?

Приглашаются все, кто прошёл квалификационные раунды. А также болельщикам вход не запрещается...

P.S.: Опубликован официальный разбор.

P.S.: Видео-разбор — от него iPhone andrewzta раскалился.

До свидания.

Здравствуйте!

Приглашаю поучаствовать в третьем и последнем квалификационном раунде Russian Code Cup, который пройдёт в ближайшее воскресенье — 10 июня. Естественно допускаются все желающие, кроме тех, кто уже прошёл в следующий раунд.

Не забудьте зарегистрироваться. А то последний розыгрыш футболок "Russian Code Cup 2012" пройдёт мимо вас.

И да пройдут сильнейшие из вас! Удачи! И да покорятся вам эти великолепные задачи с лёгкостью, и да поимеете вы удовольствие с этого раунда.

P.S.: Выложен официальный разбор задач — http://russiancodecup.ru/round/8/analysis.

P.S.: Видео-разбор, сделан с помощью телефона andrewzta.

Здравствуйте!

Кто ещё не участвовал или не прошёл с QR 1 приглашаются на QR 2, который состоится в эту субботу (2 июня, в 11:00 по Московскому времени). Будет весело. Присоединяйтесь.

Мы постарались учесть полученные замечания. (Но я всё равно в жюри — значит, не все. :-)!)

Забыл. Предоставляю ссылку — http://russiancodecup.ru. И будьте точно уверены, что вы зарегистрированы...

До свидания!

P.S.: А первым 200 участникам полагается футболочка. Заметьте, вторую получить нельзя, если вы уже квалифицировались, так как Вы не можете участвовать в этом раунде.

P.S.: А вот и разбор: http://russiancodecup.ru/round/7/analysis.

**P.S.: Я попробовал ввести инновации и модернизации пока не совсем официально, спасибо спонсорам pashka и andrewzta за предоставленные айфоны для съёмки. Собственно, видео-разборы: http://www.youtube.com/channel/UCjum2OyCTe4wt_fkldljOrw?feature=mhee. **

Здравствуйте все!

Возможно, некоторым уже известно, а некоторые забыли или даже не знали, что в ближайшее воскресенье (27 мая 2012 г.) в 11:00 по Московскому времени состоится первый квалификационный раунд RCC 2012.

Задачи обещают быть хорошими, а борьба, надеюсь, будет жаркой, вне зависимости от того, что это только квалификационный раунд.

Я думаю, что не будет лишним написать ещё раз ссылку — Русский кодо-кубок.

Желаю удачи на раунде.

Член жюри.

Председатель жюри : andrewzta.

Координатор задач : Joshik.

Раунд подготовили : Павел Кротков pashkal, Николай Ведерников Niko, Андрей Комаров komarov, Демид Кучеренко BLIZZARD, Владимир Ульянцев, Антон Ахи anton.akhi и Aksenov239.

Помогали в подготовке : Антон Банных anton.bannykh и Владислав Исенбаев winger.

Опубликован разбор задач: http://russiancodecup.ru/round/6/analysis

Если кому-то хочется посмотреть на доказательство равенства простых — http://codeforces.net/blog/entry/4625#comment-94117.

P.S.: Если что-то не совсем понятно в правилах пишите в службу поддержки — http://russiancodecup.ru/feedback/.

Ни одна из задач не была специально взята с "Wikipedia". Для меня было очень поразительно, что задача "B" была там.

A (Div 2). (Идея : Gerald, реализация : Aksenov239, код : 1670635)

Если длины строк не равны — то ответ "NO". Далее мы ищем позиции, на которых символы в строчках не совпадают. Если таких позиций не 2 — "NO". Иначе меняем 2 символа не этих позциях в первой строке, и сравниваем строки.

B (Div 2). (Идея : Aksenov239, реализация : Aksenov239, код : 1670637)

1. Можно заметить, что всё можно считать в целых числах, так как k — целое число процентов.
2. Для каждого гнома мы находим оптимальную стратегию — то есть проверяем 2 стратеги и выбираем лучшую.
3. А далее просто сортируем.

A (Div 1). (Идея : Aksenov239, реализация : Aksenov239, код : 1652592) Предположим, что после i-го года, у нас было x треугольников вверх и y треугольников вниз. После ещё одной итерации можно заметить, что количество треугольников стало — 3x + y вверх и x + 3y вниз. Рассмотрим разницу между ними: на i-ый год она равна x - y, а не i + 1-ый — (3x + y) - (x + 3y) = 2 * (x - y). Теперь ясно, что разница между количеством треугольников за год увеличивается в 2 раза. Так как на i-th год разница становится 2ⁱ и всего треугольников 4ⁱ. То на i-ый год количество треугольников, направленных вверх — . Это можно посчитать по модулю p, используя алгоритм быстрого возведения в степень.

B (Div 1). (Идея : Aksenov239, реализация : Aksenov239, код : 1652597) Ответ на эту задачу: .

Доказательство: . (Это неравенство о среднем арифметическом и среднем геометрическом. Для тех, кто желает ознакомиться.)

Равенство достигается только при .

Но надо не забывать про нули. Если a = b = c = 0 — вы должны выбрать какую-нибудь подходящую точку — x + y + z ≤ S.

C (Div 1). Без комментариев. :-)!

D (Div 1). (Идея : Aksenov239, реализация : cerealguy, Gerald, Aksenov239, код : 1652604)

Это задачка на теорию чисел.

Постараюсь объяснить всё по шагам:

1) Сначала докажем, что НОД чисел не больше 2.

Пусть . Возводим обе части в квадрат , а нам нужно, чтобы . Это означает, что d может быть только 2.

2) Сделаем наше длинное произведение покороче.

.

Мы это можем посчитать по модулю p быстро, и поделить на 2^r - l, если k — нечётное.

3) Но есть несколько ловушек.

Первая — это не работает, когда p = 2 — но Вы справитесь сами.

Другая проблема посложнее, что если , это означает, что для любого i ≥ l : , из чего следует,
что для любого i ≥ l : k²ⁱ + 1 ≡ _p2. И наше произведение по модулю p равно 2^{r - l + 1}.

E (Div. 1) (Идея : Aksenov239, реализация : cerealguy, код : 1652611)

Эту задачу не взяли на РОИ, поэтому я предложил её здесь. На мой взгляд, задача вполне сложная. Если честно, я точно не знаю, что написал cerealguy, но его решение работает за O(nlogn) — без бин-поиска. Для меня это достаточно уже сложно, так как первоначальное решение было с ним. (Вроде, даже такие решения прошли.) Также были ещё решения с более худшей асимптотикой, но некоторые даже быстрее работали.

Я могу Вам только дать ключевые идеи решения, которые Вам помогут. (В конце концов, вы можете посмотреть решение cerealguy)

Идеи:

1. Для каждого гнома найдём ближайшее метро. Это можно сделать за nlogn с помощью дерева отрезков или чего Вам там больше нравится.
2. Можно заметить, что если гном идёт до метро, то другие гномы с меньшим расстоянием до метро, могут тоже идти туда — это никак не повлияет на ответ. Поэтому отсортируем гномов по этому расстоянию.
3. Точки, до куда гном может дойти за t секунд, представляет собой ромб. И мы можем пересечь все ромбы за O(n) — пересечение будет похоже на прямоугольник.
4. Построим начальное пересечение, когда никто не идёт в метро. Мы получим прямоугольник.
5. Основная идея — для прямоугольника пересечения — ближайшее к нему метро всегда остаётся одним и тем же. Теперь можно пройтись по гномам в отсортированном порядке, мы умеем быстро пересчитывать прямоугольник пересечения — и поэтому можем быстро пересчитывать ответ.

И у нас получается решение за O(nlogn). Та-дамс!

Спасибо за Ваше внимание и понимание. Мне очень стыдно, за то что я натворил с задачей "C".

Здравствуйте! Уже в ближайшее время состоится второй раунд, в создании которого я принимаю участие. (Первый был — Codeforces Beta Round 56.) Он будет несколько похож на предыдущий. (Но тот вроде бы был не так плох. :-)!) Надеюсь этот Вам тоже понравится.

Собственно я являюсь автором всех задач кроме одной, которую мне как раз предложил Gerald.

Огромное спасибо Gerald за всё, он постоянно улучшал мои задачи.

Так же соавтором со вчерашнего дня является cerealguy, который подготовил, на мой взгляд, самую сложную задачу в наборе. (Он стал соавтором после прорешивания первой версии контеста где-то за один час. :-)!)

Также благодарность pashka, который в самом начале подготовки оценивал задачи.

Конечно же спасибо главному переводчику кодефорсес — Delinur.

А также спасибо системам "Polygon" и "Codeforces" при реализации раунда

И без грибов не обойдётся и этот раунд!

Здравствуйте Дамы и Господа! В 11-00 19 июня (т.е. в воскресенье;) состоится отборочный раунд на финальный раунд соревнования "Russian Code Cup 2011". (Извините за тавтологию;) В финал выйдет всего 50 человек, т.е. конкурс будет достаточно серьёзный. (50 из 600;)

Good luck and have fun!

P.S.: Сайт - russiancodecup.ru. Там же Вы можете найти правила.

Здравствуйте! Хочется Вам напомнить, что через некоторое время - в 17-00 15 мая (воскресенье;) состоится третий и последний квалификационный раунд "Russian Code Cup" в данном турнире. В данном раунде распределятся последние 200 мест в следующем раунде, а также 200 футболочек. Хотите футболочку? Всё зависит от Вас!

Good luck and have fun!

P.S.: Сайт - russiancodecup.ru. Там же Вы можете найти правила.

Вчера, у меня на кружке по программированию был семиклассник, у него я подглядел несколько задач по математике. Вы можете проверить свои силы. И понять - "Умнее ли Вы семиклассника?".

1); Докажите, что если , то .

3); Дан четырёхугольник ABCD. AB = BC, , , . Найти углы четырёхугольника.

Здравствуйте! Хочется Вам напомнить, что через некоторое время - в 11-00 14 мая (суббота;) состоится второй квалификационный раунд "Russian Code Cup". В данном раунде распределится ещё 200 мест в следующем раунде. Может оно предназначено Вам? И ещё система была немного подредактирована - появились попытки и всякая всячина.

Good luck and have fun!

P.S.: Сайт - russiancodecup.ru. Там же Вы можете найти правила.

Здравствуйте! Хочется Вам напомнить, что через некоторое время - в 11-00 8 мая (воскресенье;) состоится первый квалификационный раунд "Russian Code Cup". Всем на нём удачи! Надеюсь, задачи Вам понравятся.

P.S.: Напоминание - из этого квалификационного раунда проходят в следующий раунд 200 человек. Сайт - russiancodecup.ru. Там же Вы можете найти правила.

UPD: Выложены тесты к первому квалификационному раунду.

Добрый день!

Автором задач сегодняшнего контеста являюсь я. (Очень информативно - не правда ли? :-)!) На сегодняшнем контесте Вы познакомитесь с большим количеством забавных персонажей, которые попали в переделки, из которых Вам нужно помочь им выбраться.

Раунд помогали подготавливать Артём Рахов (которому особая благодарность;) и Мария Белова.

Желаю всем высокого рейтинга!

Разбор задач.

P.S.: Надеюсь люди, которым нравится этот контест (я про кнопочку;) сохранят своё мнение после контеста, и количество таких людей увеличится. :-)!