Hi, all!

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 :(

ios::sync_with_stdio(false);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!