All-Ukrainian Olympiad in Informatics — Finals

There are K kinds of substances and N kinds of alchemical reactions. Each reaction consumes a fixed set of input substances and produces a fixed set of output substances, taking a fixed amount of time to complete. Any substance obtained from a reaction can be extracted in pure form and used freely — there's always enough of any substance for any use, and a substance produced by one reaction can immediately feed another. Reactions may run simultaneously.

Write a program ALCHEMY that, given the substances and reactions, finds the minimum time needed to obtain a target substance.

The first line of input file ALCHEMY.DAT contains four integers: K (3 ≤ K ≤ 250) — the number of substances, N (3 ≤ N ≤ 500) — the number of reactions, M (1 ≤ M < K) — the number of substances available at the start, and the number of the target substance. N blocks follow, each describing one reaction in three lines: the time the reaction takes, then the count and list of input substances, then the count and list of output substances. Substances available from the start are numbered 1..M; all others are numbered M+1..K. The sum of all reaction times does not exceed 2·10⁹.

The single line of output file ALCHEMY.SOL must contain the minimum time in which the target substance can be obtained, or −1 if it cannot be obtained at all.

• 3 ≤ K ≤ 250, 3 ≤ N ≤ 500, 1 ≤ M < K
• sum of all reaction times ≤ 2·10⁹

Input (ALCHEMY.DAT):
4 3 1 4
8
1 1
1 4
3
1 1
2 2 3
2
2 1 3
1 4

Output (ALCHEMY.SOL):
5

Substance 4 is obtained by running reaction 2 for the first 3 time units, then reaction 3 for 2 more — 5 units of time in total.

A gaming die sits in the top-left corner of a rectangular N×M board, in a fixed starting orientation: face 1 points forward and face 2 points left. Board cells are squares matching the die's face size. The die can roll onto an adjacent cell — up, down, left, or right — by tipping over one of its edges, but it can never leave the board; some cells are blocked and may never be visited.

Write a program CASINO that finds a path for the die from the top-left corner to the bottom-right corner such that the value on the die's top face, once it arrives, is as large as possible. The die may revisit any cell any number of times.

The first line of input file CASINO.DAT contains two integers N and M (2 ≤ N, M ≤ 50) — the board's height and width. N further lines of M numbers each (0 or 1) describe the board; a 1 marks a cell the die may never visit, a 0 marks a cell it may pass through. The starting cell is always 0.

The first line of output file CASINO.SOL must contain W, the length of the found path, followed by W lines each giving the row and column of the board cell visited at that step. If no path exists, the output file must contain a single line with -1.

• 2 ≤ N, M ≤ 50
• board cells are 0 (passable) or 1 (blocked); the start cell is always 0

Input (CASINO.DAT):
3 2
0 1
0 0
0 0

Output (CASINO.SOL):
3
2 1
2 2
3 2

There are N pieces of chain, the i-th made of Lᵢ links. Any link can be unbent and later bent shut again, joining separate pieces together.

Write a program CHAIN that, given the number of pieces N and their link counts Lᵢ, finds the minimum number of links that must be unbent and rebent to join all the pieces into a single chain. The final chain must have no branches — every link must connect to exactly two others, except the two end links, which connect to only one.

The first line of input file CHAIN.DAT contains an integer N (2 ≤ N ≤ 10 000). The second line contains N integers Lᵢ (1 ≤ Lᵢ ≤ 1 000 000 000).

The single line of output file CHAIN.SOL must contain the minimum number of links that need to be unbent and rebent to join all the pieces into one chain.

• 2 ≤ N ≤ 10 000
• 1 ≤ Lᵢ ≤ 1 000 000 000

Input (CHAIN.DAT):
3
100 3 4

Output (CHAIN.SOL):
2

A small but proud mouse has decided to eat every berry on a cherry tree. The tree's branches fork and never grow back together; from the point where a branch ends, either more branches begin, or a certain number of berries grow. Crawling one meter along a branch costs the mouse one unit of its reserve of nutrients (RN); eating a berry restores one unit of RN. If the reserve ever goes negative, the mouse dies. Movement always starts and ends at the base of branch 1, the trunk.

Write a program CHERRY that, given the tree, finds the minimum starting reserve of RN the mouse needs to eat every berry and return to the ground, never letting its reserve go negative along the way.

The first line of input file CHERRY.DAT contains an integer N (1 ≤ N ≤ 100) — the number of branches. N further lines describe the tree, one per branch: the (i+1)-th line gives branch i's length L (1 ≤ L ≤ 30 000), then the number K of branches that continue from its far end, then K branch numbers; if K is zero, a third number gives the count of berries V (0 ≤ V ≤ 30 000) growing at that branch's end instead.

The single line of output file CHERRY.SOL must contain the minimum RN reserve needed.

• 1 ≤ N ≤ 100
• 1 ≤ L ≤ 30 000, 0 ≤ V ≤ 30 000

Input (CHERRY.DAT):
8
5 3 6 5 7
5 0 10
9 0 1
4 0 19
11 0 50
5 2 2 4
3 2 8 3
4 0 0

Output (CHERRY.SOL):
15

Consider a system of N equations, where the k-th equation has the form X + Y = bₖ, with X = x₁ₖ + x₂ₖ + … + x_{k-1,k} and Y = x_{k,k+1} + … + x_{k,N}. Each equation's left-hand side therefore has N−1 terms, and every unknown xᵢⱼ appears in exactly two equations of the system.

Write a program SYSTEM that, given b₁, …, b_N, finds one solution of the system, under the condition that every unknown xᵢⱼ may only take the value 0 or 1.

The first line of input file SYSTEM.DAT contains the number of test blocks. Each block starts with a line containing N (3 ≤ N ≤ 50) — the number of equations — followed by a line with N integers bᵢ (0 ≤ bᵢ ≤ 50).

For each test block, output file SYSTEM.SOL must contain one solution of the system: N−1 lines, the k-th containing the N−k found values of x_{k,k+1} … x_{k,N}. If a test block's system has no solution, a single line containing -1 must be written instead.

• 3 ≤ N ≤ 50
• 0 ≤ bᵢ ≤ 50

Input (SYSTEM.DAT):
2
3
1 2 3
5
3 2 3 2 2

Output (SYSTEM.SOL):
-1
1 1 1 0
0 0 1
1 1
0

The first test block (N=3, b = 1 2 3) has no valid solution. The second (N=5, b = 3 2 3 2 2) is solved by the given assignment of the xᵢⱼ.

The territory of the Great Triangular Oblast (ВТО) is shaped like a right triangle whose legs measure M and N state length units. The government wants to cover as much of the territory as possible with square 1×1 tiles, packed tightly against each other and against the two legs, with no cutting — a tile counts only if it fits entirely inside the triangle, never crossing the hypotenuse. Tiles are delivered only in full containers of P tiles each, and the government orders exactly as many containers as the project needs.

Write a program TRIANGLE that finds how many tiles are left over in the last container once the paving is done.

The single line of input file TRIANGLE.DAT contains three integers: M, N (2 ≤ M, N ≤ 2 000 000 000) and P (100 ≤ P ≤ 10 000).

The single line of output file TRIANGLE.SOL must contain one integer — the number of unused tiles left over from the last container.

• 2 ≤ M, N ≤ 2 000 000 000
• 100 ≤ P ≤ 10 000

Input (TRIANGLE.DAT):
4 3 100

Output (TRIANGLE.SOL):
97

Three tiles fit under the hypotenuse of the 4×3 right triangle, so one container of 100 is ordered and 97 tiles come back unused.