Problem A. ACM Rank Table ≡

Statement

ACM contests, like the one you are participating in, are hosted by the special software. That software, among other functions, preforms a job of accepting and evaluating teams' solutions (runs), and displaying results in a rank table. The scoring rules are as follows:

1. Each run is either accepted or rejected.
2. The problem is considered solved by the team, if one of the runs submitted for it is accepted.
3. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submission of the first accepted run for this problem (in minutes) plus 20 minutes for every other run for this problem before the accepted one. For an unsolved problem consumed time is not computed.
4. The total time is the sum of the time consumed for each problem solved.
5. Teams are ranked according to the number of solved problems. Teams that solve the same number of problems are ranked by the least total time.
6. While the time shown is in minutes, the actual time is measured to the precision of 1 second, and the the seconds are taken into account when ranking teams.
7. Teams with equal rank according to the above rules must be sorted by increasing team number.

Your task is, given the list of N runs with submission time and result of each run, compute the rank table for C teams.

Input file format

Output file format

Constraints

Sample tests

2 3
1 1 5000 0
1 1 500 1
2 1 10000 1

1 2

3 3
1 2 3000 0
1 2 3100 1
2 1 4200 1

2 1 3

Problem B. Sudoku Checker ≡

Statement

The puzzle game of Sudoku is played on a board of N² × N² cells. The cells are grouped in N × N squares of N × N cells each. Each cell is either empty or contains a number between 1 and N².

The sudoku position is correct when numbers in each row, each column and each square are different. The goal of the game is, starting from some correct position, fill all empty cells so that the final position is still correct.

This game is fairly popular in the Internet, and there are many sites which allow visitors to solve puzzles online. Such sites always have a subroutine to determine a correctness of a given position.

You are to write such a routine.

Input file format

Output file format

Constraints

Sample tests

2
0 0 0 0
0 0 0 0
0 0 2 0
0 0 0 1

CORRECT

2
2 1 3 0
3 2 4 0
1 3 2 4
0 0 0 1

INCORRECT

Problem C. Texture Tile ≡

Statement

Square raster image is represented by an array of N × N pixels. A texture tile is a square image in which the first row is equal to the last one, and the first column is equal to the last one. This property is valuable when covering the surface of graphics object with repeating copies of texture, because it allows "seamless" transitions between tiles.

Your program must, given an image, find its largest subimage which is a texture tile.

Input file format

Output file format

Constraints

Sample tests

2
0 0
2 3

1 1 1

4
1 0 0 0
1 2 5 2
1 0 0 0
4 4 4 4

1 2 3

Problem D. Customer support ≡

Statement

Customer support department in an "Incomprehension Amateurs, Ltd" software company has call center for answering users' questions. Support prices are as follows:

So, for example, if user asks the same question three times, first receives incorrect answer, then correct one, and the third time correct answer with explanation, it will cost him 10 + 20 + (40 + 1 * 10) = 80 USD.

Customers are billed monthly according to call log. Company engineers review the log and for each question determine:

1. unique number, so the equivalent questions have same numbers,
2. whether the answer was correct,
3. whether the answer was short or included detailed enough explanation.

Input file format

Output file format

Constraints

Sample tests

1
9834 0 1

10

3
33 1 0
33 0 0
33 1 1

80

Problem E. Ecology tax ≡

Statement

In a big and rich on natural resources country, the government started a campaign to control deforestation. In fact the government is not too interested in how many trees get fallen, but rather how effectively the wood is utilized. So a law was passed which requires every logging company to pay amount of money in proportion to amount of wood that it wastes during operation.

A felling quota on some territory was allotted to a company in this country. Company lorries may only transport logs of exactly L meters long. So when a tree gets sawed into logs, the remainder is wasted.

Trees in this country grow exactly 1 meter per year, so the company may decrease the amount of tax to be paid by simply waiting for some years. Your task is to determine the number of years needed to achieve smallest possible tax. If there is more than one answer, find minimal (earliest) one.

Input file format

Output file format

Constraints

Sample tests

3 1 
10 15 11

0

3 2
5 3 6

1

Problem F. Alternating digits ≡

Statement

Let us call a string of digits d₁ d₂… d_k alternating string if the digits on even and odd positions form two disjoint sets.

For example, 121212 and 01234567 are alternating strings, while 11 and 5435 are not.

Your program must, given the string of digits, find its longest continuous alternating substring. If there is more than one longest substring, output the leftmost one.

Input file format

Output file format

Constraints

Sample tests

7777

1 1

01234567802345

2 13

Problem G. Distinct colors ≡

Statement

Colors on computer screen are represented by (r, g, b) triplets, where r, g, b are integer intensities of red, green and blue components.

Two colors (r₁, g₁, b₁) and (r₂, g₂, b₂) are distinct if min(|r₁ − r₂|, |g₁ − g₂|, |b₁ − b₂|) ≥ D.

Your program will be given N (not necessarily distinct) colors. It must either calculate K new colors that are distinct from each other and from all initial colors, or determine that it is impossible.

Input file format

Output file format

Constraints

Sample tests

2 1 10
255 100 100
100 100 255

110 110 110

2 1 200
255 100 100
100 100 255

-1

Problem H. Going to be a programmer? ≡

Statement

Igor is a computer science freshman student. As opposed to most of his classmates, he actually knows a little about computer programming. Because of this, other students often ask him to write their homework assignments for the "Introductory Programming" course.

He noticed that, although each assignment is unique, they usually follow a simple pattern. In particular, one assignment states:

"Count the number of integers in the array which are [greater than|less than|equal to|not equal to] [value]",

where parts in brackets differ from student to student. Assignments also contain sample input and output to encourage students to test their programs before submission.

Igor have many classmates, so to save time he decided to write a homework generator. He started with the following template:

  count := 0;
  for i := 1 to N do
    if a[i] #cond# #value# then
      Inc(count);

Your program will be given sample input -- an array of N integer values, and the corresponding output R. It must find such substitution strings for #cond# and #value# that after execution of the code snippet above count will be equal to R, or determine that it is impossible.

Input file format

Output file format

The first line of output must contain one of the strings '<', '>', '=', '<>' -- substitution for #cond#. The second line must contain an integer -- substitution for #value#.

If there is no solution, output file must contain a single character '?' (ASCII 63). If there is more then one solution, output any of them.

Constraints

Sample tests

3
10 20 30
2

>
15

3
1 1 1
2

?

Problem I. Nearest number - 2 ≡

Statement

Input is the matrix A of N by N non-negative integers.

A distance between two elements A_i j and A_p q is defined as |i − p| + |j − q|.

Your program must replace each zero element in the matrix with the nearest non-zero one. If there are two or more nearest non-zeroes, the zero must be left in place.

Input file format

Output file format

Constraints

Sample tests

3
0 0 0
1 0 2
0 3 0

1 0 2
1 0 2
0 3 0