Заболел

He and KUTcoder (who solved 500 under 3 minutes) have been banned. Good job, TC staff!

Now this is much closer but what do people think of Dshawn's submission in 1 minute 18 seconds? Looking at this code it seems hard to imagine that one could read the problem statement that fast and code the check function he has in so little time. But he is not banned so I guess unlike kutengine the topcoder admins think this is legit.

Let answer is 2^a₂·3^a₃·... (Notice that we should consider only primes  ≤ 10⁴) So we have to find a_p for each p. Let α is maximal number such that p^α ≤ n (linear multipliers will never be divided by bigger powers of p). Let's fix x modulo p^α. Now for every multiplier (x - a) we can calc maximal r such that p^r divides (x - a) for current x. Then we should find minimal sum of r-s among all possible values of x modulo p^α. That approach is O(n³).

But it is easy to see that p^r divides (x - a) only if x = a modulo p^r. So, we can enumerate r and find d[r][i] — sum of powers (from the problem) of multipliers divisible by p^r with x = i. And finaly for every f(k) = d[0][k / p^α - 1] + ... + d[α - 1][k]}. Min of f(k) is a_p.

Here's how to binary search.

Suppose we want to check if we can make x rounds. Now, we already have E easy problems, so we need max(0,x-E) more easy problems. This can only come from easy/med problems. Similarly, we already have H hard problems, so we need max(0,x-H) more hard problems. This can only come from the med/hard problems.

So, we check EM >= max(0,x-E) and HM >= max(0,x-H). Now, we put everything else for the medium, so we also check that EM-max(0,x-E) + HM-max(0,x-H) + M >= x.