Author:  A. Klenin  
Input file:  input.txt  Time limit:  2 sec  
Output file:  output.txt  Memory limit:  16 Mb 
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:
Your task is, given the list of N runs with submission time and result of each run, compute the rank table for C teams.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  4 sec  
Output file:  output.txt  Memory limit:  16 Mb 
The Unknown Trading Company have installed a new inventorytracking 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 twodimensional 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.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  8 sec  
Output file:  output.txt  Memory limit:  2 Mb 
The pseudorandom 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 nth 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_{0} = 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_{0}, find such two elements R_{i} < R_{j} that:
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  B. Vasilyev, A. Klenin  
Input file:  input.txt  Time limit:  5 sec  
Output file:  output.txt  Memory limit:  4 Mb 
Radio station 'ACM Rock' is broadcasting over the circular area with center in point (x_{0}, y_{0}) 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 ith 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_{0}  x_{i})^{2} + (y_{0}  y_{i})^{2} ≤ R^{2}.
Your task is to select a subset of sites for relay stations so that:
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  3 sec  
Output file:  output.txt  Memory limit:  4 Mb 
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})^{2} + (y − y_{c})^{2} ≤ R^{2}
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.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  5 sec  
Output file:  output.txt  Memory limit:  16 Mb 
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 wellknown: 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.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 

