Editorial Tinkoff Internship Warmup Round 2018 and Codeforces Round #475 (Div. 1...

There are 2 cases:

If weight of the split equals , then the split consist of ones. Here we have only 1 option.

Else maximum number in the split is more then 1. Then we can replace all maximum numbers with twos and the rest we split into ones and weight will be the same. So, here we have options.

Answer for this problem is + 1.

Adding C·k to account is equivalent to adding C to prices of all come, but not read messages. Then after every minute to every unread messages adds C - B. If C - B is positive, then answer is maximum when we read all messages at the time T. Otherwise we should read every message at the time it comes.

Let and .

Let's notice that according equality is true:

We can easily get values of , . We only have to count the value of geometric progression.

Remember to handle the situation when . In this case it is not necessarily means that .

If n is even, then the answer is always NO, because such trees have odd degree, but we can destroy only even number of edges.

For any odd n the answer exists.

Let's call dfs(i) from subtree i and destroy such nodes, that new subtree will be empty or for all alive nodes in connected component will be true, that they have odd degree.

Realisation of this dfs:

Call it from sons of i and recount degree of i, if it is even we destroy all subtree.

Assume, that after the destruction we have nonempty subtree. All nodes have odd degree, so amount of left nodes is even. So number of left edges is odd, but in start we have even count of edges, contradiction. That means, that we destroyed all nodes.

There are a lot of ways to solve this problem.

Let occurs in input (sum of ) times аnd occurs . Then on a side of initial rectangle number of times occurs number of times occurs is a ratio . Analogically for .

Let's build the smallest rectangle which satisfies this ratio and call him the base one. Then initial rectangle should consist of it.

The last step is to check that initial rectangle consists of base ones. To do this we'll iterate over all types of rectangles in input and if we find a mistake - print 0. In this way we will check no more than types of recktangles.

An answer for this task is number of divisors of ratio between the initial rectangle and the base one (it's not hard to see that this ratio equals to of all )

Let be the summary length of

Number of different lengths of is . All are distinct, so summary number of their entries in is .

Let's find all entries of every . To do this we can use Aho-Corasick's algorithm. Then we know entries of , it is not hard to calculate the answer.

Let's call a sell "good", if for its coordinates the following condition is satisfied x2 + y2 ≤ R2.

For each good cell we consider the equation of its expected value:

f(x, y) = p1·f(x - 1, y) + p2·f(x, y + 1) + p3·f(x + 1, y) + p4·f(x, y - 1) + 1.

Then this problem can be reduced to solving the system of linear equations.

We can do this using Gauss's method with a complexity of O(R6), but this solution gets TL.

Now, we can see that we only need to calculate f(0, 0). So we will handle cells top down. While handling each row, we will relax values of all previous rows and a row of cell (0;0). Also we will iterate only for non-zero elements of each row. This solution has a complexity of O(R4).

Prove of the complexity:

Let's dye yellow all cells that we have already passed, green - all cells adjacent to them and black - all other cells. Then next cell which we will add is green. Note that its equation(for a moment of adding) doesn't include yellow cells. It consists of initially adjacent black cells and green cells. It's not hard to see, that then row includes only O(R) non-zero elements and the current green cell is inside of O(R) not visited rows. So one row in Gauss's method is handled inO(R2) and there are O(R2) rows. That's why this Gauss's method works in O(R4).