div2 A. In this problem you should find length of polyline, multiply it by k / 50 and output that you will recieve. Length of polyline is sum of lengths of its segments. You can calculate length of every segment using Pythagorean theorem: .

div2 B. Idea of this problem was offered by RAD. It was the last problem in the problemset and I had no any easy idea:) I thank him for it.

Here you should calculate an array cnt[100]. i-th element of it stores number of sticks whose lengths equal i. Now you should calculate number of pairs of sticks of equal lengths. This number is , where [x] is floor of x. For every frame you need 2 if such pairs and you can choose it in any order. Therefore the answer will be z = [k / 2].

div2 С. div1 A. At the first you should consider cases when t₀ = t₁, t₀ = t₂ and t₁ = t₂. Answers will be (x₁, 0), (0, x₂) and (x₁, x₂). The last 2 of them didn't present in the pretests.

Next, for all 1 ≤ y₁ ≤ x₁ you should find minimal y₂, for that t(y₁, y₂) ≥ t₀. You can do it using one of three ways: binary search, two pointers or just calculation by formula [y₁(t₀ - t₁) / (t₂ - t₀)], where [x] is rounding up of x. You should iterate over all cases and choose one optimal of them.

The last tricky case consists in the fact that for all 1 ≤ y₁ ≤ x₁ и 1 ≤ y₂ ≤ x₂ t(y₁, y₂) < t₀. For example, you can see following test

100 110 2 2 109 (it is the 6th pretest).

In this case you should output (0, x₂).

All calculations should be done in 64-bit integers (8th pretest checks overflow of 32-bit integers) or very carefully in the real numbers.

div2 D. div1 B. 

Let us calculate a prefix-function for all prefices of string. Prefix-function p[i] is maximal length of prefix that also is suffix of substring [1...i]. More about prefix function you can see in a description of Knuth-Morris-Pratt algorithm (KMP).

The first of possible answers is prefix of length p[n]. If p[n] = 0, there is no solution. For checking the first possible answer you should iterate over p[i]. If at least one of them equal to p[n] (but not n-th, of course) - you found the answer. The second possible answer is prefix of length p[p[n]]. If p[p[n]] = 0, you also have no solution. Otherwise you can be sure that the answer already found. This substring is a prefix and a suffix of our string. Also it is suffix of prefix with length p[n] that places inside of all string. This solution works in O(n).

Also this problem can be solved using hashing. You can find hash of every substring in O(1) and compare substrings by comparing thier hashes. Well, let's check for every prefix that it is a suffix of our string and store thier lengths into some array in the increasing order. Then, using binary search over the array, you can find maximal length of prefix that lie inside of string. Check of every prefix you can do in O(n). So, you have some solution.

In point of fact, the array of prefix lengths in the previous solution is list { p[n], p[p[n]], ... }, that written if reversed order. From the first solution you know that the answer is prefix of length either p[n], or p[p[n]] (if it exists, of course). Therefore some naive solution without binary search can fits in the limits if you will stupidly check all prefices in the order of decrease thier lengths:) This solution works in O(n).

Also this problem can be solved using z-function.

div2 E. div1 C. You can see that every command i, j you should do no more than once. Also order of commands doesn't matter. Actually, sequence of command you can represent as boolean matrix A with size n × n, where a_ij = 1 mean that you do the command i, j, and a_ij = 0 mean that you don't do it.

Let us describe one way to construct the matrix.

Let the starting image is boolean matrix G. A boolean matrix B of size n × n stores intermediate image that you will recieve during process of doing commands.

For the upper half of matrix G without main diagonal you should move line by line from the up to the down. For every line you should move from the right to the left. You can see that for every positions all nonconsidered positions do not affect the current position. So, if you see that values for position  i, j in the matrices G and B are different, you should do command i, j: set in the matrix A a_ij = 1, and change segments (i, i) - (i, j) and (j, j) - (i, j) in the matrix B.

