Oleksiy PylypenkoOlympiad Years

Kyiv City Olympiad in Informatics

Stage III, Kyiv 2002 · February 2002

Diploma III (Σ 24)24 ptsDiploma III

Tied for 8th of the grade-10 field; 'Місце' in this protocol marks diploma tier, not exact placement.

A second appearance at the Kyiv city stage, this time as a 10th-grader and one year deeper into UPML's training — the same six-problem, single-day format as the year before, but with a noticeably harder problem set: a Reuleaux-triangle animation, an integer polynomial factorization, a resistor network solved with Kirchhoff's laws worth 31 of the 100 available points on its own.

Σ = 24 this time, built mainly from a near-complete solve of the recurrence- sequence problem (8/12) plus partial credit on three others, for a Diploma III. It landed in a cluster of contestants scoring 24-26 points, one tier below UPML's own Bohdan Yakovenko, who topped the grade-10 protocol outright with 34. It was a smaller result than the year before by score, but it came against a harder set and inside a field UPML itself was now dominating the top of.

ContestantSchoolGradeΣDiploma
Bohdan YakovenkoUPML1034I
Serhiy DashevskyiSchool 1711026III
Oleksandr ChubarievPL Solomianskyi1026III
Oleksiy PylypenkoUPML1024III
Anton KharkivSchool 1711024III
Yevhen SlyusarSchool 1451021—
Grade-10 protocol, city (stage III) olympiad, 2002 — top row plus the field around the UPML entry. — Official results spreadsheet (kievoi.ippo.kubg.edu.ua)

Problems

Problems from this contest

Checker Moves on a Cube Surface

Шашка на кубі

graphsdpcombinatorics

Statement

A cube's surface is divided, by lines parallel to its edges, into square cells whose side is 1/l of the cube's edge length (l an odd natural number). A checker moves, one move at a time, to a cell orthogonally adjacent to its current one (sharing a full side). Write draught.* to compute the number of distinct m-move paths the checker can take from the cell at the center of one face to the cell at the center of an adjacent face.

Input / Output

File draught.dat holds natural numbers l and m (l < 52, m < 200). File draught.res holds the number of distinct paths.

Constraints

  • l < 52
  • m < 200

Example

l = 3, m = 3 gives 1 path.

Solution idea

Treat the cube's surface grid cells as nodes of a graph, with edges between orthogonally adjacent cells — including across the folds between adjacent faces — and count walks of length m between the two fixed start and end cells by dynamic programming: propagate a "number of ways to be here after i moves" count over all 6l² cells for i = 1..m. Since l < 52 the whole surface has under roughly 16000 cells, so an O(m × l²) DP comfortably fits the given bounds.

Common Element of Arithmetic Progressions

Спільний елемент

number-theorycrtmath

Statement

Write common.* that finds the smallest natural number that simultaneously belongs to n given infinite arithmetic progressions of natural numbers.

Input / Output

File common.dat holds 2n + 1 non-negative integers: n, followed by n pairs — the first term and the common difference of each progression. File common.res holds the answer, or 0 if no such number exists.

Constraints

  • every input number does not exceed 10000
  • n < 100

Example

For n = 3 with progressions (1, 2), (4, 2), (5, 20), the answer is 25.

Solution idea

This is a system of simultaneous congruences x ≡ first_i (mod diff_i). Merge the progressions pairwise using the generalized Chinese Remainder Theorem: two congruences are compatible only if gcd(d1, d2) divides the difference of their first terms (found via the extended Euclidean algorithm), and when compatible they combine into a single progression with difference lcm(d1, d2). Fold all n progressions into one this way and report its smallest non-negative term, or 0 the moment any pairwise merge turns out to be inconsistent.

Integer Polynomial Factorization

Множники

mathnumber-theorypolynomials

Statement

Write factor.* that factors an integer-coefficient polynomial into integer-coefficient factors that can no longer be split into integer-coefficient linear (binomial) factors.

Input / Output

File factor.dat holds the degree n followed by n + 1 integer coefficients, from the leading term down to the constant term. File factor.res: line 1 holds the sign of the leading coefficient and the GCD of all coefficients; each following line describes one linear factor found — its multiplicity, its degree (always 1), and its coefficients with a positive leading coefficient — ordered by non-decreasing leading coefficient, then by increasing degree, then by the sign of the constant term; a final line, if present, holds the leftover factor that is not a binomial (the quotient left after dividing out every linear factor found, with its multiplicity).

Constraints

  • n < 100
  • coefficients fit in 4 bytes (no bignum arithmetic is required)
  • every number written to factor.res has at most 2 digits

Example

The degree-7 polynomial 7x⁷ − 84x⁶ + 84x⁵ − 133x⁴ + 196x³ − 140x² + 77x − 35 factors, per the worked sample, into a constant factor −7 together with several repeated linear binomial factors (see the source statement for the full worked breakdown).

