Problem A. Altitude and visibility ≡

Statement

Consider a sequence of numbers a₁, …, a_N, representing heights. Let's say that element a_i has a visibility radius d if a_i ≥ a_j for all j such that 1 ≤ j ≤ N and |i − j| < d.

You task is to find maximum d_i for every a_i.

Input file format

Input file contains integer N followed by N integers a_i.

Output file format

Output file must contain N integers d_i — maximum visibility for every a_i. If maximum visibility radius for element a_i is unlimited, output d_i = 0.

Constraints

1 ≤ N ≤ 10⁶, 0 ≤ a_i ≤ 10⁹

Sample tests

1
10

0 

6
1 5 2 2 1 4

1 0 1 2 1 4 

Problem B. Blanks ≡

Statement

Young programmer Vasya works for a local government.

His first job is to automate filling of paper forms. A form is represented by a single string consisting of Latin letters, spaces and underscores ('_', ASCII 95). Substrings of underscores (known as fields) represent blank spaces left for an applicant to fill. Under each field the paper form has a small caption explaining to the applicant what data he should put over those underscores. For example:

My name is ________
             name

You program must, given the representation of a form and a value for each field caption, put corresponding value into every form field.

When filling a field with a value, additional rules must be observed:

1. First and last character of the field must remain underscores.
2. Total field length must not change. If a value is longer than a field, it must be truncated on the right. If a value is shorter than a field, it must be aligned to the left.

Input file format

First line of input file contains a string representing the form. Second line contains field captions. Third line contains an integer N — number of different captions. Following 2 × N lines contain N pairs of captions and corresponding values. Captions consist of Latin letters only. Values consist of Latin letters and spaces. All captions are different. Note that several fields may have the same caption.

Output file format

Output file must contain a single line — a form with all fields filled in. It is guaranteed that values for all captions are present in the input. Note that spaces in the form are significant and must be preserved.

Constraints

All strings have length from 1 to 1000 characters. All fields consist of at least 3 underscores. 0 ≤ N ≤ 100

Sample tests

Hello _________ welcome to our ___
         name               location
2
name
Vasya
location
Eastowner city

Hello _Vasya___ welcome to our _E_

___  ____
a a
1
a
bb

_b_  _bb_

Problem C. Comparison of topologies ≡

Statement

Consider a set of rings on the plane. Each of these rings can be described by coordinates of its center (x, y), internal and external radius: q, r. It is known that any two circles bounding different rings do not cross each other.

Let us define a continuous mapping on this set that includes the next operations:

• to move a center of any ring along the continuous curve;
• to resize internal (or external) radius of the ring.

It is assumed that during these operations the bounding circles shouldn't intersect. Also, any ring shouldn't become singular (circle or point) during resizing. In other words, this mapping must keep the basic topological properties of the initial set.

Your program must, given two sets of the rings M₁ and M₂, determine whether there exist a continuous mapping to obtain M₂ from M₁ or not. It is assumed that order of rings in these sets may be different.

Input file format

Input file contains integer n — number of rings in the each set, followed by 4 × n floating point numbers x_i, y_i, q_i, r_i — parameters of the rings of M₁, and then followed by another 4 × n numbers — similar parameters of the rings of M₂,

Output file format

Output file must contain a single integer 1 — if M₂ can be obtained by continuous mapping from M₁ or 0 — otherwise.

Constraints

All input values have no more than 3 digits after the decimal point.

 − 10⁵ < x_i, y_i < 10⁵, 0 < q_i < r_i < 10⁵, 1 ≤ n ≤ 2000

Sample tests

 3
 0.000  0.000  1.000  2.000
 0.000  0.000  0.500  1.500
 5.000 -7.000  1.000  2.000
 0.000  0.000  1.000  6.000
-5.000  9.000  0.500  2.000
 0.000  0.000  0.500  1.500

1

 3
 0.000 -2.500  4.790  6.800
 0.000 -2.180  3.260  4.000
 9.810  2.630  1.000  1.500
 0.000 -8.500  2.000  6.800
-0.940 -4.000  0.500  1.500
-3.970 -8.970  1.000  1.500

0

Problem D. Destiny of mathematician ≡

Statement

Young mathematician Vasya has dropped out of university computer science degree, and now works as a janitor in a local software company. Part of his job is to lock offices after every programmer leaves.

Employees of software company work on a flexible schedule, everybody comes and goes when he pleases. However, Vasya's mother calls him every evening to know when Vasya will get home so as to prepare a hot supper for him.