For the lower half of the matrix G without main diagonal you should do it absolutely symmetric. At the end you should iterate over main diagonal. Here it should be clear.

Well, for matrix G you always can build matrix A and do it by exactly one way. It mean that this way requires minimum number of commands. So, you can get answer for problem by following way: you can build the matrix A from the matrix G and output number of ones in the matrix A.

There is only one problem that you should solve. Algorithm that you can see above works in O(n³), that doesn't fit into time limits. Let's speed up it to O(n²). Consider in the matrix B the upper half without main diagonal. During doing commands all columns of cells that placed below current position will have same values. Values above current position are not matter for us. Therefore instead of the matrix B you can use only one array that stores values of columns. It allows you do every command in O(1) instead of O(n). This optimization gives a solution that works in O(n²).

div1 D. Let us represent a number in the Fibonacci code. You can imagine Fibonacci coding by following way: i-th bit of number corresponds to the i-th Fibonacci number. For example, 16=13+3 will be written as 100100. You can represent into this code any positive integer, for that no two neighbouring 1-bit will be present. It is possible to do it by only one way (let's define this way as canonical). In the problem you should calculate a number of ways to represent some number into Fibonacci code in that two ones can be placed in the neighbour positions.

You can easily get the canonical representation if you generate several of Fibonacci numbers (about 90) and after that try to substract all of them in the decreasing order.

You should store positions of 1-bits of canonical representation into an array s in the increasing order. You can decompose any of them into two ones. It looks like that:

1000000001 // starting number;
0110000001 // there we decompose
0101100001 // the first "one"
0101011001 // using all
0101010111 // possible ways

After some number of such operations you will meet next 1-bit (or the end of number). This 1-bit also can be decomposed, but it can be "shifted" by only one bit.

Let us dp1[i] is number of ways to represent a number that consists of i last 1-bits of our number in the case that the first of 1-bits are NOT decomposed. Also let us dp2[i] is number of ways to represent a number that consists of i last 1-bits of our number in the case that the first of 1-bits are decomposed.

You can easily recaclulate this dp following way

dp1[0] = 1, dp2[0] = 0
dp1[i] = dp1[i - 1] + dp2[i - 1]
dp2[i] = dp1[i - 1] * [(s[i] - s[i - 1] - 1) / 2] + dp2[i - 1] * [(s[i] - s[i - 1]) / 2]
where [x] is rounding down.

Answer will be dp1[k] + dp2[k], where k is total number of 1-bits in the canonical representation. So, we have solution for one test.

div1 E. Consider all partitions of 7 × 8 board into dominoes. There is only 12988816 of them (you can get this number using some simple bruteforce algorithm)

Also, consider all "paintings" of 7 × 8 board (i.e. number of cells of every color) and find number of patritions into set of pills of 10 types for every of them. In the worst case you will get 43044 partitions (this number you can get using another bruteforce algo).

In the first part of solution you should iterate over all partitions of board into dominoes and find all sets of pills that you will get. You will have no more than 43044 of them.

In the second part of solution you should try to distribute all available pills for every of sets that you recieved in the first part. You should distribute them in such way that maximal number of colors match.

You should build a graph that composed from 4 parts - source, the first part of 10 nodes, the second part of 10 nodes and sink. There are edges between all pairs of nodes from neighbour parts. From source to the first part you should set capacities of edges equal to numbers of available pills of every type. From the second part to sink you should set capacities of edges equal to numbers of pills in the current partition. From the first part to the second part you should use infty capacities and set costs equal to number of MISmatched colors in the types of pills (it is some numbers in range from 0 to 2). At the end, you should find maximal flow of minimal cost (MCMF) if this graph and save a flow that gets minimal cost.

In the third part of solution you should restore answer from optimal flow.

In the second part of solution you can replace MCMF by usual maxflow. You can see that at the beginning MCMF will fill edges of cost 0. So, you can fill them by hand. After that you can drop all edges of cost 0 and 2 and just find maxflow.