In fact need to do what is asked in the statement. We need to find in a cycle the maximum height h, counting, how many blocks must be in i-th row and adding these values to the result. Iterate until the result is not greater than n.
Jury's solution: 8924831
Sort lanterns in non-decreasing order. Then we need to find maximal distance between two neighbour lanterns, let it be maxdist. Also we need to consider street bounds and count distances from outside lanterns to street bounds, it will be (a - 0) and (l - a[n - 1]). The answer will be max(maxdist / 2, max(a - 0, l - a[n - 1]))
Time complexity O(nlogn).
Jury's solution: 8924823
Sort (ai, bi) in non-decreasing order for number of essays bi, after that go from the beginning of this sorted pairs and add greedily the maximal number of points we can, i.e. add value min(avg * n - sum, r - ai), while total amount of points will not be greater, than avg * n.
Time complexity O(nlogn).
Jury's solution: 8924807
Let's create vector rez with size x + y, in which there will be a sequence of Vanya's and Vova's strikes for the first second. To do this, we can take 2 variables cntx = cnty = 0. Then while cntx < x and cnty < y, we will check 3 conditions:
1) If (cntx + 1) / x > (cnty + 1) / y, then add into the vector word “Vova”, cnty++.
2) If (cntx + 1) / x < (cnty + 1) / y, then add into the vector word “Vanya”, cntx++.
3) If (cntx + 1) / x = (cnty + 1) / y, then add into the vector word “Both” 2 times, cntx++, cnty++.
Then we are able to respond on each query for О(1), the answer will be rez[(ai - 1)mod(x + y)].
Time complexity O(x + y).
Jury's solution: 8924773
As long as gcd(dx, n) = gcd(dy, n) = 1, Vanya will do full cycle for n moves. Let's group all possible pathes into n groups, where 1 - th, 2 - nd, ... , n - th path will be started from points (0, 0), (0, 1), …, (0, n - 1). Let's look on first path: (0, 0) - (dx, dy) - ((2 * dx) mod n, (2 * dy) mod n) - ... - (((n - 1) * dx) mod n, ((n - 1) * dy) mod n). As long as gcd(dx, n) = 1, among the first coordinates of points of the path there will be all the numbers from 0 to n - 1. So we can write in the array all relations between the first and second coordinate in points for the path, that starts in the point (0, 0), i.e. y = 0, y[dx] = dy, ... , y[((n - 1) * dx) mod n] = ((n - 1) * dy) mod n. Now we know, that all points with type (i, y[i]), where 0 ≤ i ≤ n - 1, belong to the group with start point (0, 0). In that case, points with type (i, (y[i] + k)modn) belong to the group with start point (0, k). Then we can add every point (xi, yi) to required group k for О(1): (y[xi] + k) mod n = yi, k = (yi - y[xi] + n) mod n. Then we need just to find group with the maximal amount of elements, it will be the answer.
Time complexity O(n).
Jury's solution: 8924746
P.S. Sorry for my bad English, I hope, I will correct this editorial as much, as possible.