For a long time Vasya was unsure how to answer, but finally he remembered something from his mathematical education. Vasya collected data about programmers' schedules. There are N programmers working in the company, numbered from 1 to N. Programmer number i may leave work in any integer-valued moment of time between l_i and r_i inclusive with equal probability. All moments of time are measured in a whole seconds passed from the start of the day.

All programmers work on different projects so their schedules are independent from each other. Each day, Vasya leaves the office at the same moment as the last programmer.

Your program must, given data about programmers' schedules, calculate an expected value (also known as mathematical expectation) of the moment when Vasya will leave work.

Input file format

Input file contains a single integer N, followed by N pairs of integers l_i r_i.

Output file format

Output file must contain a single floating point number  — expected value of the moment of Vasya's leaving, with at least 5 correct digits after decimal point.

Constraints

1 ≤ N ≤ 8, 1 ≤ l_i ≤ r_i ≤ 1000

r_i − l_i ≤ 100

Sample tests

1 1 8

4.5

2 1 10 1 10

7.15

Problem E. Empire ≡

Statement

The Galactic Empire consists of numerous star systems. Each system has its own number. The capital world, Trantor, has number 1. Initially, thousands years ago, the empire consisted of Trantor only. All other star systems were captured by the Empire and each next system was receiving the next natural number (2, 3, etc.).

In order to keep the Empire connected, each newly captured system was connected by a hyper-tunnel with exactly one of the systems belonging to the Empire at the moment of capture. Captures is the only case when the Empire builds hyper-tunnels.

Some of the systems were disconnecting from the Empire and were never captured again. In order to disconnect from the empire, rebels destroy the hyper-tunnel that was built to connect them with the Empire. Some other systems also may become disconnected from the Empire at that moment and the Empire loses them too.

