Problem A. ACM Rank Table

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

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

Input contains integer numbers C N, followed by N quartets of integes ci pi ti ri, where ci -- team number, pi -- problem number, ti -- submission time in seconds, ri -- 1, if the run was accepted, 0 otherwise.

Output file format

Output file must contain C integers -- team numbers sorted by rank.

Constraints

1 ≤ C, N ≤ 1000, 1 ≤ ciC, 1 ≤ pi ≤ 20, 1 ≤ ti ≤ 36000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 3
1 1 5000 0
1 1 500 1
2 1 10000 1
1 2
2
3 3
1 2 3000 0
1 2 3100 1
2 1 4200 1
2 1 3

Problem B. Sudoku Checker

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

The puzzle game of Sudoku is played on a board of N2 × N2 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 N2.

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

Input file contains integer N, followed by N4 integers -- sudoku position. Empty cells are denoted by zeroes.

Output file format

Output file must contain a single string 'CORRECT' or 'INCORRECT'.

Constraints

1 ≤ N ≤ 10.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2
0 0 0 0
0 0 0 0
0 0 2 0
0 0 0 1
CORRECT
2
2
2 1 3 0
3 2 4 0
1 3 2 4
0 0 0 1
INCORRECT

Problem C. Texture Tile

Author:A. Klenin, T. Chistyakov   Time limit:2 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

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

Input file contains integer N followed by N2 numbers ci, j -- pixel values.

Output file format

Output file must contain numbers p q m -- coordinates of top left corner and size of the largest texture tile. If several solutions exist, output any of them.

Constraints

1 ≤ N ≤ 370, 0 ≤ ci, j ≤ 255.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2
0 0
2 3
1 1 1
2
4
1 0 0 0
1 2 5 2
1 0 0 0
4 4 4 4
1 2 3

Problem D. Customer support

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

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

1.Answer to a question10 USD
2.Correct answer to a question20 USD
3.Correct answer to a question with explanation40 USD
4. Correct answer to a question which was already correctly answered before +10 USD for each previous correct answer

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.
Given that data, your program must calculate the payment amount.

Input file format

Input file contains number of calls N followed by N triples qi ai xi, where qi is integer question number, ai = 1 if the answer was correct, 0 otherwise, xi = 1 if explanation was given, 0 otherwise.

Output file format

Output file must contain a single number -- payment amount.

Constraints

1 ≤ N ≤ 10000, 1 ≤ qi ≤ 106.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
9834 0 1
10
2
3
33 1 0
33 0 0
33 1 1
80

Problem E. Ecology tax

Author:I. Ludov   Time limit:1 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

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

Input file contains number of trees N, length of log L, followed by integers i1 i2… iN -- heights of each tree.

Output file format

Output file must contain single integer -- number of years to wait.

Constraints

1 ≤ N ≤ 30000, 1 ≤ L, ik ≤ 30000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 1 
10 15 11
0
2
3 2
5 3 6
1

Problem F. Alternating digits

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

Let us call a string of digits d1 d2… dk 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

Input file contains single string of digits.

Output file format

Output file must contain integers P L -- position and length of alternating substring.

Constraints

Input string consists of 1 to 30000 digits.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
7777
1 1
2
01234567802345
2 13

Problem G. Distinct colors

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

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 (r1, g1, b1) and (r2, g2, b2) are distinct if min(|r1 − r2|, |g1 − g2|, |b1 − b2|) ≥ 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

Input file contains numbers N K D followed by N triplets ri gi bi, representing initial colors.

Output file format

Output file must contain K triplets rj gj bj, representing resulting distinct colors. If there is no solution, output must contain a single number 1. If there is more than one solution, output any of them.

Constraints

0 ≤ ri, gi, bi ≤ 255 for both input and output colors,

0 ≤ N ≤ 256, 1 ≤ D, K ≤ 256

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 1 10
255 100 100
100 100 255
110 110 110
2
2 1 200
255 100 100
100 100 255
-1

Problem H. Going to be a programmer?

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

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);

And now he wants to substitute #cond# and #value# based on the sample input from the assignment. Of course, generated program might be different from what was required in the assignment, but at least it would pass the sample test -- his classmates are grateful to have even that. Do you know enough Introductory Programming to help Igor?

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

Input file contains integer N followed by N integers ai and then by integer R.

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

1 ≤ N ≤ 100, 0 ≤ R ≤ N, 106 ≤ ai ≤ 106.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
10 20 30
2
>
15
2
3
1 1 1
2
?

Problem I. Nearest number - 2

Author:A. Klenin   Time limit:5 sec
Input file:input.txt   Memory limit:200 Mb
Output file:output.txt  

Statement

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

A distance between two elements Ai j and Ap q is defined as |ip| + |jq|.

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

Input file contains the number N followed by N2 integers, representing the matrix row-by-row.

Output file format

Output file must contain N2 integers, representing the modified matrix row-by-row.

Constraints

1 ≤ N ≤ 200, 0 ≤ Ai ≤ 1000000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
0 0 0
1 0 2
0 3 0
1 0 2
1 0 2
0 3 0

0.145s 0.008s 29