Solution idea

Use the rational root theorem: every rational root p/q (in lowest terms) of an integer polynomial has p dividing the constant term and q dividing the leading coefficient. Enumerate the resulting candidate roots, test each by evaluation, and repeatedly divide out any linear factor (qx − p) found (by synthetic division) until no more rational linear factors remain — the 2-digit output bound keeps the candidate set small enough to search directly — leaving one final non-linear remainder factor, if any.

Recursively Defined Sequence

Послідовність

recursionbignummath

Statement

A table gives the first 18 terms of an integer sequence a_n. Every later term is defined by one of seven recurrence identities, each expressing a term at an index of the form 9n + r (for a fixed remainder r in {0, 1, 2, 4, 5, 7, 8}) as a linear combination of a_{3n+2} and a_{3n+1}. Write sequence.* that computes a_n for a given index n.

Input / Output

File sequence.dat contains a single natural number n, with up to 100 decimal digits. File sequence.res must contain a_n.

Constraints

n may have up to 100 decimal digits, so a_n must be computed without ever materializing n as a small machine integer.

Example

a_2 = 15, taken directly from the given table of the first 18 terms.

Solution idea

If n ≤ 18, look the answer up directly in the table. Otherwise, since every recurrence identity is stated in terms of n mod 9, work out which of the seven residue classes the given index falls into, derive the smaller indices 3n+2 and 3n+1 needed on the right-hand side, and recurse on those. Each recursive step divides the effective index by roughly 9, so the recursion has only logarithmic depth even though n itself may have up to 100 digits — which is what makes the problem tractable with bignum arithmetic.

Resistor Network

Опір

graphsphysicslinear-algebra

Statement

n numbered terminals of an electrical circuit are connected by m resistors, each with a non-negative rational resistance in ohms. Write resistor.* to determine the resistance between terminals 1 and n.

Input / Output

File resistor.dat holds n and m (both between 1 and 2500), followed by m quadruples of non-negative integers: two terminal numbers and the numerator and denominator of the resistance connecting them. File resistor.res holds a single line with the answer as an irreducible fraction (the denominator is omitted when it equals 1), or the text Zero conductivity if no chain of resistors connects terminals 1 and n.

Constraints

  • 1 ≤ n, m ≤ 2500
  • solving the circuit never requires more than 50 simultaneous linear equation variables

Example

For 3 terminals with resistors 1–2: 2Ω, 2–3: 7Ω, 2–3: 6Ω, the resistance between terminals 1 and 3 is 168/13 Ω.

Solution idea

Apply Kirchhoff's laws directly: inject a unit current at terminal 1 and extract it at terminal n, write (n − 2) node-current-balance equations (one per terminal other than the two endpoints) and enough independent-loop voltage equations to cover every resistor at least once, then solve the resulting linear system for the branch currents (proportional to the injected EMF) and read off the equivalent resistance as EMF divided by the total current through the source. Equivalently, repeatedly collapse the network with series/parallel combination and star–mesh (Y–Δ) transforms until a single equivalent resistor between terminals 1 and n remains, treating any zero-resistance short circuit and any disconnected terminal pair as the two special-case outputs.

Reuleaux Triangle Animation

Трикутник Рело

graphicsgeometrysimulation

Statement

Write figure.* that draws a Reuleaux triangle — a convex shape bounded by three 60° arcs of circles of equal radius a — and animates its rotation.

Input / Output

The program reads, from the keyboard, in order, a single-digit natural number k and a real number t (0.1 ≤ t ≤ 10). It draws, full-screen on a black background, a yellow Reuleaux triangle inscribed in a light-blue square of side a, with one vertex of the triangle at the midpoint of the square's top side, and a red circle of radius a/10 centered at the point equidistant from the Reuleaux triangle's three vertices. After Enter is pressed, the figure redraws every t seconds, rotating the Reuleaux triangle counter-clockwise by 30°/k per frame while it stays inside the fixed square (the red circle's center keeps tracking the rotating triangle's centroid). Any key press stops the program.

Constraints

  • k is a single decimal digit, 1 ≤ k ≤ 9
  • 0.1 ≤ t ≤ 10

Example

With k = 2, t = 1, the triangle rotates 15° once per second.

Solution idea

Precompute the Reuleaux triangle's three vertices and its centroid relative to the enclosing square once. Each animation frame simply rotates those points by a further 30°/k about the centroid, redraws the triangle and the tracking red circle, and waits t seconds (or for a key press) before the next frame — no state beyond "current rotation angle" is needed between frames.

Sources

  1. [1]Official results spreadsheet (kievoi.ippo.kubg.edu.ua)
  2. [2]Stage III problem set (kievoi.ippo.kubg.edu.ua)