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. Sales Report ≡

Statement

The Unknown Trading Company have installed a new inventory-tracking system, which stores a complete database of goods and trading points worldwide. Each salespoint and each item was assigned an integer unique identifier (id). For every sale, the system logs id of the item, number of items sold, and id of the salespoint.

Your task is to output a summary report, tabulating total sales by items and salespoints. The report must be a two-dimensional table, with the first row containing item ids in increasing order, first column containing salespoint ids in increasing order, and values inside the table representing total sales of corresponding item from the corresponding salespoint. The value in first column of the first row must be −1. The values in cells without corresponding sales must be 0.

Input file format

Output file format

Constraints

Sample tests

4
10 1 3
20 2 5
10 2 2
20 2 1

-1 10 20
1 3 0
2 2 6

1
1 1 5

-1 1
1 5

Problem C. Random Gap ≡

Statement

The pseudo-random number genegators (or RNGs for short) are widely used in statistical calculations. One of the simplest and ubiquitious is the linear congruence RNG, that calculates the n-th random number R_n as R_n = (aR_{n - 1} + c) mod m, where a, c and m are constants. For example, the sequence for a = 15, c = 7, m = 100 and starting value R₀ = 1 is 1, 22, 37, 62, 37, 62, ...

Linear RNG is very fast, and can yield surprisinly good sequence of random numbers, given the right choice of constants. There are various measures of RNG quality, and your task is to calculate one of them, namely the longest gap between members of the sequence. More precisely, given the values of a, c, m, and R₀, find such two elements R_i < R_j that:

1. there are no other R_k R_i ≤ R_k ≤ R_j,
2. the difference R_j − R_i is maximal.

Input file format

Output file format

Constraints

Sample tests

15 7 100 1

25

2 0 127 5

26

Problem D. Radio Coverage ≡

Statement

Radio station 'ACM Rock' is broadcasting over the circular area with center in point (x₀, y₀) and radius R. In order to increase the auditorium, it were suggested to build several relay stations. N locations were selected as candidate sites for relay stations. Relay station placed in i-th location will cover a circular area with center in point (x_i, y_i) and radius r_i, where center lies inside the area covered by the base station, (x₀ - x_i)² + (y₀ - y_i)² ≤ R².

Your task is to select a subset of sites for relay stations so that:

1. the covered areas for relays do not intersect (but may touch) one another,
2. the total area covered by base station and all relays is maximum possible.

Input file format

Output file format

Constraints

Sample tests

1 0 0 10
10 0 10

505.4816

Problem E. Circle Drawing ≡

Statement

Graphics libraries usually implement drawing of graphics primitives, like lines, polygons and circles. Your task is to write a program that draws circles.

Graphic canvas is represented as an array of X_size by Y_size pixels. Each pixel have a color ranged from 0 to 9. Initially all pixels have color 0. Pixels are thought of as small sqares with the side of length 1. A circle with center (x_c, y_c) and radius R is a set of pixels (x, y) satisfying the inequality (x − x_c)² + (y − y_c)² ≤ R²

To draw a circle, your program should set the color of all pixels in a set defined above to the color of the circle. After drawing N given circles, the program should output the color of all pixels of the canvas.

Input file format

Output file format

Constraints

Sample tests

5 5 1
2 2 1 3

00000
00300
03330
00300
00000

4 3 2
2 2 2 5
0 1 1 9

9050
9955
9555

Problem F. Harder Sokoban Problem ≡

Statement

The game of sokoban is played in a rectangular labirinth of N by N cells with each cell either empty, denoted by '.' character (ASCII 46), or occupied by wall, denoted by '#' character (ASCII 35). There is also a single destination cell, denoted by '*' character (ASCII 42).

One player and one container are located in the empty cells of the labirinth. The player can move between the empty cells in horizontal or vertical direction. If the cell where the player tries to move is occupied by container, the container is "pushed" to the next cell in the same direction. That next cell must, of course, be empty.

The objective of the game is well-known: to place the container in the destination cell with the minimum number of moves. Your task, however, is different: given the field, select starting position for the player and the container so as to maximize the required number of moves.

Input file format

Output file format

Constraints

Sample tests

2
..
.*

0

3
..#
...
..*

10