Russian Code Cup 2013 - analysis of qualifying round tasks

Last Sunday, the qualifying round of the Russian Code Cup took place. This is the last online round of the competition: the final game of the finalists will be held in Moscow. In order to participate in the final, it was necessary to put more effort than in the previous stages. Participants were offered six tasks (in the qualifying rounds there was one less), three hours were allocated for their solution (two in the qualifying rounds).

The struggle for the finals was not easy, but fair: during the round, not a single copywriter was revealed.
Under the cut - statistics on the winners and a detailed analysis of the tasks of the qualifying round:

• Task A: Two Towers
• Task B: Deposit
• Task C: Kepler
• Problem D: Test
• Task E: Lasers
• Task F: Wheel

')
During the round, 439 people logged in, of which at least one solution was sent by 371 participants. A total of 3334 solutions were sent.

Participants who first sent solutions to the relevant tasks, and the time after the start of the round (min: s):

• Problem A: RAVEman (9:12)
• Problem B: ant.ermilov (16:58)
• Task C: Zhukov_Dmitry (5:52)
• Problem D: e-maxx (33:05)
• Task E: winger (37:50)
• Task F: tourist (82:51)

The territorial distribution of participants in this round was as follows:

Russia => 183
Ukraine => 53
Belarus => 23
United States => 18
Kazakhstan => 5
Germany => 4
Switzerland => 3
Latvia => 2
Armenia => 2
Bulgaria => 1
Iceland => 1
Hungary => 1
Uzbekistan => 1
Georgia => 1
Spain => 1
Lithuania => 1
UK => 1
Austria => 1
Cyprus => 1
Poland => 1

Only by the end of the third hour the picture of the list of winners began to take shape. 50 people reached the final. The first 10 of them:

1. Vladislav Isenbaev
2. Gennady Korotkevich
3. Dmitry Dzhulgakov
4. Peter Mitrichev
5. Vladislav Epifanov
6. Artem Rakhov
7. Mikhail Kever
8. Dmitry Gozman
9. Dmitry Zhukov
10. Evgeny Kapun

And, finally, we proceed directly to the analysis of tasks.

Task A. Two towers
Idea: Fedor Tsarev
Realization: Pavel Krotkov, Andrei Stankevich
Analysis: Pavel Krotkov

The task

Time limit: 2 seconds
Memory limit: 256 megabytes

Mail.World recently moved to a new office that looks like two towers, skyscrapers of 10 ⁹ floors each. On some floors of the tower are connected by transitions, which can go from one to another. There are n transitions in total, they connect towers on floors a ₁ , a ₂ , ..., a _n

Artem works in the tower b ₁ on the L _1st floor. Today, he needs to talk with his colleague Dmitry, who works in tower b ₂ on the L ₂ nd floor. Oddly enough, it turned out that choosing the fastest way to get from the workplace of Artem to the workplace of Dmitry is not so easy.

In each of the towers installed one elevator. The elevator in tower 1 travels one floor in time u ₁ seconds, and the elevator in tower 2 in u ₂ seconds. Artem spends t seconds on the way between the towers on the transition.

Based on this information, help Artem find out in what minimum time he can get from his workplace to Dmitry's workplace. The time of movement inside the floor of one tower and the waiting time of the elevator should be neglected.

In the first example, Artem needs to just take the elevator of the first tower.

In the second example, the elevator in the second tower runs significantly faster, and it is more beneficial for Artem to cross the transition to the second tower, take the elevator to the 10th floor, return to the first tower and drive another floor on the elevator in the first tower.

Input Format

The first line contains a positive integer t - the number of test cases in the input data. The following are descriptions of test examples.

