The plates must touch the edge of the table, so their centers must lie on the circle with radius R - r (see the figure).

*a*= 2(

*R*-

*r*)

*sin*(π /

*n*), it can be easily deduced. For that you should consider the right triangle (the green one in the figure).

*r*= (

*R*-

*r*)

*sin*(π /

*n*) (*) holds. Because of the computational error the right-hand side can get larger than the left-hand one. This can result in answer "NO" instead of "YES". Comparison in such cases should be performed with a small ε:

*a*+ ε <

*b*instead of

*a*<

*b*,

*a*<

*b*+ ε instead of

*a*≤

*b*.

*a*and

*b*, if they are distinct. In particular, for computations by the formula (*), taking into account the constraints of the problem, this difference may be approximately 7· 10

^{ - 7}. So ε = 10

^{ - 7}is sufficient, but ε = 10

^{ - 6}is not.

1 | 2 | 3 | 4 | |

{1} | - | 1 | 1 | 1 |

{1, 2} | 2 | 1 | 1 | 1 |

{3, 1, 2} | 3 | 3 | 1 | 3 |

{3, 1, 2, 4} | 3 | 3 | 1 | 3 |

*O*(

*n*

^{2}) solution.

**Solution 1.**Suppose that the answer is k. If there are more than k equal among the given numbers, it's clear that we can't use them all (we can't use equal snowballs in the same snowman). So we leave k snowballs of them, and discard the rest. Then, sort the radii in the non-decreasing order. After that every two snowballs with numbers i and k + i are different. Make snowmen of snowballs with numbers (1, k + 1, 2k + 1), (2, k + 2, 2k + 2), (3, k + 3, 2k + 3) and so on. If the total number of snowballs is not less than 3k, we always manage to make k snowmen. Now we can for the fixed k answer to the question, if k snowmen can be made, so k can be chosen by binary search.

**Solution 2.**Count quantities of snowballs of each size, choose greedily the three largest quantities, take a snowball from each of them, make snowman and continue the process, while it's possible. Why is it correct? Let k be the answer for the problem. If there are quantities larger than k, we will count them as k, because other snowballs in them will not be used in any way. We prove the correctness of the algorithm using

*Proposition*: if every quantity is ≤

*k*and the total quantity of snowballs is ≥ 3

*k*, then it's possible to perform a step of the algorithm.

*k*- 1, and their total sum is ≥ 3(

*k*- 1). Thus, we always can perform k steps and get the answer k.

**Solution 1 (greedy).**Optimal order to solve problems is an increasing (non-decreasing) order by their difficulties. Problems solved before the New Year must be submitted at 0:00, ones solved after the New Year must be submitted just after finishing their solutions.

*descent method*. General scheme of reasoning is the following. Suppose you have the optimal order which is not the increasing order by problems' dificulties. Show that it is possible to come (to descend) from it to another variant, that is not less optimal. As a result you come to the sorted variant by such steps.

*T*+

*a*

_{i}) + (

*T*+

*a*

_{i}+

*a*

_{j}), where T is a time of the beginning of solution for the first problem,

*a*

_{i}is a time for the solution for the first problem,

*a*

_{j}<

*a*

_{i}is a time for the solution for the second problem. After the swap of these problems we get the penalty (

*T*+

*a*

_{j}) + (

*T*+

*a*

_{j}+

*a*

_{i}), that is less than (

*T*+

*a*

_{i}) + (

*T*+

*a*

_{i}+

*a*

_{j}). It remains to consider cases when one of the consecutive problems that are in the "wrong" order "intersects the New Year". These cases can be treated similarly.

*a*

_{i}to a smaller one doesn't spoil an answer. Rigorous proof can be obtained by the same descent method.

**Solution 2 (dynamic).**First of all, as in the previous solution, choose the maximal number of the easiest problems that Gennady has time to solve. Discard the remaining tasks. Try every problem as one being solved in the moment of the New Year (0:00). Remaining problems (except it) must be divided into two sets. One is for solving before the New Year, and another is for solving after the New Year. Problems in the second set must be solved in increasing order of their difficulties (it is a well-known fact for everybody participating in contests by ACM rules). In the first set an order of solving is immaterial. Sort the given numbers in increasing order, and count the dynamics d[i][j][k] that is the smallest possible penalty, if there are the first i problems solved, j from them are solved after the New Year, and the last problem after the New Year was solved at the moment k. Note that the triple (i, j, k) uniquely determines the number of problems solved before the New Year and the total time needed for their solutions. After calculating the dynamics, recollect the problem being solved exactly at 0:00 (it was not taken into account in the dynamics). Try moments of time before the New Year when its solutions starts, and count remaining problems using the dynamics we already has.

*subtask*for one layer. It consists in finding the number of ways to compose a garland of lengths s with lamps of exactly k colors such that no two consecutive lamps have the same color. Variants different only by an order of colors are considered to be the same (we always can multiply by k! if we need). The solution of the subtasks is required only for

*k*≤

*s*≤ 5000, so can be done by

*O*(

*s*

^{2})-dynamics:

*j*≤

*l*

_{i}(!). All d[i][j] can be calculated in

*O*(

*L*) operations, because sets of colors with different cardinalities are always different (!!). Indeed, put d[i][j] =

*A*

_{m}

^{j}* a[l[i]][j] * (sum of all d[i-1][k]), and then subtract variants with equal sets on the i-th and (i-1)-th layers. Coefficients

*A*

_{m}

^{j}=

*m*(

*m*- 1)... (

*m*-

*j*+ 1) can be pre-calculated because they are required only for

*j*≤ 5000.

*O*(

*L*+

*s*

^{2}) (

*L*≤ 10

^{7},

*s*≤ 5000), and it doesn't use division (only addition and multiplication modulo p).

*x*

_{c},

*y*

_{c}). Consider all points symmetrical to (

*x*

_{i},

*y*

_{i}) with this center. They are of form (2

*x*

_{c}-

*x*

_{i}, 2

*y*

_{c}-

*y*

_{i}). It is necessary to check that they all except may be k of them are in the set {(

*x*

_{i},

*y*

_{i})}. It can be done in by binary search (if the set was previously sorted). But there is more effective way of check in

*O*(

*n*). Note that if initially the points (

*x*

_{i},

*y*

_{i}) were sorted, say, by x-coordinate in increasing order and in case of equal x by y, then the points of the form (2

*x*

_{c}-

*x*

_{i}, 2

*y*

_{c}-

*y*

_{i}) will be sorted in the reverse order. The order doesn't depend on the center (

*x*

_{c},

*y*

_{c}). So we can check the points (2

*x*

_{c}-

*x*

_{i}, 2

*y*

_{c}-

*y*

_{i}) in the order of sorting moving a pointer in the sorted array (

*x*

_{i},

*y*

_{i}).

*O*(

*n*). Asymptotics of the solution is

*O*(

*nk*

^{2}).

In conclusion, a couple of words about the difficulty order in the problemset must be said. Difficulty of a problem is subjective. Especially if we need to compare a problem with idea and nearly without implementation and implementation without idea. As a result, different participants form different preference lists (russian). I can't deny that the order chosen during preparation of the contest appeared to be inadequate with the number of solutions for the problems, and it surely can be not liked by someone personally. Nevertheless, I want to say a couple of words in its support. Namely, about principles we have used to choose it.