On Saturday, April 25, the second qualifying round of the Russian Code Cup 2015 was held. 3516 programmers solved problems within two hours, of which at least one correct solution was sent by 458 participants.

The first in 4 minutes and 9 seconds to solve the problem A (Turnstiles in the subway) Alexander Masharabov (map). Problem B (Game) in 8:48 was decided by Dubnilny Denis (Stigius), task C (Sticks and hinges) in 18:08 was decided by Nigmatullin Niyaz (niyaz.nigmatullin). Task D (Fibonacci numbers) for 1 hour 5 minutes and 21 seconds was solved by Lunev Anton (Anton_Lunyov). And the last task E (Teleports) in 1 hour 44 minutes and 55 seconds was decided by Pavel Kunyavsky (PavelKunyavskiy), who took the 1st place in the rating according to the results of the round. The last successful attempt was made by Albert Sahakyan 4 seconds before the end of the competition. All five tasks passed only Pavel Kujawski.
')
In total, the participants sent 4287 solutions for review, 3145 for C ++, 613 for Java. Note that out of 2166 solutions submitted to GNU C ++, 1218 solutions use C ++ 11 standards, and the rest still do not use new features language. This time there are only 913 correct decisions, of which in C ++ - 726, in Java - 141.

Following the results of the round, 200 participants were qualified, who will compete for the title of finalist in the qualifying round on June 14. Those who were not lucky on Saturday and who for one reason or another could not take part in the round, will be able to try their hand at the third qualifying round on May 31 at 13:00. In the qualifying round, scheduled for 1:00 pm on June 14, 200 best participants from each qualifying round will be selected.

Anyone wishing to participate in the championship may still have time to register on the site before the start of the third qualifying round.

Task A. Turnstiles in the subway

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

According to the condition of the problem, you need to find the point in time when the numbers displayed on the turnstile of the two boys will differ by k times. First we analyze the case k = 1, in this case the answer is YES, if 99 shows on both turnstiles or if a = b . Otherwise, it is easy to see that the correct moment of time will come no earlier than any boy’s number of trips will be less than 99. We proceed straight to the first such moment. We only have no more than 99 variants of suitable days. We will iterate and check each of them for the fact that it satisfies the condition of the problem.

Task B. Game

Idea: Nikolay Vedernikov
Realization: Nikolay Vedernikov
Analysis: Nikolay Vedernikov

According to the condition of the problem, you need to find the expectation of the length of the path from the first level to the last. To do this, we use the dynamic programming method. Dp [i] [j] will store the expected length of the path if we start on the i- th floor in the j- th room and go to the last level. Then the answer to our task will be stored in dp [1] [1] .

We will solve the problem from the last level to the first. It is clear that dp [n + 1] [x] = 0, where x is from 1 to n + 1. Now, knowing the answer for the ( k + 1) -th level, we calculate the dynamics value for k .

• If a [k] [j] [0] < a [k] [j] [1] , then dp [k] [j] = dp [k + 1] [j] + a [k] [j] [ 0] . Where a [k] [j] [0] is the length of the corridor from the k- th level of the j -th room to the j- th room at the ( k + 1) -th level. A a [k] [j] [1] is the length of the corridor from the k- th level of the j-th room to the ( j + 1) -th room at the ( k + 1) -th level.
• If a [k] [j] [0] > a [k] [j] [1] , then dp [k] [j] = dp [k + 1] [j + 1] + a [k] [j ][one].
• If a [k] [j] [0] = a [k] [j] [1] , then dp [k] [j] = ( dp [k + 1] [j] + dp [k + 1] [ j + 1] ) / 2 + a [k] [j] [0] . Since we could go both along the first corridor and the second with equal probability.

After the calculation, the answer to the problem will be stored in dp [1] [1] .

Problem S. Sticks and Hinges

Idea: George Korneev
Realization: Gregory Shovkoplyas
Analysis: Gregory Shovkoplyas

In this problem, we are given a sequence of sticks connected by hinges, which can take the form of any broken line, with edges equal to the lengths of the corresponding sticks. In the condition of this figure was called a chain. It is necessary to find the minimum radius of such a circle that a chain can be placed in it, and the center of the circle should coincide with the beginning of the first rod.

