Problem A. Alternating digits ≡

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

Statement

Let us call a string of digits d1 d2… dk alternating 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 P L — position and length of alternating substring.

Constraints

Input string consists of 1 to 30000 digits.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
7777
1 1
2
01234567802345
2 13

Problem B. Bureaucracy generator ≡

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

Statement

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:

1. 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).
2. Each manager's immediate subordinates must be either all managers (who in turn have their own subordinates), or all developers.
3. Each developer and manager has exactly one immediate superior manager, except a single highest level manager called Project Leader, who has none.
4. 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 S N, 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 si ci, 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.

Constraints

1 ≤ S, ai, ci ≤ 100, 1 ≤ N ≤ 10

Sample tests

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

Problem C. Cosmonaut ≡

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

Statement

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:

xc yc zc — coordinates of torus center,

xd yd zd — 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,

x y z — coordinates of the point in space.

Output file format

Output file must contain real numbers xm ym zm — 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

106 xc, 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.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
0 0 0
0 0 1
10 1
1 0 0
9.0 0.0 0.0
2
5 6 7 1 1 1 50 10 3 2 1
32.5203582126019 5.16103228678696 -22.1982936390279

Problem D. Distinct colors ≡

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

Statement

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 N K D followed by N triplets ri gi bi, representing initial colors.

Output file format

Output file must contain K triplets rj gj bj, 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

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 1 10
255 100 100
100 100 255
110 110 110
2
2 1 200
255 100 100
100 100 255
-1

Problem E. Enormous spiral ≡

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

Statement

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 N K S followed by N integers ai, and then by K coordinates xi yi.

Output file format

Output file must contain K numbers — cell counts for each window.

Constraints

2 ≤ ai ≤ 109, ai1 < ai+1, 1 ≤ N ≤ 106, 109 ≤ xi, yi ≤ 109, 1 ≤ K ≤ 10000, 1 ≤ S ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1 1 10
100
0 0
10
2
2 1 10
100 1000
1 -1
0
3
4 3 3
4 3 6 4
-1 0
0 0
1 0
5 6 7

Problem F. Frogless swamp ≡

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

Statement

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 integers Y M N, followed by N pairs of integers xi yi — 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.

Constraints

1 ≤ N ≤ 100, 1 ≤ Y, M ≤ 1000, 0 ≤ xi, yi ≤ 1000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
13 7 6
13 3
13 5
9 7
7 7
3 8
2 9
20.595
2
20 16 1
100 10
-1

Problem G. Going to be a programmer? ≡

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

Statement

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.

Constraints

1 ≤ N ≤ 100, 0 ≤ R ≤ N, 106 ≤ ai ≤ 106.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
10 20 30
2
﻿>
15
2
3
1 1 1
2
?

Problem H. Hot-keys ≡

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

Statement

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.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
yes
no
cancel
&yes
&no
&cancel
2
4
abc
bca
acb
aaaa
&amp;abc
&amp;bca
a&amp;cb
aaaa

0.149s 0.004s 35