I am the author of the last problem.

Let dp[i][j] be the maximum possible amount that Mirko can win in game with i rounds and j opponents at the beginning, divided by 100 000. dp[i][j] = min (dp[i — 1][j — k] + k / j), for k in 1, 2...j It is enugh to get 20 points.

To get 50% you need some observations. Let a_1, a_2...a_k be the number of people that have been thrown out in each round. It's not hard to prove that a_1 >= a_2 >= ... >= a_k. Also a_1+a_2+...+a_k = n so we get a_i <= n/i, because otherwise we would have a_1+a2+...+a_k > n. Because of that dp[i][j] = min (dp[i — 1][j — k] + k / j), for k in 1, 2,...n/i so total complexity is now n*(n+n/2+...+n/k) = n^2*(1+1/2+...+1/k) = n^2 log k and that is enough to get 65 points.

To get 100% you have that see that dp[i][j+1] — dp[i][j] <= dp[i][j] — dp[i][j — 1] which means that we can use aliens trick.

More about aliens trick you can learn here. https://ioinformatics.org/files/ioi2016solutions.pdf (the last problem, subtask 6.)

Nevermind, didn't read the FAQ. It says:

4. Should I use %lld or %I64d for long long input/output in C++?
%lld.

I'm not sure if you still need it, but I'll leave you my code for the problem here Code

Suppose after a mega move number at node X moves to node Y. Add an edge between X and Y. If you do this for all N * M nodes, the whole parallelogram will be decomposed into some simple cycles. K must be equal to lcm of those cycle lengths.

Let the prime factorization of K be p₁^a₁p₂^a₂...p_k^a_k. We must have . This condition is both necessary and sufficient for the existence of answer. Because it is possible to swap any 2 adjacent nodes of the parallelogram with the given operations. For example applying T(x - 1, y - 1), T(x - 1, y - 1), R(x - 1, y - 1) consecutively swaps numbers at nodes (x, y) and (x - 1, y). Since now we can swap 2 adjecent numbers, it's not hard to construct cycles of lengths p₁^a₁, p₂^a₂, ..., p_k^a_k