Problem A. Age recognition

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

Statement

A software development company named "Adnor" is starting a new challenging project: a video analytic application capable of classifying some features of people from images of their faces. One of such features is the age of the person. Since the problem of precise age recognition is still open and very difficult, for now the company will solve a slightly easier one: the system must determine an age interval to which the owner of presented face belongs.

Age interval is defined by minimum and maximum age, for example:

Interval nameLower boundUpper bound
Young118
Adult1955
Senior56100

Most modern automatic classification methods are comprised of two steps: learning from a set of training samples, and classification itself.

For the training set, "Adnor" company has a database of face images with the exact age of each presented person. The training set is split into subsets according to desired age intervals and fed to the learning algorithm.

Sales division determined that the classifier should be able to distinguish between M age intervals. There is some freedom in choosing interval bounds, but for the optimal recognition quality training subset sizes should not differ too much. Strictly speaking, an entropy, measured in nats of sizes of these subsets should not be less than some constant E. Here entropy is defined as:

− (1 / S) × siln(si / S), where si is a subset size, and S — the sum of all subset sizes.

If this condition is not satisfied, some images should be excluded from one or more subsets to make their sizes closer and hence rise the entropy. Still, the training data should not be wasted, so some splitting must be found which uses as many samples as possible while having an entropy above or equal to E. Your task is to write a program which would find such an optimal splitting.

Input file format

Input file contains integers N M — maximum age in face images database and number of age intervals, followed by floating point number E — the lowest acceptable entropy value.

Following are N integers a1.. aN, where ai is the number of available samples for age of i years.

It is guaranteed that at least one solution exists.

Output file format

Output file should contain M triplets of integer numbers li ri si, each one corresponding to one age interval. li is lower age bound, ri is upper age bound and si is the number of samples that should be used in the training subset for the ith interval. Intervals should be sorted in ascending order of their lower bounds. They should not overlap and must have nonempty training subsets (si > 0). If there is more than one solution, output any of them.

Constraints

1 ≤ N ≤ 100; 1 ≤ M ≤ 10; 0 ≤ ai ≤ 10; 0 ≤ E ≤ 100;

There are no more than 50 non-zero values of ai.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
10 2 0.1
5 8 4 4 3 8 9 5 3 4
1 5 24
6 10 29
2
10 2 0.693
5 8 4 4 3 8 9 5 3 4
1 5 24
6 10 24

Problem B. Boustrophedon

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

Statement

Boustrophedon is a type of bi-directional text, mostly seen in ancient manuscripts and other inscriptions.

Every other line of writing is reversed. Rather than going left-to-right as in modern English, alternate lines in boustrophedon must be read in opposite directions. The individual character images on reversed lines are mirrored too.

Notice that some Latin letters are symmetrical, and so do not need mirroring on the reversed lines. This way, some English texts may be written as boustrophedons with the standard font. The symmetrical letters are: A, H, I, M, O, T, U, V, W, X, Y.

The boustrophedon must consist of at least 3 lines. All lines of the boustrophedon must have the same number of characters (let us call it the width of the boustrophedon), except the last line, which may be shorter. The text contains only capital English letters (no spacing or punctuation).

You program must find the width of the widest boustrophedon that can be constructed from the given text and does not need letter mirroring.

Input file format

Input file contains a single string composed of capital Latin letters.

Output file format

Output file must contain a single integer — maximum boustrophedon width. If there is no solution, output zero.

Constraints

String length is between 1 and 100000 characters.

Sample tests

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

Problem C. Calendar of aliens

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

Statement

Human spaceship has discovered an abandoned alien vessel in the interstellar space. Aboard the vessel, various recordings were found and xeno-archeologists have started to decipher them.

First, they were able to recognize numerals and convert them to the human notation. The next step is converting dates.

Alien dates are apparently measured in 4 units (as opposed to 3 human units — years, months and days). Also, unlike the human one, alien calendar is regular — for each unit, its ratio to the next one is whole and fixed. The problem is to find those ratios.

One of records seemed to be an astronomical log, describing and dating various notable cosmic events. Scientists were able to identify some of the events, and determine the corresponding dates. Surprisingly, the smallest unit of the alien calendar happened to be exactly equal to one Earth day.

Your program must, given the list of alien and corresponding human dates, determine all possible sets of unit ratios for the alien calendar.

All human dates are correct. You may assume that the ratios are in the range from 2 to 100.

