Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Wellknown Internet company "Dalstolb" created an online marketplace, where individuals and companies can sell some products. After purchasing and testing the product, buyer can rate the seller with an integer number from 1 to 10. For each seller, website displays number of ratings N and their average A so that prospective buyers can choose better sellers.
If a company is not satisfied with its rating, it might either improve the quality of their goods and services, or create some fake accounts and give high ratings from those accounts to itself. That practice is called astroturfing.
"Dalstolb" is aware of astroturfing and implemented following limits to make it harder: each buyer may give only one rating to a given seller; all ratings strictly greater than twice the current average are flagged for manual inspection.
Your program must calculate the minimum number of fake accounts required to raise the rating to at least B, while not triggering manual inspection.
Note that all calculations by "Dalstolb" server are assumed to be absolutely exact, with no loss of precision at all.
In the first example, ratings and averages are as follows:
Fake account no.  Fake rating  Average rating 

1  4  2.40000 
2  4  2.66667 
3  5  3.00000 
4  6  3.37500 
5  6  3.66667 
6  7  4.00000 
Input file contains integers N A B.
Output file must contain a single integer — minimum number of fake accounts.
1 ≤ N ≤ 10^{8}, 1 ≤ A < B ≤ 9
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin, I. Tuphanov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Young web developer Vasya was hired by "Dalstolb" company. Company maintains a popular news website with many advertisement banners. Marketing department of "Dalstolb" has proposed a new idea for animated transition between two text messages on the banner.
Message is a single line of characters. First message has length L_{1}, second has length L_{2} ≥ L_{1}. Since the banner width is only enough to fit L_{1} characters, the message after the transition should contain any substring the second message of length L_{1}. Transition should be performed as a series of animation frames. Each frame, message is either scrolled to the right by removing leftmost character and appending arbitrary new character from the right, or scrolled to the left by removing rightmost character and appending arbitrary new character from the left.
You program must, given two messages, find a shortest possible transition between them.
First line of the input file contains the first message. Second line of the input file contains the second message. Messages are composed of small Latin letters.
First line of output file must contain integer N — minimum number of frames. Following N lines must contain twocharacter string each — frame descriptions. First character must be either L or R, denoting right or left scrolling correspondingly. Second character must be a small Latin letter which should be appended to the message.
1 ≤ L_{1} ≤ L_{2} ≤ 2000;
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
C language was designed specifically for students who failed standard course of Compiler Programming. C program is a list of statements. Each statement is one of:
Each variable is declared at most once in the block, but variables with same name may be declared in different blocks. It that case, name refers to the variable declared in the nearest enclosing block. Note that variables may be defined in the middle of the block.
The program is guaranteed to be correct — all blocks are properly balanced, variables are referenced only after declaration, variables are always initialized before reading, etc. Program contains at least one print statement.
Your program must execute a given C program.
First line of input file contains integer N. Following N lines contain one C statement each.
Output file must contain a sequence of integers — one integer for each print statement.
3 ≤ N ≤ 1000
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  G. Grenkin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
A sculpture of dragon is established in the campus of Far Eastern Federal University. There are long claws on dragon's paws. According to a legend, when a student passes the session successfully, the claws grow a little (by several nanometers). That's why students took an interest how much the area of the claw will increase when the claw grows by d mm.
Students constructed the following mathematical model of dragon's claw growth. The claw has the shape of a convex polygon with a base on the abscissa axis. The claw grows equally in all directions and doesn't grow below its base. When the claw grows by d mm, all its sides shift in parallel by d mm to the outside (see the figure). The base of the claw remains at the same place, so one should intersect the new polygon with the abscissa axis.
Your program must calculate the area of the claw before and after its growing.
Input file contains integers N d, followed by N pairs of integers x_{i} y_{i} — coordinates of vertices of the polygon in millimeters in the clockwise order. The polygon is nondegenerate.
Output file must contain 2 real numbers: the area of the claw before and after growing in mm^{2} with at least 4 correct digits after the decimal point.
3 ≤ N ≤ 40; 1 ≤ d ≤ 100; −100 ≤ x_{i} ≤ 100; 0 ≤ y_{i} ≤ 100; y_{1} = y_{n} = 0.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  I. Tuphanov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
FEFU computer scientists use a duplication method to detect errors in network data transfer. Each bit of data is duplicated. The duplicate follows the original bit. Each byte therefore is transferred as a message of two bytes. The first byte of the message encodes high bits of the original byte, the second byte encodes low bits.
For example, a byte 67 is encoded as follows:
Scientists received two bytes. Now they need to find out what the original byte was.
Input file contains two integers designating two received bytes.
Output file must contain a single integer — the original byte, or −1 if there was an error during transfer.
Both input integers are in the range from 0 to 255.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  I. Tuphanov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Vladivostok fortress is a unique distributed system of fortifications. City government made a museum on a nearby island with n fortifications (we will call them ''sites''), and has developed an unusual tourist route.
Sites are numbered from 1 to n. The site i may have an arrow (not more then one), pointing to another site a_{i}. The value a_{i} = 0 means that there is no arrow on the site i.
A tourist is disembarked from a helicopter to a random site i (the probability is equal for all sites). He stays at the site i for a while, and then follows the arrow to the next site a_{i}. On the new site the tourist is doing the same thing. If a_{i} = 0, the tourist just stays where he is. If a_{i} was already visited by the tourist, he also stays where he is. In the evening the helicopter picks up the tourist.
Arrows are placed properly, which means that there exists a site (maybe more then one), that will be visited by a tourist disembarked at any site.
The more sites the tourist has visited, the happier he is. So the government have decided to increase the expected number of sites visited by a tourist. Due to insufficient funding, they've just decided to change a_{k} for a single site k.
Help the government to choose k and a new a_{k}, such that arrows are still placed properly and the expected number of visited sites is maximized.
Consider the example below. There are 8 sites. Arrows are placed properly since from any site a tourist will get to the site 1. The expected number of visited sites is 1/8 * (1 + 2 + 3 + 2 + 3 + 4 + 4 + 5) = 3.0. After the change, arrows are still placed properly since from any site a tourist will get to sites 1, 4, 5, 7, and 8. The expected number of visited sites is 1/8 * (5 + 6 + 7 + 5 + 5 + 6 + 5 + 5) = 5.5. Any other value of a_{1} would not give a better answer. Changing a_{k} for any k ≠ 1 would not give a better answer.
Input file contains an integer n followed by n integers a_{i}.
Output file must contain two integers — k and a new a_{k}. If there is more then one optimal solution, output any of them. If it's impossible to increase the expected number of visited sites, output 0 0.
1 ≤ n ≤ 5 × 10^{5}; 0 ≤ a_{i} ≤ n.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  G. Grenkin, A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Two fathers and two sons walked together... It is well known that this could describe a group of either 3 or 4 people.
Now let's say that A fathers and B sons walked together. Could it be that this group consisted of exactly N different persons?
A person is counted as a father if there is his son among the group. A person is counted as a son if there is his father among the group. Each father can have one or more sons, each son must have exactly one father. Father of a person can not be this person's descendant. Each person must me either a son, a father, or both.
Your program must, given numbers A B N, output corresponding fatherson relationship or determine that it does not exist.
Input file contains integers A B N.
Output file must contain a number of fatherson relationships M followed by M pairs a_{i} b_{i} where a_{i} is a number of the father, b_{i} is a number of the son (1 ≤ a_{i}, b_{i} ≤ N).
All pairs must be different. If there are several solutions, output any of them. If it is impossible for a group to consist of N persons, output file must contain a single integer 0.
1 ≤ A ≤ B ≤ 100
1 ≤ N ≤ 200
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin, G. Grenkin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Vladivostok Hackathon was an event where several student teams were invited to invent and prototype their fresh and useful software ideas in several days.
Young programmer Vasya and his team suggested original and exciting game: Tetris. Game implementation turned to be more complex than young programmers expected, so they simplified the rules.
A game is played on a rectangular field of H rows and W columns of cells. Each cell is either occupied or free. A piece takes a single cell. New piece appears at some cell on the top row, and starts to fall down in steps. On every step a player can choose any free cell of the three cells in a row below the piece — directly under it, a single cell to the right or a single cell to the left.
A piece stops dropping when it either reaches the bottom row, or the row below it is occupied and the player did not choose to move the piece right or left. After the piece stops, next piece immediately appears. Nothing else happens in the game — no rows disappearing, no score, etc.
While Vasya's team was presenting the game to the jury, it crashed and refused to start again. The only proof that the game ever worked is the log file which it wrote on the previous run. Log file contains data about N pieces — the column where the piece appeared and the column where it stopped.
Your program must, given field a description and a game log, determine whether the log could be the result of a correct game, and, if not, what is the first piece which could not fall as described in the log.
In the sample 2, after first 6 pieces fall and 7th one appears, the field looks as follows:
.#.... ..#... ..#... ..#... .##..#It is impossible to move the piece to the 6th column, so the log in incorrect.
Input file contains integers W H N, followed by N pairs of integers x_{1} x_{2} — initial and final column of each piece.
Output file must contain a single integer — the number of first incorrectly positioned piece, or 0 if all pieces are positioned correctly.
1 ≤ W, H ≤ 10^{4}, 1 ≤ N ≤ 10^{6}, 1 ≤ x_{1}, x_{2} ≤ W
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
A professor of Fences, Entrances and Frames University has developed a new Fence Inclination theory. According to that theory, a fence is modeled as a sequence of planks. Every plank is either slanted right, represented by character / (ASCII 47), or left, represented by character \ (ASCII 92). For example, a fence of three rightslanted planks followed by two leftslanted planks would be represented by string ///\\.
Fence Inclination theory predicts that plank slants change in steps.
On a single step, the fence is first subdivided into a minimal possible number of plank groups. Each group consists of R ≥ 0 rightslanted planks followed by L ≥ 0 leftslanted planks. In the sample 1 below an initial state is subdivided into 3 groups, while in the sample 2 — into 4 groups.
Next, for every group: if R > L, all planks in the group become rightslanted, if R < L, all planks in the group become leftslanted, if R = L, plank of the group remain unchanged. So after the first step the fence in sample 1 will change into the state //////\\\\.
Steps are repeated until the fence state stops changing.
You program must, given the the initial fence state, output its final state after the changes stop.
Input file contains a single string of / and \ characters — representation of the initial fence state.
Output file must contain a single string of / and \ characters — representation of the final fence state.
The length of the input string is between 1 and 1001 characters.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 

