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 name
Lower bound
Upper bound
Young
1
18
Adult
19
55
Senior
56
100
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 NM — 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 lirisi, 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;
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.
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: uivuwitidimiyi. In the group,
uivuwiti are numbers comprising i-th alien date,
in order from the smallest to the largest unit, dimiyi 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.
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' = x−W… x+W, y' = y−W… 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 NW, 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 xiyi, where
xi — the column of the i-th depression,
yi — the row of the i-th depression.
Numbering starts from 1.
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 x1y1x2y2cd,
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.
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 LRE — level and radius of the initial break
and the additional horizontal/vertical rays length.
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 NML.
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 rici, where
ri is the distance from the top edge of the labyrinth to the top edge of the i-th square,
(so 0 ≤ ri < 2N),
and ci is the distance form the left edge of the labyrinth to the left edge of the i-th square,
(so 0 ≤ ci < 2M).
If there is more than one layout, output any of them.
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:
C
Pascal
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.
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 NM, followed by
M pairs of integers uivi.
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.
Let us consider a snake consisting of