Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Consider a sequence of numbers a_{1}, …, 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 contains integer N followed by N integers a_{i}.
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.
1 ≤ N ≤ 10^{6}, 0 ≤ a_{i} ≤ 10^{9}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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 ________ nameIn computerized form, captions are represented by a single string of spaces and Latin letters. Every caption is a single word. Number of captions is guaranteed to be equal to the number of fields. However, number of spaces between captions may be arbitrary, so captions are not necessarily located directly under corresponding fields.
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:
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 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.
All strings have length from 1 to 1000 characters. All fields consist of at least 3 underscores. 0 ≤ N ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  Baranov A.A.  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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:
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_{1} and M_{2}, determine whether there exist a continuous mapping to obtain M_{2} from M_{1} or not. It is assumed that order of rings in these sets may be different.
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_{1}, and then followed by another 4 × n numbers — similar parameters of the rings of M_{2},
Output file must contain a single integer 1 — if M_{2} can be obtained by continuous mapping from M_{1} or 0 — otherwise.
All input values have no more than 3 digits after the decimal point.
−10^{5} < x_{i}, y_{i} < 10^{5}, 0 < q_{i} < r_{i} < 10^{5}, 1 ≤ n ≤ 2000
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  M. Sporyshev, A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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 integervalued 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 contains a single integer N, followed by N pairs of integers l_{i} r_{i}.
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.
1 ≤ N ≤ 8, 1 ≤ l_{i} ≤ r_{i} ≤ 1000
r_{i} − l_{i} ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  I. Tuphanov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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 hypertunnel with exactly one of the systems belonging to the Empire at the moment of capture. Captures is the only case when the Empire builds hypertunnels.
Some of the systems were disconnecting from the Empire and were never captured again. In order to disconnect from the empire, rebels destroy the hypertunnel 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 hypertunnels 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:
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.
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.
1 ≤ N ≤ 200000;
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  M. Sporyshev  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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 4connected 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^{6}. Robots are allowed to temporarily move off the field during the sequence.
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 must contain integer C — number of robot moves, followed by C move descriptions.
Each move description must contain 4 integers i_{1} j_{1} i_{2} j_{2} — 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.
2 ≤ N, M ≤ 100, C ≤ 10^{6}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Eccentric millionaire Vasiliy VorotkinTretij 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:
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).
Your program must find a location for a northsouth wall which maximizes mystery level. In the second sample, original garden has mystery level 1. Replacing all grass squares in the 4th column by bushes will create five secluded areas, shown by digits in a picture.  111#2# #1##2# 3#4#2# 3##### 333#55 
First line of input file contains integers W H. Following H lines contain W characters each — garden representation.
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.
1 ≤ W, H ≤ 1000
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  I. Oleynikov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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 "nicelooking" mileage numbers.
Serge says that mileage is "nicelooking" 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 nicelooking mileage. In the example above Serge needs to drive 35.5 km.
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 must contain a single exact floating point number — the distance that Serge must drive, measured in kilometers.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  M. Sporyshev  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
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 contains integers N M.
Output file must contain a single integer — maximum number of lamps.
1 ≤ M ≤ N ≤ 10^{9}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 