The first line contains n - the number of transitions between towers (1 ≤ n ≤ 10 ⁵ ). The second line contains n distinct integers a ₁ , a ₂ , ..., a _n (1 ≤ a ₁ <a ₂ <... <a _n ≤ 10 ⁹ ). The next line contains three positive integers: u ₁ , u ₂ and t (each of them lies in the range from 1 to 10 ⁹ ). Finally, the next two lines contain two numbers: b ₁ , L ₁ and b ₂ , L ₂ , respectively (each of b ₁ and b ₂ is 1 or 2, 1 ≤ L ₁ , L ₂ ≤ 10 ⁹ ).
The total number of transitions in all test examples in the input data does not exceed 10 ⁶ .

Output format

For each test case, output one number - the minimum time in seconds in which Artyom can get from his workplace to the workplace of Dmitry.

Examples

Input data	Output
2 one five 3 3 2 eleven 1 10 2 1 10 5 3 2 eleven 1 11	27 36

Task analysis

This task is a simple special case of the problem of finding the shortest path in a graph. One way to solve it is to simply implement the Dijkstra algorithm on the graph described in the condition. However, due to the large possible number of vertices, not any implementation of this algorithm will be within the time limit of the program. Therefore, consider a solution that works faster.

Let's build a graph of the floors we are interested in. The following floors will be considered interesting:

• The floor on which Artem works, in the tower in which Artem works
• The floor on which Dmitry works, in the tower in which Dmitry works
• Floors that are the ends of the nearest transitions to Artem (in total we get 2 vertices from the transition, which is higher, and 2 vertices from the transition, which is lower)
• Add 4 vertices similar to the previous paragraph, but only for Dmitry

There are two types of edges in our graph:

• The edges connecting the vertices, between which there is a transition. The weights of such edges are t
• The edges connecting tops from one tower. The weights of such edges are equal to the distance between the respective floors, multiplied by the elevator speed in the corresponding tower.

Note that in our graph there are 10 vertices. You can search for the shortest paths in this graph by any method; the easiest way was to implement the Floyd algorithm.

Task B. Deposit
Idea: Boris Minaev
Realization: Vitaliy Demyanyuk
Analysis: Vitaly Demyanyuk

The task

Time limit: 2 seconds
Memory limit: 256 megabytes

For many years of work experience, Vasily Ivanovich earned k rubles. Now Vasily Ivanovich has retired and wants to put this money on deposit for the next m years. There are n banks in his hometown. If Vasily Ivanovich has money in the bank with number i for the jth year, at the end of the year their number in this account will increase by p _{i, j} percent.

At the beginning of each year, Vasily Ivanovich can, if he wants, redistribute the money lying on the accounts in banks. The process of redistribution of money occurs in four stages. First, he chooses a number of banks involved in the redistribution. Then Vasily Ivanovich removes all the money in these banks. After that, he pays a commission to each of the selected banks. In the end, in each of the selected banks, he puts into the account as much money as he wants, and in total, Vasily Ivanovich puts all the money he has withdrawn into his accounts, less the commission paid. At the same time, in the set of selected banks there may be banks, where Vasily Ivanovich did not have money, or in which he does not plan to put money. At the bank with the number i, the commission is equal to a _i rubles. If Vasily Ivanovich has not enough money to pay the commission, then he gives all the withdrawn money to the banks that participated in the redistribution of money.

At the beginning of the first year, Vasily Ivanovich can put any number of rubles on deposits in any banks for free, and in total he will put all his money on deposits.

Find the maximum total number of rubles on all accounts of Vasily Ivanovich at the end of the m-th year.

In the example, Vasily Ivanovich first puts the money in the second bank. After the first year he has 115 rubles, he chooses both banks for the redistribution. After paying a commission of 2 rubles, he puts all the money in the first bank. At the end of the year, he has 113 × 1.15 = 129.95 rubles in a bank account.

Input Format

The first line contains a positive integer t - the number of tests. (1 ≤ t ≤ 50)

