All-Ukrainian Olympiad in Informatics

A data-compression algorithm ("block-sort" compression) applies the following transform to a block of data. A string P is a rotation of a string S if it is obtained by a cyclic shift of S's characters: if S = a1 a2 ... aN, then P = ap ap+1 ... aN a1 ... ap-1 for some 1 ≤ p ≤ N. Build an N×N table M whose rows are all N rotations of S, sorted in lexicographic order. Let L be the last column of M.

The forward transform takes S and produces L together with K, the row number of M that contains S itself (if S appears more than once among the rotations, any one occurrence's row number is acceptable). This is exactly the Burrows–Wheeler transform. Program ABRAKA must perform the inverse transform: given L and K, recover the original string S.

The first line of ABRAKA.DAT contains two integers K and N (1 ≤ N ≤ 30000, 1 ≤ K ≤ N). The second line contains the N characters of L — lowercase Latin letters.

The single line of ABRAKA.SOL must contain the string S.

• 1 ≤ N ≤ 30000
• 1 ≤ K ≤ N
• L consists only of lowercase Latin letters

Input (ABRAKA.DAT):
2 6
karaab

Output (ABRAKA.SOL):
abraka

For S = "abraka", the sorted rotation table M has S itself on row 2, and its last column reads L = "karaab" — so decoding (K=2, L="karaab") must recover "abraka".

Let A be an array of N elements A1, ..., AN, with maximum max(A) and minimum min(A). Let S be the sum of its elements. The Confuse operation replaces every element with the difference between S and that element: Ai := S - Ai for all i (computed from the original, pre-replacement sum and values).

Array B is the result of applying Confuse K times in a row to some original array A. Program CONFUSE must compute max(A) - min(A) given only B and K — without ever reconstructing A itself.

The first line of CONFUSE.DAT contains integers N and K, where N is the number of elements of B (2 ≤ N ≤ 10000) and K is the number of times Confuse was applied to the original array (1 ≤ K ≤ 100). The second line contains the N elements of B, integers in [-2 000 000 000, 2 000 000 000].

The single line of CONFUSE.SOL must contain the integer max(A) - min(A).

• 2 ≤ N ≤ 10000
• 1 ≤ K ≤ 100
• elements fit in the range ±2×10^9

Input (CONFUSE.DAT):
4 2
45 52 47 46

Output (CONFUSE.SOL):
7

N players, numbered 1 to N, play a round-robin tournament: every pair plays exactly one game, which always has a winner (no draws). At the end of the tournament, a player is said to take place P if exactly P - 1 players beat them and they beat everyone else, and every player who beat them also beat everyone they themselves beat. For any other player, a final place cannot be meaningfully assigned.

Program CONTEST is given N and the results of the games played so far (the tournament is still in progress). It must count how many players are guaranteed to end up without a determinable final place, no matter how the remaining, not-yet-played games turn out.

The first line of CONTEST.DAT contains two natural numbers: N, the number of players (1 ≤ N ≤ 100), and M, the number of games played so far. Each of the next M lines gives one played game as two numbers: the winner's number, then the loser's number.

The single line of CONTEST.SOL must contain the number of players whose final place cannot be determined.

• 1 ≤ N ≤ 100
• 0 ≤ M ≤ N(N-1)/2

Input (CONTEST.DAT):
6 8
1 5
1 4
5 2
5 6
3 2
2 6
6 4
4 3

Output (CONTEST.SOL):
4

A 3D figure is built out of unit cubes stacked on an integer grid. From the figure you can derive its frontal projection and its right-side projection — each a 2D silhouette showing, for every position, whether at least one cube casts a shadow there. Two projections do not, in general, uniquely determine the figure that produced them.

Program CUBES is given the frontal and right-side projections of some figure and must compute the minimum and the maximum number of unit cubes that a figure with exactly those two projections could be built from.

The first line of CUBES.DAT contains three integers N, M, K, the dimensions of the projections (1 ≤ N, M, K ≤ 100). Two projections follow, frontal first, then right-side. A projection is given as N lines of 0s and 1s separated by spaces — M values per line for the frontal projection, K values per line for the right-side projection. 0 marks an empty cell of the projection, 1 a filled one.

The single line of CUBES.SOL must contain two numbers: the minimum and the maximum possible cube count.

• 1 ≤ N, M, K ≤ 100

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

Output (CUBES.SOL):
4 7

A sequence of positive integers is written in binary around the rim of a circular dial, one after another, digit after digit — no number is zero, and each starts with a 1 bit; a binary number has at most 25 digits, and the whole dial has at most 100 digits in total. The dial can be cut into sectors by drawing lines between digits — a cut line may fall between two numbers, or in the middle of a number, in which case that number is split into two (or more) separate numbers, one per side of the cut. Each sector's sum is the sum of the (whole or split) numbers that fall inside it.

Program DIAL must count how many different ways the dial can be cut into sectors so that every sector has the same sum.

The single line of DIAL.DAT contains the sequence of numbers, written in binary and separated by spaces (each number possibly consisting of several binary digits, all concatenated around the circular dial).

The single line of DIAL.SOL must contain a natural number — the number of sector partitions with equal sector sums.

• each number is nonzero and starts with a 1 bit
• each number has at most 25 binary digits
• the dial has at most 100 digits in total

Input (DIAL.DAT):
101 1 1101

Output (DIAL.SOL):
9

The three numbers concatenate into the circular digit string 10111101 (8 digits). Nine distinct ways of drawing cut lines around this circle produce sectors whose (possibly split-number) sums all agree.

The plane holds a set of N simple polygons with the following guarantee: no two polygons share a point, and for every polygon i there are exactly Pi polygons that contain it and N - 1 - Pi polygons that it contains (0 ≤ Pi ≤ N - 1). In other words, every pair of polygons is related by strict containment — the whole set forms a single nested chain, like Russian dolls, rather than a scatter of side-by-side shapes.

Program POLYGON must output, for each polygon, the number of polygons that contain it.

The first line of POLYGON.DAT contains N, the number of polygons (3 ≤ N ≤ 10000). Each of the next N lines describes one polygon: an integer Ci, the number of vertices (3 ≤ Ci ≤ 20), followed by Ci pairs of integer coordinates in traversal order. Coordinates lie in [-2 000 000 000, 2 000 000 000].

The single line of POLYGON.SOL must contain N numbers, the i-th being Pi, the number of polygons that contain the i-th polygon.

• 3 ≤ N ≤ 10000
• 3 ≤ Ci ≤ 20 per polygon

Input (POLYGON.DAT):
3
3 -2 1 8 9 12 1
4 9 -1 9 4 2 4 2 -1
3 18 -3 5 8 -6 -3

Output (POLYGON.SOL):
2 1 0

The first polygon is nested two levels deep, the second one level deep, and the third is the outermost shape.

A rectangular board has N rows and M columns. A token standing on a cell of some column can move, in one step, to one of a fixed list of cells in the next column (the allowed destinations for each cell are given). The token may never revisit a cell it has already stood on, across the entire game — not just within the current left-to-right pass.

At the start, the token is placed on any cell of column 1, and moves rightward until it either reaches the last column or has nowhere legal left to go. Each time it reaches the last column, it is placed again on any not-yet-visited cell of column 1 and set moving again. The game ends when the token cannot make a move.

Program WAYS must compute the largest possible number of complete passes from column 1 to column M that a sequence of restarts can achieve.

The first line of WAYS.DAT contains N and M (1 ≤ N ≤ 50, 2 ≤ M ≤ 10). It is followed by M - 1 blocks of N lines each, one block per column boundary: line i of block j describes the possible moves from the cell in row i of column j — first the count of possible destinations, then that many row numbers in column j + 1, listed in increasing order without repeats.

The single line of WAYS.SOL must contain the maximum number of complete column-1-to-column-M passes (0 if no cell of column 1 can even reach column M).

• 1 ≤ N ≤ 50
• 2 ≤ M ≤ 10

Input (WAYS.DAT):
4 3
2 1 3
3 1 2 4
0
2 2 3
1 2
1 2
1 3
2 2 4

Output (WAYS.SOL):
3

Three full passes are achievable, e.g. via the routes (1→3→3), (2→4→4) and (4→2→2).