Merthyr Tunnel by Pictonart

On May 8, the first qualifying round of the Russian Code Cup 2016 championship took place. We remind you that this year the contest of programmers is being held for the first time in English, so the language barrier is no longer an obstacle for our foreign participants. To pass the first qualifying round, it was necessary to solve five problems. The decision was given no more than two hours. Not only correctness was taken into account, but also the speed of the decision. In total, 3559 people took part in the round, of which those who took the first 200 places move to the next stage of the competition. In the meantime, let's consider the solutions to the proposed tasks:

1. Binary string
2. Train and tunnel
3. Beautiful break
4. Task preparation
5. Similar subway

Task A. Binary String

Condition:
')
Time limit of 2 seconds
256 MB memory limit

Peter wrote on the blackboard a string of length n of zeros and ones. After that, he looked at all the pairs of symbols in a row and found out that the pair 00 occurs a times, the pair 01 occurs b times, the pair 10 occurs c times, and the pair 11 times d ( a + b + c + d = n - 1 ).

Hooligan Grisha erased his line. Having grieved, Peter now wants to restore some line for which the same conditions are fulfilled for the number of pairs of corresponding neighboring symbols. Help him!

Input format:

At the input serves several test examples. The first line contains a positive integer t (1 ≤ t ≤ 10 000) - the number of test cases.

Each test case is described in one line, containing four numbers a , b , c and d (0 ≤ a, b, c, d ≤ 20) - the number of pairs of adjacent symbols equal to 00, 01, 10, 11, respectively.

It is guaranteed that a + b + c + d ≥ 1.

Output Format:

Output t lines. For each test case, output the search string consisting of zeros and ones, or impossible if such a string does not exist.

Examples:

Input data
five
0 0 1 0
1 0 0 1
1 1 1 1
2 1 1 2
1 2 3 4

Output
ten
impossible
00110
0001110
11111001010

Decision:

To begin with, we note that a problem has no solutions if and only if one of the two conditions is fulfilled:

• • Or | b - c | > 1
• • Either b = 0, c = 0, and at the same time a ≠ 0 and d 0

For the remaining cases, we will solve in two stages: First, we collect the minimum line that will satisfy the conditions on lines 01 and 10, and then we add a 1 zero after the first zero encountered a , and d - 1 units after the first zero met. It is obvious that the conditions on 01 and 10 from such actions will not deteriorate.

Problem B. Train and tunnel

Condition:

Time limit of 2 seconds
256 MB memory limit

Peter decided to go on a trip. Now he is traveling in a train. The train consists of n cars, the length of the i- th car is a _i meters. The distance between the cars can be neglected.

Petya noticed that some cars turned on the lights. The train is approaching a railway tunnel with a length of h meters. Petya does not want, at some point in time, only cars with no light in the tunnel. Petya calls the dark point in time, if in all the cars, a certain portion of non-zero length of which is in the tunnel, the light does not light up. To exclude the appearance of such a moment, Peter wants to turn on the light in some cars.

Help Petya turn on the light in the minimum number of cars, so that during the passage of the tunnel, no point in time is not dark.

Input format:

The input contains several test cases. The first line contains one number t (1 ≤ t ≤ 100) –– the number of tests. The following are descriptions of tests.

Each test is defined as follows: the first line contains two natural numbers n , h (1 ≤ n ≤ 10 ⁵ , 1 ≤ h ≤ 10 ⁹ ) - the number of cars in the train and the length of the tunnel in meters. The next line of the test contains n natural numbers a _i (1 ≤ a _i ≤ 10 ⁹ ) - the lengths of the cars in meters. The next line contains n numbers, the i -th of which is 1 if the light is initially turned on in the i- th car, and 0 otherwise. The carriages are listed from head to tail of the train.

The sum of n values ​​for all tests does not exceed 10 ⁶ .

Output Format:

For each test case, output a single number — the smallest number of cars in which the light should be turned on.

Examples:

Input data
2
7 10
5 3 4 5 9 9 9
1 0 0 0 1 0 0
5 2
1 2 3 1 1
1 1 0 1 1

Output
2
one

Decision:

We divide the entire train into segments of cars without light. We will go through each group of such cars, and in the car on which the total length of the cars becomes at least h , we will turn on the light. Obviously, this strategy gives the lowest result. You also need to remember to turn on the light in the first and last cars: when entering the tunnel and leaving it, respectively, these cars form a dark moment of time.

Problem C. A beautiful break

Condition:

Time limit of 2 seconds
256 MB memory limit

Today at school in the lesson of mathematics, Petya was told about the greatest common divisor of many numbers. He liked this topic so much that he began to look for it in all tasks.

Thus, in the computer science lesson, the teacher wrote down an array of integers on the board, and Peter immediately noticed that its elements can be divided into two sets M ₁ and M ₂ so that gcd (M ₁ ) and gcd (M ₂ ) are rather large. Here gcd (M) , where M is a non-empty set of numbers, means the greatest common divisor of all numbers from M.

Petya decided to generalize the problem: using a given array of numbers, he wants to find a partition of its elements into two non-empty sets M ₁ and M ₂ so that min (gcd (M ₁ ) , gcd (M ₂ )) is as large as possible. Help him with this task.

Input format:

The input contains several test cases. The first line contains the number of tests t (1 ≤ t ≤ 1000).
Each of the tests is described as follows: the first line of the test description contains the number n (2 ≤ n ≤ 5 • 10 ⁴ ) - the number of array elements. The next line contains n numbers a _i (1 ≤ a _i ≤ 10 ⁹ ) - element1 of the array.

The sum of the values ​​of n in all tests of the same input data does not exceed 5 • 10 ⁴ .

Output Format:

For each test in a separate line print the answer to it - the maximum possible value min (gcd (M ₁ ) , gcd (M ₂ )) .

Examples:

Input data
3
five
3 2 4 6 9
3
3 5 14
four
6 4 6 6

Output
2
one
four

Decision:

The first element of the array is either M ₁ or M ₂ . Without loss of generality, we assume that it belongs to M ₁ . Then a [1] is divided by gcd (M ₁ ) , that is, gcd (M ₁ ) is the divisor of a [1].

Let's iterate over all divisors a [1] (there are no more than 1344 for numbers up to 10 ⁹ ). Considering the current divider d , we take all the elements of the array, dividing by d , in M ₁ (because this does not make gcd (M ₁ ) less than d , and the fewer the elements in M ₂ , the more gcd (M ₂ ) is) all other elements in M ₂ and update the answer with the value min (gcd (M ₁ ) , gcd (M ₂ )) . Note that we can neglect the fact that M ₂ will be empty, considering in this case gcd for it is equal to infinity, since all the elements in this case are divided by d , then gcd (M ₂ ) will be no less than d .

The asymptotics of the solution is O (sqrt (a [1]) + d (a [1]) • n ), where d (a [1]) ≤ 1344.

Task D. Preparing Tasks

Condition:

Time limit of 2 seconds
256 MB memory limit

Andrei came up with n tasks that need to be prepared for the championship. For each task i, he estimated the time t _i , which is necessary for its development. Andrei wants to invite friends to help him with the preparation.

He still does not know how many friends he will be helped, but he wants to fairly distribute the work between assistants. Therefore, for each task, he wants to determine an integer x _i such that each of his friends spends exactly x _i minutes on its preparation. Andrei believes that task i will turn out to be of high quality if all the friends in the sum spend at least t _i minutes on its preparation.

Sometimes Andrei understands that he incorrectly estimated the time that is needed for the qualitative development of a task, and increases or decreases t _i by 1. You need to help Andrei evaluate how much time it will take to prepare the tasks.

The initial estimates of the time for preparing tasks t _{i are given} . It is required to process m requests. Each request is described as follows:

• 1 i - Andrew decided to increase the value of t _i by one;
• 2 i - Andrew decided to reduce the value of t _i by one;
• 3 k - Andrei wants to know how much time it will take for a friend to prepare tasks if he is helped by his friends.

Input format:

The first line contains two integers n and m (1 ≤ n , m ≤ 10 ⁵ ) - the number of tasks and the number of queries.

The next line contains n integers t _i (1 ≤ t _i ≤ 5 • 10 ⁵ ) - the time that is needed to prepare the i -th task according to Andrew’s initial estimate.

The following m lines are followed by queries. Each of them is described by two numbers, the first of which is its type. If the type is 1 or 2, then the second number i (1 ≤ i ≤ n ) is the number of the task. And if type 3, then the second number k (1 ≤ k ≤ 5 • 10 ⁵ ) is the number of friends who are going to help Andrew.

It is guaranteed that t _{i is} always between 1 and 5 • 10 ⁵ .

Output Format:

For each request of the third type, print a single number - the total time that is necessary for preparing tasks for one person.

Examples:

Input data
5 11
1 2 3 4 5
3 1
3 2
3 3
eleven
3 1
3 2
3 3
2 5
3 1
3 2
3 3

Output
15
9
7
sixteen
9
7
15
eight
7

Decision:

First, we solve the problem if there are no requests for changing times. From the array t _{i, we will} generate a new array cnt _j , in which we will store the number of tasks for which we need to spend j minutes, and also prefetch an array of its prefix sums. Then the amount of time each friend spends, if there are only k , can be calculated as O (MAX / k) , where MAX is the maximum time needed for the task (just sorting through which tasks take 1, 2, ... MAX / k minutes) . As is known, the total running time of such an algorithm for all k from 1 to MAX is O (MAXlog (MAX)) .

Now let's see what happens when the time required for the task changes from t to t + 1. The answers will change only for k being divisors of t . Since the maximum number of divisors for numbers up to 5 • 10 ⁵ is 200, you can simply sort them all over time proportional to their number and update the answer only for them.

Similarly, if time changes from t to t - 1, then the answers change for numbers that are divisors of t - 1.