The description of each test begins with a line containing three integers n, m, and k — the number of banks, years, and rubles earned, respectively. (1 ≤ n ≤ 10000, 1 ≤ m ≤ 20, 1 ≤ k ≤ 10 ⁹ ) The next line contains n integers, where the i-th number is a _i - the commission of the i-th bank (1 ≤ a _i ≤ 10 ⁹ ). Each of the next n lines contains m integers each. In the i-th line, the j-th number is p _{i, j} is the percentage of additional money received by Vasily Ivanovich in the j-th year on an account in the i-th bank (0 ≤ p _{i, j} ≤ 100).

The total number of banks in all tests does not exceed 50,000.

Output format

For each test in a separate line, print the maximum total amount of money on all accounts of Vasily Ivanovich at the end of the m-th year. Your answer will be counted if its relative error does not exceed 10 ⁻⁶ .

Examples

Input data	Output
one 2 2 100 eleven 10 15 15 10	129.95

Task analysis

Let us show that it is always beneficial for Vasily Ivanovich to store all the money in one bank. Consider the optimal answer. Assume that there is a year in which Vasily Ivanovich's money was in several banks. Among all these years, choose a year with a minimum number. For each bank, let us consider what percentage in m years we received from the money lying during the year under consideration in this bank without considering all commissions. Choose a bank with a maximum percentage. Note that if you put all the money in it, the answer will not worsen, because in each year the set of banks that participated in the redistribution of funds will be a subset of the set of banks in the optimal answer.

Taking into account the fact that has just been proved, the problem is solved by the dynamic programming method. Let dp _{i, j} be equal to the maximum amount of rubles in Vasily Ivanovich’s accounts in i years, if, during the i-year, all his money was in the j-th bank. We look through all the banks where the money could be stored in the previous year, then dp _{i, j} = (max (dp _{i-1, k} –a _k ) - a _j ) • p _{j, i} for all k from 1 to n.

Consider separately the case when j = k, then dp _{i, j} = max (dp _{i, j} , dp _{i, j-1} • p _{j, i} ). The answer is equal to the maximum dp _{m, k} over all k. As a result, at first glance, the solution works for O (n2m). However, note that dp _{i-1, k} - a _k does not depend on j. Therefore, if for all i to support max (dp _{i-1, k} - a _k ), then we get the solution in O (nm).

Problem C. Kepler
Idea: Vitaly Aksyonov
Realization: Andrey Komarov
Analysis: Andrey Komarov

The task

Time limit: 2 seconds
Memory limit: 256 megabytes

After the failure of the second gyroscope, the Kepler astronomical telescope became unsuitable for further operation. NASA decided to compensate for this loss and launch another telescope into space. In order to provide the telescope with electricity, it was decided to use solar panels. The blank for the solar battery is a rectangular panel of size n × m, consisting of cells 1 × 1.

Unfortunately, it is impossible to deliver a battery into orbit in an unfolded state. To facilitate transport, the panel is made of thin material and can be bent along any border of cells. Scientists have decided that the battery will fly into space folded to a size of 1 × 1.

To do this, they come with a blank for the battery as follows: if one of the sides of the current blank has an even length, then the blank can be folded along it; the panel is obtained twice as small (the thickness of the panel can be neglected). If one of the sides has an odd length (the panel is (2n + 1) × m), then they can cut a piece of 1 × m in size with an ultra-precise laser in time m, and then fold it in half along the side 2n long. The cut piece of the panel is thrown away. As a result, scientists get a 1 × 1 panel, which will fly into orbit and unfold there.

The laser works much longer than all foldings occur. Help them determine the shortest laser time that they can achieve in order to roll up the original billet in this way into a 1 × 1 square.

Please note that the size of the battery, which will result from the deployment of the panel, does not matter, it is necessary to minimize the time of the laser.

Input Format

The first line contains an integer t (1 ≤ t ≤ 1000) - the number of test queries. The following t lines contain the queries themselves. Each query consists of two integers n and m (1 ≤ n, m ≤ 10 ⁹ ) - the initial size of the blank for the solar panel.

