Добрый день!
Автором задач сегодняшнего контеста являюсь я. (Очень информативно - не правда ли? :-)!) На сегодняшнем контесте Вы познакомитесь с большим количеством забавных персонажей, которые попали в переделки, из которых Вам нужно помочь им выбраться.
Раунд помогали подготавливать Артём Рахов (которому особая благодарность;) и Мария Белова.
Желаю всем высокого рейтинга!
P.S.: Надеюсь люди, которым нравится этот контест (я про кнопочку;) сохранят своё мнение после контеста, и количество таких людей увеличится. :-)!
А в принципе, можно прочитать условия, и тогда решить, что делать. Если ничего не сабмитить, то контест учитываться не будет.
Похоже такое впервые - )
Надеюсь когда нибудь контесты будут проходить при участии пятизначного числа участников.
:)
3. Register, check yourself in registrants (
А вообще да - это старая бага.
Update: исправили, спасибо.
Вот даже обидно: давно уже Гене идею задачи для контеста предлагал, где, в частности, надо было знать, что такое пифагорова тройка. Так Гене не нравилось, что это не общеизвестный математический факт. А теперь уже засвечена.
Зато, правда, он первый эту задачу сдал.
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=42
http://acm.mipt.ru/judge/problems.pl?problem=127
А вообще говоря идеи потому и не патентуются, потому что они могут прийти в голову любому. Например, на локальных тренировках я дал одну задачу на идею, которую раньше нигде не видел. И что же - на сборах в Петрозаводске попалась задача с той же самой идеей, и вот недавно я обнаружил задачу - ну копия моей - тут на Codeforces, с тем лишь отличием, что тут были своего рода мультитесты.
Так что... сожаление сожалением, а всегда надо быть готовым нагенерить новых идей, более сложных и более интересных.
фазы луныкол-ва посылок и тестов в задачах.And I did realize if i write something with leading spaces for hacking(i.e without using generators), all leading spaces are automatically removed. It took me two unsuccessful hacks to know that :(
Частично, опыт.
Пичалька :'(
А так занял 240 место и слил 70 рейтинга. Всего -100 баллов, а какой эффект!
Смотрю, сколько рейта прибавили те, кто набрал столько баллов и бьюсь головой об стенку.
при этом старый рейн ТЕХ должен быть хотя бы примерно равен старому твоему рейтингу, иначе это бред у тебя получается. Например сержант при 100-ом месте набирает в несколько раз больше чем капитан!
Ну это само собой.
P.S. Кстати, а может кто-нибудь объяснить, почему моё решение по C в худшем случае не ловит TL за 106*O(n2)? :-[
Гена взломал мое решение по С
отсылаю его в дорешивании, а оно проходит полностью(время <0.5 сек)
видимо успешные взломы не добавляются в полную проверку
UPD: всё, нашла уже ответ)
http://www.ideone.com/WIBXx
Can I know what's wrong with my solution for E?
My code is here: http://pastebin.com/AQdbqw4E
My idea is:
Let the array be S with elements from 1 to N. Let f(x) be the sum of all elements after k moves.
Then f(x) = 3*f(x) - (S[1] + S[N]); f(0) = sum, where sum == summation of all elements in S.
The solution to this recursion is sum * 3^X - (S[1] + S[N]) * (3^X - 1) / 2
We can use this to calculate what happens in the first X moves. After that, the elements will be sorted. The leftmost element, the smallest element, will still be S[1]. However, we need to find what the rightmost element, ie the largest element, is. After some testing (proven by bruteforce XD, can anyone share a formal proof?), I realised this.
Let g(x) be the largest mushroom after x turns. Then g(x) = g(x-1) + g(x-2). Define g(0) = S[N] and g(-1) = S[N-1]. It is sort of like a fibonacci sequence.
After getting the leftmost and rightmost numbers in the new sequence, we can use the same idea in the first part and plug it into new_sum * 3^Y - (S[1] + g(x)) * (3^Y - 1) / 2. Then we can get the answer.
However, I get WA :(. One error I can think of is that in my solution to the recusion, I am doing division by 2. However, it seems that division in modulo does not work very well. I am not sure how to solve this problem. Can someone help me? Or does anyone have a better solution?
Thanks in advance!