Author:  T. Chistyakov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  2 Mb 
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), A_{1}, A_{2}, …, A_{L × 7} — quantity of pizzas to be delivered for each day of the period (A_{i} ≥ 0).
Once an absentminded 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 contains the following integer numbers:
N — number of fulfilled orders in the delivery history w_{1} d_{1} q_{1} w_{2} d_{2} q_{2}… w_{N} d_{N} q_{N} — 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, zeroquantity orders were fulfilled.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin, T. Chistyakov  
Input file:  input.txt  Time limit:  2 sec  
Output file:  output.txt  Memory limit:  256 Mb 
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.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  B. Vasilyev, A. Klenin  
Input file:  input.txt  Time limit:  3 sec  
Output file:  output.txt  Memory limit:  64 Mb 
Given a set of points with integer coordinates x_{i}, y_{i}, i = 1… N, your program must find all the squares having each of four vertices in one of these points.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin, T. Chistyakov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  2 Mb 
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.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin, T. Chistyakov  
Input file:  input.txt  Time limit:  3 sec  
Output file:  output.txt  Memory limit:  256 Mb 
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:
Your program must output the state of the terrarium after T seconds.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  2 sec  
Output file:  output.txt  Memory limit:  64 Mb 
The puzzle game of Sudoku is played on a board of N^{2} × N^{2} 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^{2}.
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.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  T. Chistyakov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  2 Mb 
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 halffinished 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 halffinished 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.
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.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 

