NEERC Pilot Junior Contest — Transcaucasian Group

Fix the number of digits i that N will have and count, for that many digits, how many numbers of length ≤ i sort lexicographically before K — call that count C. As i grows this prefix-count only increases, so the right i is the first one where the running count reaches M. Within that digit length, the lexicographic rank of K is determined by "how many i-digit strings are less than K's own padded value," which reduces to a digit-DP style walk over K's decimal digits.

Concretely: for each digit length i, build the largest i-digit number that is still lexicographically before K (this is K's decimal representation truncated/adjusted to i digits, with its last kept digit decremented), and add that count to a running total. Once the running total reaches or passes M at digit length i, the answer's own decimal digits can be reconstructed directly from M - C by walking back through the same counting logic and appending digit i on top of K. Because N can have up to ~19 digits, all of this arithmetic (add, subtract, compare) is done on custom big integers represented as digit arrays rather than machine integers.

A brick has three distinct pairs of face dimensions: (A,B), (A,C), (B,C). For a rectangular cross-section D × E to let a rectangle of side lengths a × b through (tilting is allowed, not just axis-aligned pushes), the classic test is: the rectangle fits straight if a ≤ D and b ≤ E (in either assignment), and otherwise it may still fit tilted at some angle if a diagonal placement clears both hole dimensions. The jury solution checks all 6 combinations of (face pair, hole-dimension assignment) with an exact "fits(a, b, d, e)" tilted-rectangle-through-rectangle test, expressed entirely in scaled integer arithmetic (multiplying every length by 10 to avoid floating point) to keep the geometric inequality (derived from setting up the rectangle's rotated bounding box and solving for a valid tilt angle) exact. If any of the 6 checks succeeds, the answer is YES.

The optimal square's southwest corner can always be pinned to either the park's own southwest corner (x = 0 or y = 0) or to the x- or y-coordinate of some tree — an unconstrained corner could always be nudged toward the nearest such coordinate without shrinking the square. This gives at most (N+1) candidate x-values and (N+1) candidate y-values, so it suffices to try every pair (p, q) drawn from {0} ∪ {tree x-coordinates} × {0} ∪ {tree y-coordinates} as a candidate corner (O(N²) pairs). For each candidate corner, the largest square that avoids all trees is bounded above by the distance to the park's far edges (min(W-p, H-q)) and, for every tree strictly northeast of the corner, by max(treeX - p, treeY - q) (the square must stop before enclosing that tree). Taking the minimum of all these bounds gives the largest valid square at that corner; the best over all O(N²) corners is the answer. Overall O(N³), comfortably fast for N ≤ 100.

Because the second message encodes a space followed by exactly the same clear-text as the first message, its first byte's clear-text is known: a space (0x20). That immediately gives the first key byte: K[1] = E2[1] XOR 0x20. From there, message 2's byte i+1 decodes to the same clear-text character as message 1's byte i (since message 2 is message 1 shifted right by one position). So once K[i] is known, decode C[i] = E1[i] XOR K[i], and since C[i] is also the clear-text at position i+1 of message 2, the next key byte follows as K[i+1] = E2[i+1] XOR C[i]. A single left-to-right pass reconstructs all N+1 key bytes in O(N).

This is a transportation-optimality check, decided via a negative-cycle argument on a graph over shelters. Define a "transfer cost" from shelter j to shelter k as the cheapest possible change in total time from moving one worker's assignment from j to k: pick, among all buildings currently sending workers to j, the one for which dist(building, k) - dist(building, j) is smallest. If that cheapest transfer is negative and shelter j has spare assigned workers while shelter k has spare capacity, the plan is improvable by that single move. More generally, run an all-pairs shortest-path relaxation (Floyd–Warshall) over these pairwise transfer costs to find chains of transfers (j → l → k) whose combined cost is negative and whose endpoints are feasible (a valid start and end of a transfer chain, including loops back to the same shelter to catch 3+ cycles) — any such negative chain proves the plan suboptimal and is applied by walking the recorded path and moving one worker at each hop. If no negative transfer or transfer-chain exists, the plan is already optimal (this is exactly the transportation problem's optimality condition: no improving cycle in the reduced-cost graph).

Classic interval DP. Let cost[i][j] be the minimum folded length of the substring from position i to j. Base case: single characters cost 1. For a longer interval, two kinds of transitions are tried: (1) split the interval at some point k into two folded pieces and add their costs (cost[i][k] + cost[k+1][j]); (2) repeat — if the interval's length is divisible by some period lr, and the substring is literally lr-periodic across the whole interval, fold it as x(period) where x is the repeat count, costing 3 + cost[i][i+lr-1] (for the digits, parens) plus one extra character for each extra decimal digit needed to write x (10 ≤ x needs 2 digits, 100 ≤ x needs 3). Take the minimum over both transition types for each interval, filling the DP table by increasing interval length (O(n²) intervals, O(n) work each for the split, O(n) periods to test for the repeat check — O(n³) overall for n ≤ 100). The actual string is reconstructed by remembering, for each interval, which transition achieved the minimum, and recursively expanding from the top interval.

Each sphere, seen from the origin, subtends a circular cone of directions that would hit it; a ray "kills" a ghost exactly when its direction lies inside (or on) that ghost's cone. The optimal ray direction, if it is interior to several cones simultaneously, can always be perturbed to lie on the boundary of at least one of those cones without losing any of the others — and generically it can be pushed to the boundary of two cones at once (their intersection curve). So it suffices to test only two families of candidate directions: the exact direction to the center of every ghost (N candidates), and, for every pair of ghosts, the (up to two) directions lying on the intersection of their two viewing cones — derived from the geometry of two cones sharing an apex, by decomposing the candidate direction into a component along the plane spanned by the two ghost-center directions and a normal component (O(N²) pairs, O(1) trig work each). For every candidate direction, count how many spheres the ray actually intersects by comparing the perpendicular distance from each sphere's center to the ray against its radius. Overall O(N²), which comfortably handles N ≤ 100.

State space is small enough for exact DP/memoized recursion: (mana remaining, pack's current total HP, pack's current square) — at most MP_H × (HP_M × N_M) × N states, each ≤ 50 × 100 × 10 ≈ 50000. Define GetHPNeed(mana, packHP, packSquare) as the minimum hero HP required, right now, to still guarantee eventual victory from this state. It tries all three spells recursively: Lightning Bolt reduces packHP by L at the current square (immediate win if that kills the pack); Heal is only useful if the hero can survive next turn's monster hit regardless; Teleport is only ever useful sending the pack beyond V+1 squares away (closer choices are dominated). Each branch accounts for the HP lost if the pack ends its following move on square 1. Memoizing on the three-tuple avoids recomputation, and comparing the memoized minimum HP need against the hero's actual starting HP_H answers VICTORIOUS/DEFEATED; replaying the recorded best spell at each step from the initial state reconstructs the winning move sequence.

A 45°-right-triangle piece always has its right-angle vertex at a point where one horizontal-or-vertical cut crosses one diagonal cut (or the plate border, treated as extra horizontal/vertical cut segments), with its two legs running along the horizontal/vertical direction and its hypotenuse along a diagonal. The jury solution doubles all coordinates (so diagonal/axis intersections stay integral), adds the four border edges as extra cut segments, and computes every pairwise intersection point between perpendicular-family cuts (horizontal×vertical, horizontal×diagonal, vertical×diagonal, diagonal×diagonal), marking each intersection on a grid. Then, for every horizontal/vertical crossing point, it walks outward in the four axis directions to the nearest other marked intersection to get four candidate leg lengths, and for every diagonal/diagonal crossing point it walks outward along the two diagonal directions similarly — for each of the (up to 4) leg-length combinations at a vertex, it checks whether the implied third side (the hypotenuse or the matching perpendicular leg) is actually an uninterrupted cut segment between those two points before counting it as a real triangular piece. Summing valid triangles over all crossing points gives the answer.

No jury solution for this practice problem survives in the archive, so the idea here is derived directly from the sample behavior. Reading N = -3 giving -5 confirms the range is meant inclusively in either direction: it is the set of integers from min(1, N) to max(1, N), e.g. for N = -3 that is {-3, -2, -1, 0, 1}, which sums to -5. The general closed form avoids any loop: let a = min(1, N) and b = max(1, N); the sum of the inclusive integer range [a, b] is the arithmetic series total (a + b) * (b - a + 1) / 2. For N = 2: a=1, b=2, sum = (1+2)*2/2 = 3. For N = -3: a=-3, b=1, sum = (-3+1)*5/2 = -5 — matching both samples. O(1) time, no loop needed even though the constraint (|N| ≤ 10000) would have made a direct loop fast enough too.