Problem A: Approximations

First let us consider a slightly different problem. We replace rounding with truncation. It shall not be difficult to figure out a solution that uses a trie. It can be proved that x can be chosen to coincide with one of the given fractions.

Now consider the original problem. Rounding makes it more complicated since all approximations of a set of fractions do not necessarily form a tree structure. Nor does the aforementioned lemma hold in this case. However, scrutinizing a solution to the problem using truncation, we can discover that it does not rely on the relation between any two approximations of a fraction. Consequently, we can still use a trie. What makes the difference it that when working a node representing some fraction f of accuracy a, we have to additionally set counters to count the fractions hitting the two intervals [f − ^a⁄₂, f) and [f, f + ^a⁄₂). The want x can then be chosen accordingly to coincide with some fraction that has a corresponding node in the trie.

Problem B: Battle

In the i-th round (1 ≤ i ≤ N), depending on whether you attack there can be two possible outcome concerning you and Heilong's HP. If you attack, your HP decreases by A_i and that of Heilong decreases by x; otherwise your HP increases by max{y − A_i, 0} while that of Heiling remains unchanged. Based on this analysis, a solution proceeds in a greedy way: whenever possible, you attack; only when your remaining HP cannot stand the next attack by Heiling, retract some past decisions of attackting and change them to defending or healing in light of the gain of HP.

Problem C: Distance to the Prey

Now that the web is recursively quinquepartite, the method of solution is thus recursive quinquesection. First we determine the smallest S_k that contains Zhizhu and its prey’s locations. If the two locations are contained in some portion in the web of the shape of S_{k − 1}, we are then encountered a problem with reduced scale. Otherwise, a path can be directly constructed. (This latter case might be nontrivial.)

Problem D: Cross Counting

Keep track of the size of largest cross centered at each cell in each step using dynamic programming. A solution that handles each step in O(N + M) time will suffice.

Problem E: A Simple Problem with Integers

An efficient solution uses the segment tree. Each node represents a contiguous segment of integers, keeping track of their sums. Operations of increasing the integers are deferred with the increments properly stored in the tree and not explicitly computed until some query involves the corresponding nodes.

Problem F: Dual Core CPU

Any assignment of the modules to the two cores can be modeled by a cut in the flow network G = (N, A) where N = {s, t} ∪ {1, 2, …, N} and A = {(<s, i>, A_i) | 1 ≤ i ≤ N} ∪ {(<i, t>, B_i) | 1 ≤ i ≤ N} ∪ {(<a, b>, w), (<b, a>, w) | a cost w has to be charged if modules a and b are assigned to different cores}. By the max-flow-min-cut theorem. the desired answer equals the value of the maximum flow from s to t.

Problem G: Walls

We can use an offline algorithm which scans the walls in each of the four directions to find the minimum time that Xiaoniao hits a wall. During each scan, a segment tree is used to record whether some wall stands in the way of Xiaoniao’s flight and the position of the closest one of such walls. Besides, special check has to be done to deal with circumstances where space wraps around.

Problem H: Integral Roots

Factorize a₀ and test its factors as candidates of the integral roots.