Output format

For each request, print out one number — the shortest laser time that scientists can achieve.

Examples

Input data	Output
3 eleven 4 4 3 2	0 0 one

Task analysis

Let us examine the size of the panel with all possible foldings. Fix one of the sides and see how its length will change over time. Consider the example of the side corresponding to the first dimension. Let the panel initially have a size of n × m. The side of interest is of length n. Further two cases are possible:

• We fold along the side of length n. In this case, the new length is ⌊n / 2⌋
• We fold along the side of length m. In this case, the length will not change and will remain equal to n

Therefore, a side can only have length n, n / 2⌋, ⌊⌊n / 2⌋ / 2⌋, ..., 1. There are only N = ⌊log ₂ n⌋ + 1. Having carried out similar reasoning for the second side, we obtain that its length can take M = ⌊log ₂ m⌋ + 1 values.

To solve the problem, we use the idea of ​​dynamic programming. Denote by a _i , i∈ [1..N] the lengths that the first side can have, ordered in descending order. Similarly for b _i .

We calculate the following value: dp [i, j] = "the shortest time for which you can get from the panel n × m panel a _i × b _j ". Then, since a and b are ordered descending, a _N = 1, b _M = 1, and therefore, the answer to the problem is dp [N, M]. dp [i, j] can be calculated by the rules:

1. dp [i, j] = ∞
2. dp [i, j] = min (dp [i, j], dp [i-1, j] + ((ai-1 mod 2) • bj) if i> 1
3. dp [i, j] = min (dp [i, j], dp [i, j-1] + ((bj-1 mod 2) • ai) if j> 1
4. dp [1, 1] = 0

Problem D. Test
Idea: Artem Vasilyev
Realization: Artem Vasilyev
Analysis: Artem Vasilyev

The task

Time limit: 2 seconds
Memory limit: 256 megabytes

Artem passes an educational test in the electronic system. The test question contains n statements, some of which are true and must be checked. By checking some of the checkboxes, you can check the answer for correctness. The answer to the question is considered correct if all true statements are flagged, and all false statements are not.

Artem is too lazy to think, so he decided to simply go through all the options for placing flags. For this, he compiles a list of all 2 ⁿ variants of their arrangement. In the list, each option flag placement must be present exactly once.

Intuitively, it seems to him that there are a lot of true statements, so he wants to sort out the options of arrangement in order of decreasing the number of checkboxes. In addition, Artem is very lazy and wants that for two consecutive options the number of positions in which they differ does not exceed two. Help Artem.

Input Format

The first line contains an integer n (1 ≤ n ≤ 16).

Output format

Output 2 ⁿ lines. In the i-th line print n characters 0 or 1 - the state of each of the flags for the i-th answer, 1 for the checkbox and 0 for the unspecified one. The number of units in the variants should not increase. The number of positions in which two adjacent lines are distinguished should not exceed two.

Examples

Input data	Output
2	eleven ten 01 00

Task analysis

In this task, it was necessary to list all the rows from 0 and 1 with length n so that two properties were fulfilled: first, the number of ones does not decrease, and second, the two adjacent lines differ in no more than two positions.

We write the solve (n, k) procedure, which returns a list of all bit strings of length n satisfying our property. Each line contains exactly k units. We describe the recursive algorithm to solve (n, k):

1. If k is 0 or n, then we return a list from a single line 0 ⁿ or 1 ⁿ
2. Otherwise, we call recursively solve (n - 1, k) and solve (n - 1, k - 1)
3. To all bit lines from the first list we assign to the end 0, to all elements from the second list we assign to the end 1
4. We return the concatenation of the first list and the expanded second

Now the solution is to output all bit strings from the solve (n, k) list for all k from n to 0. We prove the correctness of this solution. Consider the properties of the list, which returns the solve procedure.

1. The first element of the solve (n, k) list is 1 ^k 0 ^{n - k}
2. If k> 0, then the last element of the solve (n, k) list is 1 ^{k - 1} 0 ^{n - k} 1
3. If k = 0, then the last element of the solve (n, k) list is 0 ⁿ

It is easy to prove all these properties by induction. As a result, we find that the solve (n, k) procedure really works correctly. It remains to verify that the last element of solve (n, k + 1) and the first element of solve (n, k) differ in no more than two positions. The last element of solve (n, k + 1): 1 ^k 0 ^{n - k - 1} 1, the first element of solve (n, k): 1 ^k 0 ^{n - k} . It is easy to see that for these two lines the property also holds. Thus, we obtained an algorithm that lists all bit strings of length n and satisfies the necessary properties.

Task E. Lasers
Idea: Anna Malova
Realization: Artem Vasilyev
Analysis: Artem Vasilyev

The task

Time limit: 2 seconds
Memory limit: 256 megabytes

Scientists from the Laboratory of Lasers are testing a new kind of laser. To do this, they use a special laboratory table, on which there are n attachment points.

A laser is fixed at one of these points, and special programmable refractive devices are fixed at the remaining n - 1 points. Each device can be configured as follows: you can select certain directions and program the refractor so that it turns the beam hitting it from the selected direction at a certain angle. This angle can be different for different directions even on one refractor. At the same time, for each refractor and each direction selected on it, the angle in degrees cannot in absolute value exceed the value of the voltage applied to this refractor a. By virtue of the design of the laboratory installation, the same voltage is applied to all the refractors.

To test a laser, scientists want to choose a certain direction and shoot a beam in it so that it travels a non-zero distance and returns to the starting point. To do this, you need to configure the refractors. Before you do this, you need to select the voltage applied to the refractors. After that, you can choose for each direction refractor and for each direction the angle to which the turn will be performed.

Scientists want to know for what minimum voltage a can carry out a planned experiment.

Input Format

The first line contains an integer n (2 ≤ n ≤ 150) - the number of attachment points on the laboratory table. The next n lines contain two integers xi, yi - the coordinates of the i-th point. (−20000 ≤ x _i , y _i ≤ 20000 for all i from 1 to n, all points are different). The first point corresponds to the laser, all the rest - to the refractors.

Output format

Print one real number - the minimum voltage that you need to apply to the refractors. The absolute or relative error of the answer should not exceed 10 ^-8 .

Examples

Input data	Output
four 0 0 0 1 eleven ten	90.0

Task analysis

The main idea of ​​the solution is a binary search by answer. Fix the maximum angle of deviation α and check the existence of a solution with such an answer. To do this, we reduce the problem to finding a path in the graph.

Denote the points given in the condition as P ₁ , P ₂ , ..., P _n . Construct a graph of n (n - 1) vertices, where each vertex is an ordered pair of different points. Draw edges from a pair (i, j) into a pair (j, k) if the angle between the vectors P _i P _j and P _j P _k does not exceed α. In the constructed graph no more than n ³ edges. Now, if in such a graph there is a path from a vertex of the form (1, i) to a vertex of the form (j, 1), then with such α, the experiment can be carried out. You can check for the existence of a path using any path finding algorithm in the graph.

Thus, one iteration of the binary search works in O (n ³ ), which means that the whole algorithm can be implemented in O (n ³ log (1 / ε)) or, if we note that the search space is actually discrete (we are only interested no more than n ³ angles), then this algorithm can be implemented in O (n ³ log (n ³ )).

Problem F. Wheel
Idea: Boris Minaev
Realization: Boris Minaev
Analysis: Boris Minayev.

The task

Time limit: 2 seconds
Memory limit: 256 megabytes

The country in question is a rather interesting system of roads. In total, in this country n + 1 city is the capital and n ordinary cities. All ordinary cities are located on a circle whose center is in the capital. The distance between all neighboring ordinary cities is the same. Each city is connected by roads with its two neighbors, as well as with the capital. If we looked at this country from above, we would see the correct n-gon whose vertices are connected to the center.

In this country there are two equally strong opposition parties that want to seize power in the country. And no one wants to do it peacefully! In each city, just in case there is a tank platoon. Exactly at the beginning of the next day the following will occur. In each city (including the capital) with equal probability one of the opposition parties will seize power. At the disposal of this party will be a tank platoon located in this city. Further, each party plans to gather in one place the army as large as possible. A tank platoon can drive along the road only if both cities that are connected by the road are captured by the same party.

You are the organizer of the underground movement, which also wants to seize power. You need to know the mathematical expectation of the greatest number of tank platoons that can be in the same city. Don't let your organization down!

For example, let there be three ordinary cities. Then all four cities (three ordinary and the capital) are pairwise connected by roads. Then with probability 1/8 all cities will be captured by the same party. In this case, the maximum size of the army is 4. With a probability of 3/8, two cities will be captured by one party and two by the other. In this case, the maximum size of the army is 2. Finally, with a probability of 1/2 in one city, one party will seize power, and the other in three others. In this case, the maximum size of the army will be 3. The mathematical expectation of the answer in this case is 4 × 1/8 + 2 × 3/8 + 3 × 1/2 = 2.75.

Input Format

The first line contains a positive integer t - the number of test cases. The next t lines contain one integer n (3 ≤ n ≤ 500) - the number of ordinary cities in the country. It is guaranteed that the total number of ordinary cities in all test examples does not exceed 1000.

Output format

For each test case, print one number - the expected value of the largest number of platoons that may be in the same city. The answer is considered correct if it differs from the correct one by no more than ^10-9 .

Examples

Input data	Output
2 3 four	2.75 3.4375

Task analysis

We formalize the condition of the problem. Without loss of generality, we will assume that the first opposition party seized the capital. To all other cities we will compare one number. It will be 0 if one lot has captured the capital and the city, and 1 otherwise. Then all the information about the captured cities can be represented as a bit mask of length n. All possible bitmasks are equally likely. For a specific bit mask, the answer is obviously the maximum of (the number of zeros + 1) and (the maximum number of units that go in a row in the mask). It should be borne in mind that the mask is looped: the next bit after the last is the first.

In order to obtain a polynomial solution, we will use dynamic programming. Its parameters will be:

1. the number of digits in the mask
2. number of zeros in the mask
3. maximum number of units in a row
4. current number of units in a row

However, to take into account the obsession of the mask, you must also store the number of units that are at the very beginning of the mask. This solution works for O (n ⁵ ).

In order to get rid of the last parameter, we use the following consideration. The mask, which consists of one units, will be processed separately. Consider all the remaining masks. In each of them there is at least one zero. Shift the mask bits along the cycle so that the first zero comes first. Now cut the first bit. Now some masks are repeated several times. It is easy to see that the mask is repeated (the number of units in which it ends + 1) times. So, we can iterate over all masks of length n - 1, add zero to the left of the mask, and the probability of its appearance multiply by (the number of units to which it ends + 1). Note that the number by which we must multiply the probability, we already store in dynamic programming. Having got rid of one parameter, we get the solution for O (n ⁴ ).

Consider what happens to the answer with an increase in the number of cities. With a very high probability, the maximum connected component is the component to which the capital belongs. And, therefore, the asymptotic answer tends to (n + 2) / 2. It is easy to show that already at n = 150, the deviation from the asymptotic answer is about 10 ^-12 . You can also prove that as n increases, the deviation from the asymptotic response will only decrease.

Thus, we get the following solution. Using dynamic programming for O (n ⁴ ), we find the answers for the first 150 values ​​of n. For large n, we use the formula (n + 2) / 2.

Analysis of all tasks of the Olympiad is also available on the site of the Russian Code Cup . The next stage is the final; we will surely tell about it on Habré too.