Consider a solution using a binary search by answer. Obviously, if the chain is placed in a circle, then it will fit in a circle of a larger radius. Now we need to learn to check that the circle can hold a chain. The idea is simple: we type the maximum number of sticks, such that their total length is less than or equal to the radius of the circle. If there are no more sticks, then the problem is solved. Otherwise, we can see if we can put the following: if its length minus the sum of the previous ones is greater than the radius (it was turned 180 degrees in the hinge and it went beyond the circumference), then it is impossible to fit the chain into this circle, otherwise there will be a point on the circle which you can put the next hinge, which means that this wand will fit. Now we check that the length of the remaining sticks is less than the diameter of the circle, which is equivalent to the fact that we can expand all the remaining hinges into a circle, and the chain will fit into a circle.

Problem D. Fibonacci numbers

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

By the condition of the problem, you need to find the sum of the kth powers of the first n Fibonacci numbers modulo 10 ⁹ +23. The very first step was to decompose the module into factors: 10 ⁹ +23 = 3 · 11 ² · 61 · 45161. Let's calculate the required amount for each of these modules and restore the answer to the problem of the Chinese theorem on residuals.

For each module separately, the problem is solved as follows. Find the period of Fibonacci numbers. For our modules, they turn out to be small, and the pre-period is always 0. We calculate the sum of the k -th powers of the Fibonacci numbers in a given period and even a small piece. Then the answer to the problem for a fixed n will be equal to the sum of several periods and the sum on a small piece.

Having received the answer for each of the smaller tasks, we restore the answer for the initial task. Unfortunately, the task did not end at this stage. You need to come up with any optimization in order for the program to go through time. It was possible to apply the following: get rid of double taking modulo during rapid exponentiation, preliminarily presuming numbers in powers of two, or raise not to degree k , but use the Euler theorem and raise to a power modulo φ .

Problem E. Teleports

Idea: Ilya Zban
Realization: Ilya Zban
Analysis: Ilya Zban

The problem is given n points teleports, from which you can reflect, and you want to check whether you can get from the starting point to the final one. Note that two reflections in a row with respect to points i, j will add to the current point coordinate the vector f (i, j) = (2 ( x _j - x _i ), 2 ( y _j - y _i )). If we know that there is an even number of reflections in the answer, then the problem can be reduced to the following: is it possible to imagine a vector ( x _f - x _s , y _f - y _s ) as a sum of vectors f (i, j) . The case with an odd number of vectors in the answer is reduced to a problem with an even number, if the first action reflects the starting point relative to any teleport (it may seem that you need to go through all n variants of the first move, but in fact it is not necessary) and try to solve the problem with an even number vectors in response.

Note that it is not necessary to use all n ² vectors f (i, j): f (i, j) = f (1, j) - f (1, i) . So, we have only n -1 vector in the review. It is argued that the integer linear span of integer vectors can be represented as an integer linear span of just two certain vectors, i.e. this shell is some kind of grid on the plane.

We will add to the set of considered vectors one at a time and maintain two vectors defining a linear combination of all already added ones. One vector will have the form v ₁ = ( x ₁ , 0), where x ₁ is the minimum possible positive, and the second - v ₂ = ( x ₂ , y ₂ ), where y ₂ is the minimum possible positive, and 0 ≤ x ₂ < x ₁ .

As long as all the added vectors are collinear using the Euclidean algorithm, it is easy to find which single vector can represent all the others with its linear combination. As soon as at least one pair of non-collinear vectors appears in the considered set, the vectors are recalculated differently. Let vector v ₃ be added.

To find a new vector v ₁ , we need to look at the GCD of two vectors: the old v ₁ and the vector with the minimum x of the form ( x , 0), represented by a linear combination of the vectors v ₂ and v ₃ . To do this, you need to find the minimum solution to the equation k ₂ · y ₂ + k ₃ · y ₃ = 0. To find a new vector v ₂ , you need to consider a vector of the form k ₂ · v ₂ + k ₃ · v ₃ . You need to find any solution to the equation k ₂ · y ₂ + k ₃ · y ₃ = GCD ( y ₂ , y ₃ ) and add new v ₁ several times to ensure that the x-coordinate is minimal. Knowing the two vectors defining the grid, it is easy to verify that we can represent this vector in the form of their integer linear combination: you just need to check that its coefficients of expansion along these two vectors are integers.