The plates must touch the edge of the table, so their centers must lie on the circle with radius R - r (see the figure).
In case the plates have the largest radius possible for the given table, their centers are situated in the vertices of the regular polygon (n-gon) inscribed in this circle. The problem is to find the length of the side of the inscribed regular n-gon and to compare it with 2r. The formula for the length of the side is 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).
In implementation, be careful with a case when the equality 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 constant ε should be chosen in such a way, that it is smaller than any possible difference between precise values of 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.
Once again, I focus your attention on the fact that the choice of ε depends on specific formulas used for computations and comparisons. Different solutions can be accepted or not with the same ε.
This problem was just a problem on implementation. Note that a number of a send card is uniquely determined by a number of a friend and a set of cards Alexander already has at the moment. Consider the sample form the statement.
| 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 |
The first column of the table contains sets of cards that Alexander gets after having received a next card each time. Numbers in the sets are written in order of Alexander's preferences. Each i-th of the next four columns contains numbers of cards that the i-th friend will get from the corresponding sets. Our goal is to choose for each friend the most preferred card in his column.
Note that to determine by the current Alexander's set and the number of the friend a number of a card received by this friend, it is not necessary to know the whole Alexander's set. The two most preferable cards are sufficient. So for each time moment find the two most preferable cards for Alexander. Using them, determine which of them will be send to each friend (find the numbers in the columns). Then choose the element with the maximum priority in each column. We get the O(n2) 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 ≥ 3k, then it's possible to perform a step of the algorithm.
Proposition is valid because by Pigeonhole principle there are no less than three non-zero quantities. If there are 3 (or more) quantities equal k, then k steps of the algorithm can be performed. If there is one or two such quantities, by the first step we certainly decrease them and come to a similar situation with k - 1. If there are no quantities equal k, after the first step we obtain quantities ≤ k - 1, and their total sum is ≥ 3(k - 1). Thus, we always can perform k steps and get the answer k.
From the point of view of implementation, in the second solution it is easy to calculate quantities for each size of snowballs (using sorting and scaling). Use set to work with these quantities. The time for the both solutions is 
.
.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.
Let us prove the optimality of this solution by the 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.
So suppose that there is a pair of problems in the optimal solution such that their difficulties are going in decreasing order. Then there are consecutive problems with this property. Suppose they both are solved before the New Year. Then the swap of them doesn't influence the penalty (it doesn't decrease). If the both problems are solved after the New Year, then their contribution to the total penalty is (T + ai) + (T + ai + aj), where T is a time of the beginning of solution for the first problem, ai is a time for the solution for the first problem, aj < ai is a time for the solution for the second problem. After the swap of these problems we get the penalty (T + aj) + (T + aj + ai), that is less than (T + ai) + (T + ai + aj). 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.
In case when Gennady hasn't time to solve all problems, you should choose the maximal possible number of the easiest problems. Indeed, it doesn't make sense to solve a more difficult problem instead of an easy one: change of a larger ai 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.
First, let us solve the 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(s2)-dynamics:
a[s][k] = a[s-1][k-1] + a[s-1][k] * (k -1).
They would be Stirling numbers of the second kind, if there was not a restriction about different colors of consecutive lamps.
Then, calculate the dynamics d[i][j] that is a number of ways to compose a garland for the first i layers according to the rules, such that the i-th layer contains exactly j different colors. There will be about L positions (the total length of the garland), because every layer can't contain more colors than its length: j ≤ li (!). 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] = Amj * 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 Amj = m(m - 1)... (m - j + 1) can be pre-calculated because they are required only for j ≤ 5000.
Thus, the author's solutions works in O(L + s2) (L ≤ 107, s ≤ 5000), and it doesn't use division (only addition and multiplication modulo p).
Start with the check of a candidate symmetry center (xc, yc). Consider all points symmetrical to (xi, yi) with this center. They are of form (2xc - xi, 2yc - yi). It is necessary to check that they all except may be k of them are in the set {(xi, yi)}. 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 (xi, yi) were sorted, say, by x-coordinate in increasing order and in case of equal x by y, then the points of the form (2xc - xi, 2yc - yi) will be sorted in the reverse order. The order doesn't depend on the center (xc, yc). So we can check the points (2xc - xi, 2yc - yi) in the order of sorting moving a pointer in the sorted array (xi, yi).
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 (xi, yi) were sorted, say, by x-coordinate in increasing order and in case of equal x by y, then the points of the form (2xc - xi, 2yc - yi) will be sorted in the reverse order. The order doesn't depend on the center (xc, yc). So we can check the points (2xc - xi, 2yc - yi) in the order of sorting moving a pointer in the sorted array (xi, yi).It follows from the previous reasoning, that if a set has a symmetry center, then the first point (in the order of sorting) forms a pair with n'th, the second one with (n-1)-th and so on. Since up to k points have not a pair, try the first (k+1) points from the beginning and (k+1) from the end of the array. For every pair of these points find the midpoint and check it in O(n). Asymptotics of the solution is O(nk2).
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.
Score for a problem is, first of all, its "price". Ability to solve problems with idea, IMHO, must have higher price then ability to solve implementation problems. Because everybody can learn to solve implementation with level like problem B. But idea with sorting in problm D, as I saw, was not invented by several strong and experienced participants. About the order of the problems, I can say that nobody makes you to solve them exactly in this order. It is not bad, if you fast get an idea for C or D, solve them before B, and get more scores. Many contestants acted this way. Moreover, the current standing is available that can help you to choose right problems to solve.
. Choose maximum among left-hand sides and minimum among right-hand sides and obtain an inequality in the form 
, 
, 
, 
, and so on, i.e. the roots of integers, that can be represented as 
, 
, ... In some cases we can take first 
