Observe that if Kirito fights a dragon whose strength is less than Kirito's strength, then Kirito does not lose anything — in fact, he even gains a nonnegative strength increase. Taking note of this, let's for each step choose some dragon whose strength is less than Kirito's current strength, and fight it. After performing some amount of these steps we'll eventually end up in one of these two situations: either all dragons are slain (then the answer is "YES"), or only dragons whose strength is not less than Kirito's strength remain (then the answer is "NO"). On each step we can choose a suitable dragon to fight either by searching through all dragons or by sorting the dragons by strength in non-descending order in advance.
It can be shown that only squares of prime numbers are T-primes, and that there are not too many of them — as many as there are prime numbers not greater than . Precompute these numbers (using, for example, the sieve of Eratosthenes) and store them in an array or an
std::set, then we can answer each query by simply checking whether the number in question is amongst the precomputed numbers.
Let's compute the minimum number of operations needed to get all 1s in each of the m columns. For this, traverse each row twice — one time to the left and one time to the right, recording the index of the nearest cell with 1 (in corresponding direction) for each column in this row. Then the number of operations for any particular column is the sum of the computed values over all rows. In turn, the answer to the problem is the minimal value of these sums.
Observe that when we visit some planet, the best strategy is to arrive as early as we can and then wait for the nearest free moment of time to move further. Hence this problem can be solved with the Dijkstra's algorithm by slightly altering the definition of a shortest distance. When we process a planet (meaning that we already know the minimum time needed to reach it), we need to check the array of arrival times for this planet and find the first moment of time in which we can leave this planet — this will be the distance that we will be adding to outgoing paths from this planet. It's clear that we will traverse each array of arrival times no more than once. Additionally, one must pay attention to these cases: when a traveller arrives to planet 1 at time 0 (then Jack has to wait) and when a traveller arrives to planet n at the same time as Jack (then Jack needs not to wait).
Let's call Alice's edges simply edges, and Bob's edges the antiedges. For each edge pair of the initial complete graph that pass through the same vertices, assign a weight: for each pair of edges the weight +2, for each pair of edge and antiedge −1 and for each pair of antiedges +2. Now calculate the sum of all the weights. Observe that each Alice's or Bob's triangle adds exactly +6 to the sum, and each combination of three vertices that do not form the triangle in any of the two graphs adds exactly 0 to the sum. The sum itself is calculated by iterating over all vertices and adding the total weight of all the edge pairs that pass through this vertex. If the degree of the vertex is d, then we should add d(d - 1) - d(n - d - 1) + (n - d - 1)(n - d - 2) to the final sum. Since each triangle adds +6 to the sum, then the answer is equal to the sum divided by 6.
Let's calculate the dynamics
d[i][k] — the minimal possible height of the last tower that we can obtain by merging the first i left towers into at least k towers. Assume we already have calculated the dynamics' values for the first i towers. Now we iterate over the all possible tower intervals [i + 1;j]; say the sum in the pending interval is equal to s. Now we find the greatest k such that
d[i][k] is not greater than s. Then we update the value of
d[j][k+1] to the minimum of s and
d[j][k+1]. Notice that when k increases the values
d[i][k] do not decrease. Because of that we can iterate over intervals in the decreasing value of j, and corresponding k can be found using a single pointer over values of
When we arrive in the position j during the dynamics, some of the
d[j][k] values are updated, but some are still not. Using the same observation that along with the increasing of k the values
d[j][k] do not decrease as well, we can make a single run over the values of k in the decreasing order and update the dynamics' values as follows:
d[j][k] := min(d[j][k], d[j][k+1]). This is done in the beginning of the dynamics' iteration.
In the end we can find the greatest k for which there exists an answer among the values of
d[n][k]. The answer to the problem then is n - k.
First let's establish some facts that we will use in the solution. With how much probability can the fisherman get a particular set of gifts, among which there are ai gifts of i-th name? In total there are such sets, since there are exactly subsets of gifts with i-th name of size ai, and two different names are independent during the gold fish's choice. Then the described particular set of gifts we can get with the probability of , by asking ai gifts of i-th name.
Now we know the probability p of obtaining one particular gift set A. Now observe that from p we can calculate the probabiltity p' of obtaining the set A along with some one other gift of x-th name in constant time. Say there are already ax elements of x-th name in A. Using the formula from the first paragraph, we can deduce that:
Let's solve the main problem now. We sort all the gifts in descending order of their prices. It is clear that the fisherman will definitely ask the names of all the gifts among the first n ones whose prices are not equal to the price of the n-th gift in the list. Let's say that this set of gifts is the base, and it has b elements. Then there is still n - b unchosen gifts, and we know that all of them will have the price equal to the price of the n-th gift in the list. Say the price of the n-th gift is d, and there are exactly s gifts with the price d (keep in mind that each of them has a different name); also call these gifts dubious. We can also deduce that the fisherman can make different decisions, where l = n - b.
So now we have some s dubious gifts with the price of d; let's enumerate them in any order. We calculate the dynamics f(x, y) — the cumulative probability of obtaining n most valuable gifts, if there are x chosen from the first y in the list. It is clear that f(0, 0) = p, and f(l, s) contains the answer to the problem. Using the coefficients we have deduced earlier, we get two transitions in the dynamics:
- , if we add y + 1-th dubious gift to the set of x chosen among the first y dubious gifts;
- , otherwise, if do not put the y + 1-th dubious gift. This dynamics can be computed in O(t2) time, where t is the total number of gifts.