I'm the author of today's contest. On today's contest you will meet with a big amount of funny persons (or not only persons; :-)!), who had problems, and you should try to help them.
This Round was prepared with help of Rakhov Artem and Maria Belova.
I wish you high ratings!
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 :(
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 + S[N]); f(0) = sum, where sum == summation of all elements in S.
The solution to this recursion is sum * 3^X - (S + 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. 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 + 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!