On Sunday, May 31, the last 3rd qualifying round of the RCC 2015 passed. Problem A (Buying a bicycle) Grigori Reznikov (grikukan) was the first in 1 minute and 49 seconds, he was the first to deal with tasks B (Digital roots) and C (Two snails) - 7:26 and 18:39 respectively. Adam Bardashevich (subscriber) was the first to solve problem D (Slot machines) in 14 minutes and 20 seconds.

Oleg Merkuryev (Merkurev) became the first in solving the last task E (Internet pipeline) - 1 hour and 1 minute. At the end of the 3rd round, the first line in the standings was occupied by Evlebov Gleb (GlebsHP) from Moscow.
')
Some facts: 3762 programmers fought in the round, 664 of them sent at least one correct solution. In total, 3536 solutions were sent per round. 202 best participants were qualified (3 places shared the 200th place). 3 participants were disqualified by the jury. 604 participants qualified in three rounds will compete on June 14 for the title of finalist. All participants in the qualifying round will receive online certificates, and the 200 best ones will receive RCC 2015 T-shirts.

Problem A. Buying a bicycle

Idea: Vitaly Aksyonov
Implementation: Dmitry Filippov
Analysis: Dmitry Filippov

By the condition of the problem, it is necessary to say whether it is possible to find such numbers a ₁ , b ₁ by given numbers a, b, c , that a ₁ ≤ a, b ₁ ≤ b and a ₁ + 2 · b ₁ = c .

The solution to this problem is simple: it is almost always enough to check that the total denomination of our coins is not less than c: a + 2 · b ≥ c. The exception is when c is odd. Then we still need to check that a ≥ 1.

Problem B. Digital roots

Idea: Gregory Shovkoplyas
Realization: Gregory Shovkoplyas
Analysis: Gregory Shovkoplyas

In this problem, we need to determine by the numbers a and b which of the values ​​of the digital root will occur on this segment the greatest number of times. Note that the digital has only nine values, and they are cyclically repeated. Thus, it is necessary to calculate only the digital roots of a and b , and most often there are numbers between the values ​​of these digital roots. The only thing that needed to be additionally taken into account is the case when the digital root a is larger than the digital root b . It was also necessary not to forget that the answer should be displayed in ascending order.

Problem C. Two snails

Idea: Dmitry Filippov
Realization: Nikolay Vedernikov
Analysis: Nikolay Vedernikov

In this problem, two snails climb a _i a day, and descend b _i at night. It is required to determine how much time the first snail overtook the second. The problem is solved by modeling. We consider the clock consistently. First, let's find out, now it's day or night. Let's see the position of the snails before and after this hour. If before the beginning of the hour one was higher than the other, and after the end of the hour it was also higher, then there was no overtaking. Then, if the first was higher, then add one hour to the answer. If at the beginning of the hour it was higher, and then lower, then one overtook the other. In order to know the time when one will overtake the other, it is necessary to calculate the distances between them and divide by the difference in speeds. After that, add to the answer the time when the first snail was higher than the second at this hour.

Task D. Slot Machines

Idea: Anna Malova
Realization: Vitaly Aksyonov
Analysis: Vitaly Aksyonov

We are given buttons that can turn off a set of light bulbs, and buttons that can turn on a set of light bulbs. Task: using the buttons to transfer light bulbs from the off state to the specified one or to report that this cannot be done.

First, we realize that pressing the same button twice does not make sense, since we can always leave only the last button pressed, and the final state will not change. Next, consider the problem from the end. Each light bulb will have three states: on, off and unknown. When we reverse the button press, we mark all the bulbs that have changed the state, that their state is unknown.

We could press a button if:

• the button turns off the light bulbs, then the state of the modified light bulbs must be either turned off or unknown;
• the button turns on the lights, the states of the changed lights must be either on or unknown.

We look at the last state and press the buttons (each once, if possible). Let no button be pressed, then you need to check whether the lights are either turned off or unknown, which corresponds to the starting state. If true, we can go to the specified state by a sequence of clicks, otherwise it is impossible.

Task E. Internet pipeline

Idea: Vitaly Aksyonov
Realization: Ilya Zban
Analysis: Ilya Zban

In the problem, n points are given, and it is necessary to find some straight line l and distance d such that the number of points located exactly at the distance d from the straight line l would be maximum.

Any line is given by a triple of coefficients a, b and c such that ax + by + c = 0 . Two straight lines ( a ₁ , b ₁ , c ₁ ) and ( a ₂ , b ₂ , c ₂ ) are parallel if the vectors ( a ₁ , b ₁ ) and ( a ₂ , b ₂ ) are collinear.

Let's draw straight lines through all pairs of points and bring them to normal form: GCD (a, b) = 1 , and a> 0 or a = 0 and b> 0 . Such a representation is unique for any straight line. After going through all the lines passing through a pair of points, we get all the angles at which it makes sense to carry out a direct answer (in the case where the answer is more than two, some two points from the answer will lie on the same line). Knowing the angle at which the direct-answer passes, it is easy to specify the optimal d : for fixed a, b , which set the angle of the straight line, you need to choose the two most frequent values ​​of a, b with these values ​​of c , and we get two straight lines parallel to the desired one, d . If there is only one such value c , then if not all points lie on one straight line, you can add one more point to the answer.