Hari Seldon is looking for a perfect star system for Foundation. He reconstructed the whole history of the Empire and represented it as a sequence of events: captures and disconnections. After each event he needs to know the number of the system which is the most remote from Trantor (i.e., the distance between Trantor and the system should be maximal, that's what we considers as the best place for Foundation). The distance from one system to another is measured as minimal number of hyper-tunnels that one need to pass in order to get from one system to another. If there are several most remote systems, Hari can take any of them.

Unfortunately, software engineers are quite rare in the Empire. Luckily, Hari found you and asked you to help him. You should write a program that, given the history of the Empire, will tell which world is the most remote after each event.

In the example given below, there are 5 events:

1. Add new system and connect it to system 1. New system receives number 2 and becomes the most remote system.
2. Add new system and connect it to system 2. New system receives number 3 and becomes the most remote system.
3. Add new system and connect it to system 1. New system receives number 4, but the most remote system is still 3.
4. Disconnect system 2. System 3 also appears disconnected and thus the most remote system is 4.
5. Add new system and connect it to system 4. New system receives number 5 and becomes the most remote system.

Input file format

The first line of the input file contains integer number N — number of historical events. The description of events in chronological order follows starting from the second line of the input. Each event is written in a single line. If the event is adding a new system to the Empire, then it's written as " + V" where V is the number of the system in the Empire that new system got connected with (the new system receives next integer number in the sequence of system numbers). Disconnections are written as " − V" which means that the system V is disconnected from the Empire.

All input data is correct, i.e. only a system that is connected to the Empire can be disconnected, new systems will be connected only to the ones that belong to the Empire, Trantor is never disconnected.

Output file format

For each event from the input file, print the number of the system which is the most remote from Trantor. In case several solutions exist, output any of them.

Constraints

1 ≤ N ≤ 200000;

Sample tests

5
+1
+2
+1
-2
+4

2
3
3
4
5

Problem F. FEFU swarm ≡

Statement

Scientists of Far Eastern Federal University have put serious effort into design and construction of collectives of interconnected robots, known as robot swarms.

To demonstrate their research, scientists decided to program robots to move in beautiful patterns in front of an audience.

Robots are located on a flat field divided into N by M square cells. Each robot takes exactly one square. To keep their connection, each robot must have another robot in one of the cells with a common side to its cell. Each second, exactly one of the robots may move into any of 8 neighbor cells, provided the destination cell was free and the robot will remain connected at the destination cell.

Initially robots are positioned in a horizontal row starting from the bottom left corner of the field.

Target pattern is a 4-connected set of cells (i.e. every cell of the pattern is connected to at least one other cell of the pattern). There are no holes inside the pattern.

Your program must, given description of a field and a target pattern, find such a sequence of robot moves that after executing it all cells of the pattern will be occupied by robots. Total number of moves in the sequence must not exceed 10⁶. Robots are allowed to temporarily move off the field during the sequence.

Input file format

First line of input file contains integers N M — field size. Following N lines contain M characters each.

Each character may be one of: '#' (ASCII 36)  — robot on initial position, '.' (ASCII 46)  — free cell, '*' (ASCII 42) — free cell which is a part of target pattern. It is guaranteed that number of robots equals number of target cells. There are at least 2 robots.

Output file format

Output file must contain integer C — number of robot moves, followed by C move descriptions.

Each move description must contain 4 integers i₁ j₁ i₂ j₂ — coordinates (row and column numbers) of source and destination cells for a robot move. Rows are numbered from 1 to N top to bottom. Columns are numbered from 1 to M left to right.

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

Constraints

2 ≤ N, M ≤ 100, C ≤ 10⁶

Sample tests

4 4
..**
...*
....
###.

10
4 1 3 2
3 2 3 3
4 2 3 2
3 2 2 3
4 3 3 4
2 3 2 4
3 3 2 3
2 3 1 4
3 4 2 3
2 3 1 3

Problem G. Garden of mystery ≡

Statement

Eccentric millionaire Vasiliy Vorotkin-Tretij has a garden.

The garden is a rectangular area extending W meters from east to west and H meters from north to east. Each 1 × 1 meter square is either covered with walkable grass (represented by '.' character, ASCII 46) or by impenetrable bushes (represented by '#' character, ASCII 35).

A set of grass squares is a secluded area if:

1. there is a path between every pair of squares in the set, such that
2. each square in the path belongs to the set and has a common side with the previous square in the path;
3. there are no more grass squares in the rest of the garden which have a common side with any square in the set.

Mystery level of garden is the number of secluded areas within it.

Vasiliy is quite proud of his garden's mystery level, and has decided to improve it. For this, he wants to build an additional wall of bushes from north to south across all the garden (i.e. replace all grass squares in a single column by bush squares).

111#2#
#1##2#
3#4#2#
3#####
333#55

Input file format

First line of input file contains integers W H. Following H lines contain W characters each — garden representation.

Output file format

Output file must contain two integers: maximum possible mystery level and number of column to be replaced by a wall (columns are numbered left to right from 1 to W).

If there are several optimal solutions, output one with the minimum column number.

Constraints

1 ≤ W, H ≤ 1000

Sample tests

5 1
.....

2 2

6 5
.....#
#.##.#
.#...#
.##.##
......

5 4

1 1
#

0 1

Problem H. Honest mileage ≡

Statement

Serge is an auto dealer. He brings cars from Japan and sells them in Russia. In contrast to a widespread practice of "rolling back" mileage to make a car look less used, Serge prefers a honest approach. He even drives his cars a little to get a "nice-looking" mileage numbers.

Serge says that mileage is "nice-looking" if digits located at corresponding positions on main and auxiliary car odometers are equal. The numbers on the main and auxiliary odometer written one below another look like this:

00015153 0
XXXX5121.0

Dot is the decimal separator on auxiliary odometer and does not take a place of a digit. "X" is a space filler, designating that there is no digit on this place.

Main odometer is incremented by one after each full kilometer since the moment when Serge starts driving. Serge may reset auxiliary odometer to zero at any time. Auxiliary odometer is incremented by 0.1 after each full hundred of meters since either the moment when Serge starts driving or last reset, whichever is later. Whenever any odometer reaches maximum value, it resets to zero upon next increment.

Your program must calculate a minimum distance that Serge needs to drive on his car to set car odometers to a nice-looking mileage. In the example above Serge needs to drive 35.5 km.

Input file format

The input file contains two strings, one per line. The first string contains nine digits and determines initial state of main odometer.

The second string contains four 'X' characters followed be four decimal digits, dot and another digit — the state of auxiliary odometer.

Output file format

Output file must contain a single exact floating point number — the distance that Serge must drive, measured in kilometers.

Sample tests

000151530
XXXX5121.0

35.5

Problem I. Illumination overlap ≡

Statement

The road is a straight line. A segment of the road between points A and B is N meters long and fully illuminated by several street lamps. Each lamp can be located at any (not necessarily integer) point along the road and illuminates a segment exactly M meters long, including endpoints. If any single lamp would be turned off, at least some part of the road segment between A and B will not be illuminated any more. Lamps do not illuminate parts of the road outside of segment from A to B.

Your program must calculate maximum possible number of lamps which could be put on the road while still satisfying the conditions above.

Picture illustrates sample 3.

Input file format

Input file contains integers N M.

Output file format

Output file must contain a single integer — maximum number of lamps.

Constraints

1 ≤ M ≤ N ≤ 10⁹

Sample tests

3 2

2

1000 1

1998

8 2

6