The human calendar have 12 months, containing 31, 28 or 29, 31, 30, 31, 30, 31, 31, 30, 31, 30 and 31 days. The second month has 29 days if the year is either divisible by 400 or divisible by 4 and not divisible by 100.

Input file format

Input file contains an integer N — the number of dates, followed by N groups of 7 numbers each: ui vu wi ti di mi yi. In the group, ui vu wi ti are numbers comprising i-th alien date, in order from the smallest to the largest unit, di mi yi are day, month and year of the same date in the human calendar.

Output file format

Output file must contain an integer M — number of possible calendars.

Constraints

1 ≤ N ≤ 10;

1 ≤ ui, vi, wi ≤ 100;

1 ≤ ti ≤ 10000;

1 ≤ di ≤ 31;

1 ≤ mi ≤ 12;

1600 ≤ yi < 10000;

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
1 2 3 4  5 10 1901
2 2 3 4  6 10 1901
1 3 3 4  6 11 1901
1 3 4 4  1 03 1903
97

Problem D. Depression

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

Statement

The height map of some square country is represented with a matrix of N × N integers. Each integer reflects average height of the corresponding area. We will denote the height value at location (x, y) as h[x, y].

A location (x, y) is named depression if for all x' = xW… x+W, y' = yW… y+W location (x', y') is also inside of the map and h[x, y] ≤ h[x',y'].

Your program must find coordinates of all depressions of the given height map.

Input file format

Input file contains integers N W, followed by N × N integers — location heights, row-by-row.

Output file format

Output file must contain an integer M — number of possible depressions, followed by M pairs of integers xi yi, where xi — the column of the i-th depression, yi — the row of the i-th depression. Numbering starts from 1.

Depressions must be ordered by y, then by x.

Constraints

3 ≤ N ≤ 500

1 ≤ W

2 × W < N

1 ≤ h[x, y] ≤ 1000

Sample tests

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

Problem E. Elliptical devastation

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

Statement

Spaceship Behemoth was sent to conquer the Gamma Pisces star system.

System has N planets numbered from 1 to N. The planets may be considered stationary and located on one plane. Every planet is guarded by a military space station, with the orbit in the same plane.

Some of these stations rotate around their planets clockwise, others — counterclockwise. Station orbits are ellipses. They can intersect, but cannot touch. No orbit lies entirely inside of another.

Spaceship is so huge and strong that it can easily destroy any object it encounters. Too bad, but to make it so powerful, engineers had to limit its navigational and maneuvering capabilities. It can either orbit a planet on the same orbit as one of the stations or very rapidly accelerate and decelerate to jump from one orbit to another one. The trajectory of such jump is a straight line tangent to both source and destination orbits.

To destroy a space station the ship must enter its orbit with the rotation direction opposite to that of the station. If it encounters the station while on the orbit, the station will be immediately smashed to pieces. If it has to depart an orbit before reaching its prey, it leaves a nuclear proximity mine, which will finish the business for sure.

After the destruction, the orbit of the former station gets polluted by much debris dangerous even for our mighty ship. It still can safely travel across these already visited orbits, but cannot take them for later maneuvers.

Your program must plan an assault on Gamma Pisces, which will result in destruction of all of its military stations. Behemoth will emerge from the subspace on orbit of Gamma Pisces Prime (planet number 1) and start its mission there.

Input file format

Input file contains integer N — the number of planets, followed by N orbit descriptions. Each description consists of 5 integers x1 y1 x2 y2 c d, where (x1, y1) and (x2, y2) specify coordinates of ellipse foci, c is the length of semi-major axis and d equals 1 if station rotates clockwise and 1 if counterclockwise.

Output file format

Output file must contain N integers — planet numbers in order of visiting. If several solutions exist, output lexicographically minimal one. If the solution does not exist, output a single integer 1.

Constraints

1 ≤ N ≤ 10; 106 ≤ x1, y1, x2, y2, c ≤ 106

Sample tests

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

Problem F. Fireworks

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

Statement

