Problem D.

First, let’s divide graph to connected components (provinces). Next, we consider only new graph on these components – for each province we assign a vertex of the graph. Let the total number of provinces is n. Initially the graph is empty since there are no roads between different provinces. Also for each province we have a limit of the number of tunnels that can be constructed from this province: k_i = min (k, c_i) where c_i – the number of cities which was originally contained in the province (component) i. The resulting provinces graph should be connected after building tunnels and roads. When k = 1 we have to build at least n - 2 roads, otherwise the graph will have at least 3 components and at least 2 tunnels should be constructed from one of them which is prohibited.

Further, we assume that k > = 2. Let’s calculate the largest number of tunnels we can build. Let s – the sum of all numbers k_i. Obviously we cannot build more than s / 2 tunnels since each tunnel connects exactly two provinces. The following statement is true: we can construct s / 2 (rounded to the lower side) of tunnels or to make a graph connected by constructing n - 1 tunnels (if s / 2 > = n - 1). Let’s consider vertices which have k_i > 1. We may connect these vertices into a chain using tunnels. After that let’s start to connecting vertices with ki = 1to the chain (using tunnels too) while it is possible. Suppose we had less than s / 2 tunnels built and we are unable to build one more tunnel. It means that we have exactly one vertex j with degree no more than k_j - 2. Thus k_j > 1 and this vertex is included into the chain and all the vertices with k_i = 1 are attached to this chain too (otherwise we could build another tunnel), so the graph is connected.

If after building the tunnels we have a connected graph then the answer is 0. Otherwise the graph consists of n - s / 2 components, that is we need to build at least n - s / 2 - 1 roads. In fact such a number of roads will be enough. Let’s draw each of n - s / 2 - 1 roads the following way. First, choose 2 different connected components in the current graph. Because we have built tunnels (and possibly roads) only between different components each of the chosen components is a tree. So these components have vertices with degree not greater than 1. Now, let’s choose one such vertex in each of the selected components and connect the components through these vertices (i.e. the vertices are merged into one keeping the edges from them). Thus we have a new vertex (province) with no more than two tunnels constructed from it, so we did not violate the terms since k >= 2. Thus we can get a connected graph by building additional n - s / 2 - 1 roads which is the answer for the problem.

Problem E.

When x = 2 then the answer is 0. Further we assume that x > 2.

In order to uniquely identify the desired number of items t we must choose a set of numbers ai so that for every y from 2 to x the representation in modes a_i is unique, i.e. sets of numbers b (y, i) = y / a_i (rounded up) are pairwise distinct among all y. Note that for each i function b(y, i) is monotone by y. Hence if for some i and numbers y and z (y < z) holds b(y, i) = b(z, i) then b(y, i) = b(y + 1, i) too. So to select the set of numbers a_i it is sufficient to guarantee that for each y from 2 to x - 1 exists a number j such that b(y, j) < b(y + 1, j). It is easy to see that b(y, j) < b(y + 1, j) if and only if y is divisible by a_j. Thus, it is necessary that for each y from 2 to x - 1 exists number a_i so that y is a multiple of a_i. If some number a_i is equal to 1 Vasya can just see the list in this mode to find the desired number and the answer for the problem is 1. Otherwise it is necessary and enough to take all the primes p_i < x in our set a_i to find the number. Indeed if we will not use some prime number p_i then we will be unable to distinguish numbers p_i and (p_i + 1) (since p_i is not divisible by some of the selected numbers). On the contrary if we will use all primes less than x then any number from 2 to x - 1 will be divisible by at least one of them. Thus we need to check whether there are all prime numbers less than x among a_i. Since the number of primes from 1 to x is about O(x / ln (x)) for large x all prime numbers less than x cannot be in the set of numbers a_i. For example the following statement is true: if x > 20 * n then the answer is -1. This means that we can use the Sieve of Eratosthenes to find all primes less than x for x <= 20 * n and to check whether there is at least one number from them which does not occur in a_i. If such number exists then the answer for the problem is -1 otherwise the answer is the number of primes less than x.

Problem F.

If for some velocity v₁ we were able to go from point A to point B and receive no more than k hits, then for any velocity v₂ > = v₁ we also will be able to go from A to B. So we can use  the binary search algorithm to find the answer. 

Suppose we have fixed speed of the tank v. Now we have to count how many enemy tanks will be able to shoot at our tank during the ride. Let’s consider enemy tank i located at the point P on the plane. It may aim at our tank in two ways: turn the turret at point B or rotate the turret at point A and then start turning it from point A to point B. In the first case we may just compare the time required for the tank  to move from A to B with the time required the enemy to aim the turret to point B. If the enemy tank will be able to take aim to B before we can reach this point then the enemy can make a shot. Next consider the second possible enemy strategy.  Let’s draw perpendicular PQ to the line AB. So we have divided the segment AB into 2 parts: AQ and QB (if Q does not lie on the segment AB then one of the parts will be empty and the other is a segment of AB. In this case let Q denote the end of segment AB closest to the base of the perpendicular). Let’s consider the first part of the segment - AQ (before the base of the perpendicular). It is easy to check that while the angular velocity of the turret is a constant, the linear velocity of the enemy sight along the segment AQ is monotonely decreasing. Given the fact that the speed of our tank along AB is constant we find that the difference between the coordinates of the enemy’s sight and the tank at the AQ interval is a convex function of time (second derivative is negative). Also this fact can be verified by finding the second derivative of this function explicitly. Thus we can use the ternary search algorithm for finding the minimum of this function on a time interval corresponding to time when our tank rides at segment AQ. When the minimum value of this function is negative the enemy is able to take aim at our tank and perform a shoot. Otherwise, the tank will ride ahead the enemy sight on the whole interval AQ. (Using similar statements we can find for example the minimum value of the time difference between reaching a point D of the interval AQ by the enemy sight and by our tank). It is possible to avoid the ternary search by finding a moment when the speed of the sight is equal to the speed of our tank and check who is closer to point B at this moment. But in this case we are to carefully handle the cases where one velocity is always greater than the other on the whole interval. 

Now let’s consider the second part of the segment - QB (after the base of the perpendicular). If the enemy is unable to shoot in our tank at the first part of the segment (AQ) then at the time of sighting the enemy on point Q our tank will be located closer to point B than the sight. Similarly the first part of segment AB, we can prove that the linear speed of sight along QB is monotonely increasing. So if at some point C of segment QB the sight of the enemy tank has caught our tank then speed of the sight should be higher than speed of our tank at that moment (otherwise the enemy would not be able to catch the tank). Due to the monotonicity of the sight velocity on the remaining segment CB the sight will be faster than the tank and the sight will reach point B before our tank. Accordingly, if the enemy's sight has reached point B after our tank then the tank was ahead the sight on the whole interval QB too. Thus, to determine whether the enemy can shoot it is sufficient to check only point B. 

Performing these calculations for each of the n enemies we get the number of hits on our tank and comparing this value with the number k we go to the desired branch of the binary search.