Let us call a string of digits d1d2… dkalternating string if
the digits on even and odd positions form two disjoint sets.
For example, 121212 and 01234567 are alternating strings,
while 11 and 5435 are not.
Your program must, given the string of digits,
find its longest continuous alternating substring.
If there is more than one longest substring, output the leftmost one.
Input file format
Input file contains single string of digits.
Output file format
Output file must contain integers PL —
position and length of alternating substring.
A large software company has started a new high-budget project —
the game console platform called "Y-Sphere".
The company is proud of its sophisticated development process standards,
and has recently received a prestigious CMM (Capacity for Managers Maximization)
certificate.
Using those powerful standards, it was easily calculated
that the project will need precisely S developers.
Now the only problem is how to manage them efficiently.
Fortunately, CMM process has the answer: of course a proper management
hierarchy is needed, that can be built by following few simple rules:
Each manager has managerial capacity —
number of immediate subordinates he can control.
He must be assigned to manage neither more (too difficult for him),
nor less (not efficient enough).
Each manager's immediate subordinates must be either
all managers (who in turn have their own subordinates),
or all developers.
Each developer and manager has exactly one immediate superior manager,
except a single highest level manager called Project Leader, who has none.
Each manager must have capacity strictly lower then his immediate superior
(so that more qualified managers take higher positions in hierarchy).
The company has managers of N different capacities.
It has unlimited number of managers of each capacity.
Your program must plan a proper management hierarchy or determine that it is impossible.
Input file format
Input contains two integers SN, followed by N different integers ai —
available managerial capacities.
Output file format
Output must contain integer M — total count of required managers,
who are numbered from 1 to M.
Next must be M pairs of integers sici, where
si is the number of i-th manager's immediate superior (or zero for Project Leader),
ci is capacity of i-th manager, taken from the list of available capacities.
If the there is no solution, output a single number −1.
If there is more than one solution, output any of them.
In the year 2030 International Space Station 2 was launched.
It had a torus shape to enable artificial gravity generation.
(A torus is a circular tube with circular cross-section).
Advanced spacesuit technology and micro-rocket engines
allowed for prolonged and easy spacewalks.
During one such spacewalk a crew member was looking at the station from an open space
and wondered where should he fly to get to the station surface as fast as possible.
Since he was cosmonaut and not astronaut, he had good mathematics education.
So after a return to the station he quickly wrote a program which constructed
the shortest line from any given point in space to the surface of a given torus.
Can you do this too?
Input file format
Input file contains eleven integer numbers: xcyczc — coordinates of torus center, xdydzd — a vector collinear to torus symmetry axis, r1 — distance from the center of the tube to the center of the torus, r2 — radius of the tube, xyz — coordinates of the point in space.
Output file format
Output file must contain real numbers xmymzm —
coordinates of the nearest torus point
with at least 15 correct digits after decimal point.
If there is more than one nearest point, output any of them.
Constraints
−106xc, yc, zc, xd, yd, zd, x, y, z ≤ 106, 0 < r2 < r1 ≤ 106, |xd| + |yd| + |zd| > 0,
point (x, y, z) lies either outside the torus or on its surface.
Colors on computer screen are represented by (r, g, b) triplets,
where r, g, b are integer intensities of red, green and blue components.
Two colors (r1, g1, b1) and (r2, g2, b2) are distinct
if min(|r1 − r2|, |g1 − g2|, |b1 − b2|) ≥ D.
Your program will be given N (not necessarily distinct) colors.
It must either calculate K new colors that are
distinct from each other and from all initial colors,
or determine that it is impossible.
Input file format
Input file contains numbers NKD followed by N triplets rigibi,
representing initial colors.
Output file format
Output file must contain K triplets rjgjbj, representing resulting
distinct colors.
If there is no solution, output must contain a single number −1.
If there is more than one solution, output any of them.
Constraints
0 ≤ ri, gi, bi ≤ 255 for both input and output colors, 0 ≤ N ≤ 256, 1 ≤ D, K ≤ 256
Consider an infinite plane divided into square cells with the side of 1.
The spiral starts at cell (0, 0) and consists of N straight segments.
First segment runs from the starting cell in the direction of x axis,
each following segment takes a 90° turn to the right.
Segment number i contains exactly ai cells.
Segments do not overlap except at joint cells,
which are treated as belonging to both adjacent segments.
A square window on the plane consists of S × S cells
and is defined by coordinates of top left cell (x, y)
(y axis is directed upwards).
Your program will be given coordinates of K square windows,
and must determine, for each window, the number of cells inside it
belonging to the spiral.
For example, a spiral below is defined by input of sample test 3.
Cells marked with 'x' are inside the first window from the same test.
x
x
x
x
x
x
x
x
x
Input file format
Input file contains numbers NKS followed by N integers ai,
and then by K coordinates xiyi.
Output file format
Output file must contain K numbers — cell counts for each window.
Constraints
2 ≤ ai ≤ 109, ai−1 < ai+1, 1 ≤ N ≤ 106,
−109 ≤ xi, yi ≤ 109, 1 ≤ K ≤ 10000, 1 ≤ S ≤ 100
As is customary, Ivan has shot an arrow to hit a potential bride.
He did not know the local swamp was not inhabited by frogs —
neither regular nor princess ones.
Anyway, the arrow did not fall into the swamp,
but flew over to the other side.
To retrieve it Ivan has to cross the swamp.
The swamp is a strip of width Y stretching indefinitely both to the east and to the west.
Ivan stands at the southern border of the swamp, and wants to get to the northern border.
Ivan has a map showing N hummocks capable of holding his weight.
Hummocks are too far from each other to jump,
so Ivan has found a plank of length M to use as a bridge.
Hummocks are also too slippery to stand on, so Ivan decided to
break a plank in two parts (of lengths L and M − L)
and use them to move in the following way:
he would stand on first part, throw the second part over to the nearby hummock,
step onto the second part, pick up the first part,
walk with it across the second one. Repeating this procedure as necessary,
Ivan hopes to reach the other side of the swamp as fast as possible.
Ivan can choose any value of L such that 0 < L < M.
Important condition is that Ivan must always stand on the plank.
He can, however, put both parts of the plank between the same two hummocks and/or
use the parts in any order he wants (for example,
put part 1 between hummocks A and B, move to hummock B,
put part 2 between hummocks B and C, step onto part 2 staying at hummock B,
pick part 1 and put it between B and D, move to hummock D taking part 2 with him).
Your program will be given the swamp width, plank length and hummocks coordinates.
It must calculate the shortest distance Ivan has to walk to cross the swamp
or determine that he can not do so.
Distance is measured from hummock to hummock, even if plank part is longer
than the distance between hummocks.
Input file format
Input contains integersYMN,
followed by N pairs of integersxiyi — hummock coordinates.
The swamp edge Ivan stands on coincides with y = 0 line,
and the opposite edge — with y = Y line.
Output file format
Output must contain a single floating point number — the shortest
distance Ivan has to travel with at least 3 correct decimal digits.
If there is no solution, output must contain the number −1.
An image below illustrates a solution to the first sample.
Igor is a computer science freshman student.
As opposed to most of his classmates,
he actually knows a little about computer programming.
Because of this, other students often ask him to write their homework
assignments for the "Introductory Programming" course.
He noticed that, although each assignment is unique,
they usually follow a simple pattern.
In particular, one assignment states:
"Count the number of integers in the array which are
[greater than|less than|equal to|not equal to] [value]",
where parts in brackets differ from student to student.
Assignments also contain sample input and output to
encourage students to test their programs before submission.
Igor have many classmates, so to save time
he decided to write a homework generator.
He started with the following template:
count := 0;
for i := 1 to N do
if a[i] #cond# #value# then
Inc(count);
And now he wants to substitute #cond# and #value#
based on the sample input from the assignment.
Of course, generated program might be different from what was required
in the assignment, but at least it would pass the sample test —
his classmates are grateful to have even that.
Do you know enough Introductory Programming to help Igor?
Your program will be given sample input — an array of N integer values,
and the corresponding output R.
It must find such substitution strings for
#cond# and #value# that
after execution of the code snippet above count will be equal to R,
or determine that it is impossible.
Input file format
Input file contains integer N followed by N integers ai
and then by integer R.
Output file format
The first line of output must contain one of the
strings '<', '>', '=', '<>' — substitution for #cond#.
The second line must contain an integer — substitution for #value#.
If there is no solution,
output file must contain a single character '?' (ASCII 63).
If there is more then one solution, output any of them.
When designing dialog forms for interactive programs, it is important
to assign hot-keys (known also as accelerator keys) to each
dialog element, so as to facilitate keyboard input.
For better mnemonics, hot-keys are assigned based on the letters
of dialog elements' captions,
usually favoring letters near the beginning of caption.
Manual hot-keys distribution can be tedious and error-prone,
as one must be careful not to assign same letter to different elements.
Your program will be given a list of captions.
It must assign unique hot-keys to as many captions of possible.
Each assigned hot-key must be a letter from the corresponding caption.
For each hot-key, position is the leftmost occurrence of the hot-key letter
in the corresponding caption.
From all solutions with the same numbers of hot-keys,
your program must choose the one with minimal sum of hot-key positions.
If there is still more than one optimal solution, output any of them.
Input file format
Input file contains number of captions N followed by N lines with captions.
Output file format
Output file must contain N lines with the same captions as in input.
In those captions which have hot-key assigned, leftmost occurrence
of hot-key letter must be preceded with '&' (ASCII 38).
Constraints
1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and
consist of small Latin letters.
Advanced spacesuit technology and micro-rocket engines
allowed for prolonged and easy spacewalks.
Input file contains eleven integer numbers:
