## Problem A. Pizza schedule ≡

 Author: T. Chistyakov Input file: input.txt Time limit: 1 sec Output file: output.txt Memory limit: 2 Mb

### Statement

PizzaSocks company makes and delivers pizza. Pizza is delivered on regular schedule. A schedule has a period of 1, 2, 3 or 4 weeks. Quantity of pizzas to be delivered is known for each day of the period. First day of a period is always the first day of the week.

So formally pizza delivery schedule can be described by the following numbers: L — length of the schedule period (from 1 to 4), A1, A2, …, AL × 7 — quantity of pizzas to be delivered for each day of the period (Ai ≥ 0).

Once an absent-minded PizzaSocks manager lost a schedule for one Very Big and Important Client. Only the history of past deliveries was preserved. Your task is to restore the schedule from the history.

The problem is complicated by the fact that occasionally Very Big and Important Client changed his orders, ordering either more or less pizzas than scheduled, even sometimes cancelling the order competely or placing an unscheduled order.

So it's often impossible to restore the original schedule exactly. That is why your task is to find an optimal schedule, i. e. to minimize the total number of days when historically ordered quantity is different from the quantity according to that schedule. The days before the first recorded order and after the last recorded one should not be taken into consideration.

### Input file format

Input file contains the following integer numbers:

N — number of fulfilled orders in the delivery history w1 d1 q1 w2 d2 q2… wN dN qN — description of historical orders: week number, day of the week, and quantity of pizzas delivered. For each day there is no more than one record. It's considered that on those days that are not explicitly mentioned in the input file, but fall between the earliest and the latest mentioned days, zero-quantity orders were fulfilled.

### Output file format

Output periodicity of the optimal schedule — integer number L from 1 to 4. Then output numbers Ai for each i from 1 to L × 7. If several solutions exist, output any of them. However, make sure that the first week of your schedule corresponds to the earliest week mentioned in the input file.

### Constraints

1 ≤ qi ≤ 100, 1 ≤ wi ≤ 52, 1 ≤ di ≤ 7

### Sample tests

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

## Problem B. Texture Tile ≡

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

### 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 C. Count Squares ≡

 Author: B. Vasilyev, A. Klenin Input file: input.txt Time limit: 3 sec Output file: output.txt Memory limit: 64 Mb

### Statement

Given a set of points with integer coordinates xi, yi, i = 1… N, your program must find all the squares having each of four vertices in one of these points.

### Input file format

Input file contains integer N followed by N pairs of integers xi yi.

### Output file format

Output file must contain a single integer — number of squares found.

### Constraints

104 ≤ xi, yi ≤ 104, 1 ≤ N ≤ 2000. All points in the input are different.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 0 0 4 3 -3 4 1 7
1
2
9
1 1  1 2  1 3
2 1  2 2  2 3
3 1  3 2  3 3
6

## Problem D. Road Accident ≡

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

### Statement

Two cars crashed on the road, receiving some damage each, and raising the usual question: "Who to blame?". To answer this, it is essential to thoroughly reconstruct the sequence of events. By gathering witness testimonies and analyzing tire tracks, positions and speeds of cars just before the impact were determined. From these positions until the crash the cars moved straight forward.

Your program must, given the available data, calculate for each car what part of it first came into contact with the other car. Parts are numbered as shown on the picture.

### Input file format

Input file contains twelve floating point numbers: x1 y1 u1 v1 w1 s1 x2 y2 u2 v2 w2 s2, where (x, y) and (u, v) — coordinates of back-left and forward-left corners of the car, w — width of the car, s — speed of the car.

### Output file format

Output file must contain two integers: p1 p2, where p — number of part which first contacted the other one (if two parts came into contact simultaneously, output the lesser of the part numbers),

### Constraints

1 ≤ xi, yi, ui, vi, wi ≤ 106, 0 ≤ si ≤ 106. Input data is such that a crash certainly happens. Initially cars don't have common points.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1.0 2.0 10.0 2.0 1.0 10.0
50.0 1.0 40.0 1.0 1.0 20.0
2 2
2
1 1 10 1 1 20
40 1 50 1 1 10
2 1

## Problem E. Terrarium ≡

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

### Statement

A zoology research lab has a terrarium with rare species of snakes. Terrarium is a flat box filled with soil, and has a glass top allowing to watch the snakes. There are trenches in the soil, and snakes constantly move along the trenches. All snakes have diameter of 1 cm and integer length of no less than 2 cm.

While watching the snakes, the zoologists discovered a pattern in their movement: each snake moves at a speed of 1 cm per second forward, until it encounters either a wall or another snake. Faced an obstacle, snake first tries to turn right, if there is also obstacle on the right, then it tries to turn left. If there is obstacle on the left also, the snake waits for a second before trying to move again.

In order to validate the discovery, it was decided to write a program that simulates snakes' behaviour. This task was assigned to you.

The terrarium is represented by an array of N × N characters. Each character is one of:

• '.' (ASCII 46) — trench
• '#' (ASCII 35) — wall
• 'A' to 'Z' — snake's head
• 'a' to 'z' — snake's body or tip of the tail
Snakes are represented by latin letters, so there are no more than 26 snakes in terrarium. Snakes try to move in alphabetical order every second.

Your program must output the state of the terrarium after T seconds.

### Input file format

First line of input file contains integers N T. Following N lines contain N characters each — the initial state of the terrarium. The input file guarantees unambiguous recognition of snakes — all snakes are continuous, every character of snake's body has exactly two neighbour characters belonging to the same snake, while head and tip of the tail have exactly one.

### Output file format

Output file must contain N lines of N characters — the state of the terrarium after T seconds.

### Constraints

2 ≤ N ≤ 1000, 1 ≤ T ≤ 106.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 8
.bB.
....
a.#.
aaA.
.baa
.BAa
..#.
....
2
7 100000
aA.....
a#####D
aa....d
......d
......d
......d
.......
aaaaADd
.#####d
......d
......d
.......
.......
.......

## Problem F. Sudoku Checker ≡

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

### 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'.

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 G. ACM Computer Factory ≡

 Author: T. Chistyakov Input file: input.txt Time limit: 1 sec Output file: output.txt Memory limit: 2 Mb

### Statement

As you know, all the computers used for ACM contests must be identical, so the participants compete on equal terms. That is why all these computers are historically produced at the same factory.

Every ACM computer consists of P parts. When all these parts are present, the computer is ready and can be shipped to one of the numerous ACM contests.

Computer manufacturing is fully automated by using N various machines. Each machine removes some parts from a half-finished computer and adds some new parts (removing of parts is sometimes necessary as the parts cannot be added to a computer in arbitrary order). Each machine is described by its performance (measured in computers per hour), input and output specification.

Input specification describes which parts must be present in a half-finished computer for the machine to be able to operate on it. The specification is a set of P numbers 0, 1 or 2 (one number for each part), where 0 means that corresponding part must not be present, 1 — the part is required, 2 — presence of the part doesn't matter.

Output specification describes the result of the operation, and is a set of P numbers 0 or 1, where 0 means that the part is absent, 1 — the part is present.

The machines are connected by very fast production lines so that delivery time is negligibly small compared to production time.

After many years of operation the overall performance of the ACM Computer Factory became insufficient for satisfying the growing contest needs. That is why ACM directorate decided to upgrade the factory.

As different machines were installed in different time periods, they were often not optimally connected to the existing factory machines. It was noted that the easiest way to upgrade the factory is to rearrange production lines. ACM directorate decided to entrust you with solving this problem.

### Input file format

Input file contains integers P N, then N descriptions of the machines. The description of ith machine is represented as by 2 P + 1 integers Qi Si,1 Si,2… Si,P Di,1 Di,2… Di,P, where Qi specifies performance, Si, j — input specification for part j, Di, k — output specification for part k.

### Output file format

Output the maximum possible overall performance, then M — number of connections that must be made, then M descriptions of the connections. Each connection between machines A and B must be described by three positive numbers A B W, where W is the number of computers delivered from A to B per hour.

If several solutions exist, output any of them.

### Constraints

1 ≤ P ≤ 10, 1 ≤ N ≤ 50, 1 ≤ Qi ≤ 10000

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 4
15  0 0 0  0 1 0
10  0 0 0  0 1 1
30  0 1 2  1 1 1
3   0 2 1  1 1 1
25 2
1 3 15
2 3 10
2
3 5
5   0 0 0  0 1 0
100 0 1 0  1 0 1
3   0 1 0  1 1 0
1   1 0 1  1 1 0
300 1 1 2  1 1 1
4 5
1 3 3
3 5 3
1 2 1
2 4 1
4 5 1
3
2 2
100  0 0  1 0
200  0 1  1 1
0 0

0.081s 0.004s 21