Actually string 01 also has leading zero:)

Arbitrary number — d is the same for any x.

If you have something like (??))), we need to replace the second ? with ( and get balance of 3 instead of 1, or we will not be able to form correct sequence.

For each vertex find number d such that we need d numbers >= x to get value x in this vertex. For leaves it's 1, for min it's sum of this value in children, for max it's min of this value in children. Now answer is number of leaves — this value in root.

Because 2 is the only even prime number.

Bruteforce, I think. There are 6 permutations for each of 7 point (you can fix the first), so it is 6^7 ~ 300k — fast enough.

You can't eat the same type (1) twice in row, you can't start with type 1 (not enough high), and if you eat the (0 1 3) first, you can eat one type 1, and nothing else (you are still not high enough to eat 0 20 3).

If comment have negative votes — then somebody thinks it is bad.

Don't try to understand negative votes on codeforces.

According to russian version of post — yes, it will.

You have adjacent "1".

n=3 010 000 010

00100 00000 00100 00000 00100

Compiled with right keys? It works for 13 seconds on my PC without optimisation, and 1.7 with O2.

Thank you. My implementation of Floyd was wrong also, and got the same error. I really shouldn't try to save memory:(

Number of fixed points = max {i| b[:i] is subsequence of a}

First, precalc time(i,j) = min time for moving from i to j without changing car. Second, use dynamic: time2(i,j,k) = min time for moving from i to j with changing car <= k times. Base: time2(i,j,0) = time(i,j). Step: time2(i,j,k+1) = min(time2(i, j, k), min_l(time2(i,l,k) + time2(l, k, 0)) (not sure, that first argument in external min is necessary). When you go from i to j, you change car last time in city l, and move from i to l with changing car <= k times, and from l to k without changing car.

Let me in: I tried to hack really wrong solution A div 2, but failed to find 3 numbers a,b,n: n-a % b != 0, n-b % a != 0, n % (a+b) == 0.

(x,y) (x+1,y) (x-1,y) (x,y+2) is not a rhombus: 3 vertex on one line.

You want to find y_n. You should introduce some additional variables x^1_i,..,x^m_i, so that you (y_{i+1}, x^1_{i+1}, ..., x^m_{i+1}) from (y_{i}, x^1_{i}, ..., x^m_{i}) is linear. Now you can write this dependence as multiplication by matrix, and use fast pow.

Let A and B be numbers of up and down triangles. Then the transformation after 1 year is (A,B) -> (3*A+B,3*B+A). It is exactly transformation given by matrix T = ((3,1),(1,3)). Now you can calculate T^n % p, and write out sum of it first row.

You can use Lagrange's method

Also, it is possible (it will be run-time better, but code-time worse) to transform this matrix to Jordan normal form, and get a formula for the task.