Problem E. A similar metro

Condition:

Time limit 3 seconds
256 MB memory limit

Vasya often goes to international programming contests that take place in different cities. Arriving in Baitland and looking at the subway map, he realized that he had seen something incredibly similar somewhere. Having thought carefully, he realized that the metro in Byteland is very similar to the metro in Baitovia. In both cities, as it is not surprising, the tunnels of the metro form a tree — you can drive in a tunnel between two stations in both directions, and between any pair of stations there is a single simple path through the tunnels.

In order to prove to Pete’s friend that the metro maps of both cities are really similar, Vasya wants to present him with a coherent set of k stations a _i in Baytland, and the corresponding set of k stations b _i in Baitovia, such that for any i , j between stations a _i and a _j in Byteland is a tunnel if and only if there is a tunnel between stations b _i and b _j in Baitovia. A set of stations is called connected if it is possible to get from any station of this set to any other station of the set, passing only through the stations of this set.

Help Vasya to find the most similar pair of connected sets of stations by the number of stations.

Input format:

The first line contains a single integer n (1 ≤ n ≤ 50) - the number of metro stations in Baytland.

In the following n - 1 lines, pairs of numbers u _i , v _i (1 ≤ u _i , v _i ≤ n ) are given - the numbers of the stations in Byteland, between which there is a tunnel. It is guaranteed that there is exactly one simple path between any pair of stations.

The next line contains one integer m (1 ≤ m ≤ 50) - the number of metro stations in Baitovia.

The following m - 1 lines contain pairs of numbers u _i , v _i (1 ≤ u _i , v _i ≤ m ) - the numbers of stations in Baitovia, between which there is a tunnel. It is guaranteed that there is exactly one simple path between any pair of stations.

Output Format:

Output one integer k - the maximum possible size of a pair of similar sets of stations.

Examples:

Input data
3
12
2 3
3
13
3 2

Output
3

Input data
five
4 1
2 4
4 3
3 5
five
12
2 3
3 4
4 5

Output
four

Decision:

The task required to find the largest pair of connected subtrees of these trees isomorphic to each other. We will solve this problem by dynamic programming.

Calculate for a pair of oriented edges ( u ₁ , v ₁ ) in the first tree and ( u ₂ , v ₂ ) in the second tree, the value of dp [ u ₁ ] [ v ₁ ] [ u ₂ ] [ v ₂ ] is equal to the size of the largest isomorphic pair subtrees if the vertex u ₁ goes to the vertex u ₂ , and the vertices v ₁ and v ₂ do not necessarily enter the selected subtrees. In addition, we allow v _{i to} be equal to some fictitious vertex -1, this will mean that the remote subtree v _{i is} not, and all vertices can be used for a common subtree. If we calculate this value, the answer will be the maximum over all pairs of vertices u ₁ , u ₂ of dp [ u ₁ ] [- 1] [ u ₂ ] [- 1].

To count dp [ u ₁ ] [ v ₁ ] [ u ₂ ] [ v ₂ ], you need to somehow compare the subtrees u ₁ and u _{2 to} each other. Note that if e ₁ is the son of a vertex u ₁ that is different from v ₁ , then the subtree e ₁ contains less vertices than the subtree u ₁ , when the tree is hung beyond v ₁ . For the sons of e _1, by the induction hypothesis we have already calculated the vertices u ₁ and e _{2 of the} vertices dp [ e ₁ ] [ u ₁ ] [ e ₂ ] [ u ₂ ], so we know how many vertices can be added to the desired subtree, if vertex e ₁ in it will correspond to e ₂ . If the vertex u ₁ - k sons, u u ₂ - m sons, then we get a matrix a _{i, j of} size k • m , in which we need to select several cells with the maximum sum, provided that in each column and in each row no more than one cell selected. This is a standard assignment problem, which is solved by the Hungarian algorithm.

The final complexity of the solution is O (n ⁵ ) , n ² ways to select a pair of edges in two trees and O (n ³ ) is the running time of the Hungarian algorithm. For optimization, it is possible not to solve the assignment problem for identical (isomorphic) pairs of trees several times, but to remember the answer.

* * *

If you have not applied for participation in the championship, you still have time! Register on the Russian Code Cup website until May 29 and take part in the second qualifying round.

The Russian Code Cup Championship is one of the Mail.Ru Group initiatives aimed at the development of the Russian IT industry and the IT.Mail.Ru. The IT.Mail.Ru platform is designed for those who are keen on IT and are seeking to develop professionally in this area. The project combines the championships of the Russian Ai Cup, the Russian Code Cup and the Russian Developers Cup, educational projects Technopark in MSTU. Bauman, Technosphere at Moscow State University. Mv Lomonosov and Tehnotrek MIPT. In addition, using IT.Mail.Ru, you can use tests to test your knowledge of popular programming languages, learn important news from the IT world, visit or watch broadcasts from specialized events and lectures on IT topics.