There are R consecutive slots numbered from 0 to R-1. Then, you're given N people. The i-th person puts exactly one marble in some of the slots, as described by the numbers s_i, e_i and k_i. That way the i-th person put marbles in the slots is as following:
1 — it starts at slot 0.
2 — it skips s_i slots (including the current slot where the person is standing)
3 — repeat the following k_i times: put one marble in the next 2^e_i slots and skips the next 2^e_i slots.
4 — repeat the process from step 2 until it reaches slot R-1 (the last one).

The question is: after all the persons passed through the slots, what is the maximum number of marbles in any slot?

Constraints:
(3 <= R <= 10^100)
(1 <= N <= 10000)
(0 <= s_i <= 10^9)
(0 <= e_i <= 21)
(1 <= k_i <= 10^9)
NOTE: The answer fits in a 32 bit integer.

Hi guys everywhere. Suppose that some guy post some VERY fast polynomial solution to 3-SAT, for example. Would that make programming contests boring from that moment?

So, here is the problem:

You have N circles on a plane, with (4 <= N <= 50000). For each circle, you have the coordinates of the center and the radius (all of them are specified with floating-point numbers). You have to output the radius of the largest circle you can put inside the rectangle formed by the center of the first 4 circles of input, such that this circle doesn't touch any of the other ones given circles nor is inside of any of the other given circles.

Constraints: - no circle intersect another circle on input. - no circle is inside another circle on input. - no circle has radius <= 0. - no two centers of the given circles coincide. - the output radius should have precision 10^-6.

That's it! I would really appreciate some hint.