Problem A.

Let's define a half-filled square of size k as an empty square of size k after adding a cookie of the biggest posible size.

Problem B.

It's obviously, that sentences should be added into the SMS greedily. Really, if we put the sentence into the new message, when it's possible to add into previous, the number of messages may be increased. The only thing you should pay attention is correct processing whitespaces between the sentences.

Problem C.

Will be added soon.

Let's learn how to solve more easy problem: it's need to count a number of lucky tickets with 1 ≤ a ≤ x and 1 ≤ b ≤ y. Rewrite sentence a * b = rev(a) * rev(b) as a / rev(a) = rev(b) / b. Brute all a and count a number of irreducible fractions a / rev(a) using, for example, map from STL. Now for every b you should count the number of fractions a / rev(a) equal to rev(b) / b and add to answer.

Come back to our problem. 

If the number of lucky tickets with 1 ≤ a ≤ max_x and 1 ≤ b ≤ max_y less than w, it should be printed  - 1. If the solution exist, let's use the method of two pointers. 

We need to keep up the quantity of lucky tickets with 1 ≤ a ≤ x and 1 ≤ b ≤ y for some state (x, y) an change it to (x,y+1), (x+1,y), (x,y-1), (x-1,y). That's why we create two structures of type map (named m1 and m2). Let's learn how to change state from (x,y) to (x,y+1), (x+1,y), (x,y-1), (x-1,y). If we want to increase  (decrase) the value of x, we should add (subtract) m2[x/rev(x)] to (from) the number of lucky tickets and increase (decrease) m1[x/rev(x)] by one. In the case of changing y you should do the similar actions.

Let's set the state (x, y), where x = max_x, y = 1 and count the quantity of lucky tickets for it. We will be increase y, while the number of lucky tickets is less than w. Obviously, that it will be the least y for x, such as it will be enough lucky tickets in the range. Relax the answer. You had to decrease x by one and do the same actions while x is greater than one.

The anser have the least value of x * y because we relaxed it with the optimal state for every x.

So, the x was equael to every value between 1 and max_x not more than once. The similar is correct for y because it was only increasing. The time need for change the value in map is O(log(map_size)), that's why the algorithm lave an asymptotic form as O(max_x * log(max_y) + max_y * log(max_x)).

Problem D.

Notice, that any point from the triangle based on first three points will be into the area bounded with the convex hull in the future. Let choose one of these points ad set it as the origin. All points of convex hull will keep in structure like map in C++, where the key is the angle of vector from the origin to a point. No two points from the hull will have the same angle.

How to answer the second-type queries? For the point from the query (A) let's find the closest point clockwise (B) and the closest point anticlockwise (C). If the vectors AB and AC make up a clockwise rotation, then point A doesn't lay into the convex or on it's bounds. 

How to answer the first-type queries? If the point from the query (C) lays into the convex hull, then do nothing else let's find two closest points clockwise relative to point C (the closest will be named A, tho other will be named B). If rotation from the vector AB to the vector AC is a counterclockwise rotation then processing points laying clockwise relative to point C in ended, else you have to delete point A from the structure and repeat the same actions. The similar actions you should apply to points anticlockwise relative to point C.

All points will be added and deleted in the structure not more than once. These operations need O(log(h)) time, where h is a number of point in convex hull. Total  asymptotic form is O(q * log(h)).

Problem E.

Notice next facts. If we have the fixed state of some regional centers then for every city will be assigned the nearest regional center. The regional center of some city will be assigned for all cities between this city and it's regional center. It means that tree should be divided into some subtrees. Also define d[0] = 0.

Let's solve the problem using "crossed" Dynamic Programming.

First function of DP. D1(T, g, x, s) will be responsible for forming the subtree with the regional center g. T is somme subtree of tree from the input defined with edge uv. regional center g must be situated in T. Let's consider that g is assigned to v. The aim will be considered in choosing edges which will bound our subtree. Picture:

Green and red edges connect cities which g was assigned. Purple edge bounds the set of such cities. Notice, that vertexes laying on the red pass cannot be bounding, because g is assigned to v. 

Let xs edge be bounding, then for subtree T' (vertexes of it's subtree are into the circle) call the secnod funtion of DP D2(T').

The second function of DP will brute every point of subtree T' as a regional center and call D1.

D1 have O(n³) states, because the number of subtrees T is O(n), number of options to choose g is the same and pair (x;s) makes up an edge, number of edges is 2*n-2. The second function of DP has O(v) states and transition need O(v) iterations. Thats why solution need O(n³) memory and have asymptotic form O(n³).