One of possible ways of solving the problem is to compare every leave with all taken before. If it matches one of them, than do not take it. Since the order of leaves is immaterial, you can just sort all the leaves (for example, as pairs of strings) and delete unique leaves.

The problem is to find a number of triples (x, y, z), such that 0 <= x <= a, 0 <= y <= b, 0 <= z <= c and 0.5 * x + y + 2 * z = n. Trying all triples gets TL, but you can try all possible values of x and y, satisfying 0 <= x <= a, 0 <= y <= b. When x and y are fixed, z can be determined uniquely. So we get O(a*b) solution.

The easiest solution is to process all the days from 1 to n, and check for each day, that it is covered by exactly one segment [a_i, b_i]. If you find a day which is covered by less or more than one segment, output this day.

Let us call ships that were produced initially ''the ships of the first generation''. When a ship of the first generation reaches a planet, and new ships are build there, we call them ''ships of the second generation'', and so on.

Let us prove that the first collision is between two ships of the second generation, moving towars each other. Indeed, ships of the first generation move in distict dirrections (no three points lie on the same line), so they cannot collide. If a ship of the first generation collides with a ship of the second generation, the lines of their moving form a triangle OAC, where O is the first planet, A is a planet where the ship of the second generation has been produced, and C is a point of the collision. But it's clear that OA + AC > OC, and ships are moving with the same speed, so such collision cannot happen.  

Speaking about ships of the third generation, they cannot be produced at all! Suppose that a ship from the first planet has reached the planet A, and then a ship from planet A has reached the planet B. But by virtue of the triangle inequality, a ship from the first planet has reached the planet B earlier, ships were produced at B, one of them was sent to A and collide with the ship, moving from A to B.

For similar reasons two ships cannot collide, if one of them is moving from A to B, and another is moving from C to D. Ships moving from A to C and from C to A will collide earlier.

Thus, the solution is to compute for each pair of planets A, B a perimeter of the triangle OAB, and find the minimal one.

There are multiple ways to split the string. One of them is to split it into parts of lengths n / k and n / k + 1, if n is not divisible by k. Here n is the length of the given string. If lengths of such parts are not less than a and not greater than b, the answer is found. Otherwise there is no solution.

The answer may be rather large, because it grows exponentially with growth of n, but it fits int64. Indeed, there are 10 ways to choose the first digit, than 1 or 2 ways to choose the second one, 1 or 2 ways for the third one, and so on. So the number of ways doens't exceed 10· 2^n - 1.

The problem can be solved by dynamic programming. Let d_ij be a number of ways to get first i digits of a correct number with the i-th digit equal to j. From such part of a number we can obtain a part of size i + 1 with (i+1)-th digit equal to (j + a_i + 1) / 2 or (j + a_i + 1 + 1) / 2, where a_i is the i-th digit of Masha's number. So if we have d_ij for all j, we can obtain d_{i + 1, j}.

Do not forget to subtract 1, if Masha can obtain her own number. It will happen in case when each two successive digits in the given number differs at most by 1. 

First, if the tiling is possible, it is unique. Consider the most upper-left position (x, y) that is not cut out. If it is black, the tiling is impossible. If it is white, look at the next position (x, y + 1). If it is cut out, the only possible way to put a trimino is to put it vertically. Otherwise we must put a trimino horisontally, because if we put it vertically, we wouldn't be able to cover the next black position (x, y + 1). These considerations give us an algorithm for the solution. 

Four symbols a, b, c, d are always enough to represent the tiling, because a trimino can have common sides with no more than 3 triminoes located to the left or above it. So even if all the 3 triminoes  are marked by 3 different symbols, the next one may be marked by the 4-th one.