You task is to display a firework in ASCII graphics. A firework consists of one or more explosions called breaks. Each break has an integer radius R and a level L and is displayed by '*' (ASCII 42) character at the center and 8 rays: 4 horizontal ('-', ASCII 45) and vertical ('|', ASCII 124) rays, each R + E characters long (where E is an additional parameter equal for all breaks); 4 diagonal ('/', ASCII 47 and '\', ASCII 92) rays, each R characters long. If the level of the break is greater then 1, at the end of each horizontal and vertical ray a new "child" break of radius R − 1 and level L − 1 is located. Child break has only 7 rays, because the ray in the direction leading to the "parent" break is not drawn. A firework starts from a single break. It must be output as a square of characters, having minimal size sufficient to display all the breaks. Characters not belonging to any break must be output as '.' (ASCII 46). Characters belonging to more than one break must be output as 'x' (ASCII 120).

Input file format

Input file contains integers L R E — level and radius of the initial break and the additional horizontal/vertical rays length.

Output file format

Output file must contain display of a firework.

Constraints

1 ≤ L ≤ R ≤ 10, 1 ≤ E ≤ 20

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1 1 1
..|..
.\|/.
--*--
./|\.
..|..
2
2 4 1
..........|..........
.......\..|../.......
........\.|./........
.........\|/.........
......----*----......
........./|\.........
....|.\./.|.\./.|....
.\..|..x..|..x..|../.
..\.|./.\.|./.\.|./..
...\|/...\|/...\|/...
----*-----*-----*----
.../|\.../|\.../|\...
../.|.\./.|.\./.|.\..
./..|..x..|..x..|..\.
....|./.\.|./.\.|....
.........\|/.........
......----*----......
........./|\.........
......../.|.\........
......./..|..\.......
..........|..........

Problem G. Giant snake

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

Statement

Let us consider a snake consisting of L squares 1 × 1 meter in size, chained one after another by sides.

There is a labyrinth of N × M cells. Each cell is 2 × 2 meters in size. Some cells are occupied by walls, others are empty.

Your task is to lay out the snake in the labyrinth without intersections with itself and walls, or determine that it is impossible.

Input file format

First line of input file contains three integers N M L. Following N lines consist of M characters each, describing the labyrinth. Free cells are denoted by '.' (ASCII 46). Walls are denoted by '#' (ASCII 35).

Output file format

First line of output file must contain string YES if it is possible to lay out the snake and NO otherwise.

If the layout exists, the following L lines must contain positions of snake squares, listed in order they compose the snake. Each position is described by two integers ri ci, where ri is the distance from the top edge of the labyrinth to the top edge of the i-th square, (so 0 ≤ ri < 2 N), and ci is the distance form the left edge of the labyrinth to the left edge of the i-th square, (so 0 ≤ ci < 2 M).

If there is more than one layout, output any of them.

Constraints

1 ≤ N, M ≤ 50; 1 ≤ L ≤ 10000;

Sample tests

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

Problem H. How many iterations?

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

Statement

Young programmer Vasya is learning the beginnings of the algorithm complexity theory. For starters, he wants to be able to quickly estimate the number of iterations of nested loops. As a first example, he wrote the following code:

CPascal
long long f(int n)
{
   long long ans = 0;
   for (int i = 1; i <= n; i++) 
      for (int j = i+1; j <= n; j++)
         for (int k = j+1; k <= n; k++)
            ans++;
   return ans;
}
function f(n: integer): int64;
var i, j, k: integer;
begin
   result := 0;
   for i := 1 to n do 
      for j := i+1 to n do 
         for k := j+1 to n do
            inc(result);
end;

Using your knowledge of the subject, help Vasya calculate f(n) for given n.

Input file format

Input file contains an integer n.

Output file format

Output file must contain a single integer — f(n).

Constraints

1 ≤ n ≤ 106

Sample tests

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

Problem I. Innovations

Author:A. Klenin, I. Tuphanov
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb

Statement

Once upon a time in a galaxy far, far away there was a planet with an extensive government of N officials. Some officials were subordinates of others.

The main task of the government were to implement innovations. Each innovation was implemented in the following way: first, the innovation, along with some budget, is assigned to one of the officials. The official takes some of the budget and reassigns the innovation to one of his subordinates. This process repeats until innovation reaches the official without subordinates, who takes the remaining budget. At this point, innovation is declared to be implemented.

The government considers the innovation to be optimally implemented if every official is involved in the implementation.

Your program must, given the superior-subordinate relationships, find an order in which officials should be involved in the optimal implementation of the innovation.

Input file format

Input file contains integers N M, followed by M pairs of integers ui vi. Each pair designates that the official number vi is subordinate of the official number ui (1 ≤ ui, vi ≤ N, ui ≠ vi).

It is guaranteed that there are no cycles in the superior-subordinate relationship.

Output file format

Output file must contain N integers — numbers of officials in the order they should process the innovation. If there is no solution, output single number 0. If there is more that one solution, output any of them.

Constraints

2 ≤ N ≤ 103; 1 ≤ M ≤ 105

Sample tests

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

0.103s 0.009s 27