Author:  A. Usmanov. Translation: V. Toropov.  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Avengers defeated alien invaders and decided to eat some shawarma.
Hulk ordered N shawarmas. M shawarmen immediately started to cook his order. Each shawarman can cook his first shawarma in T minutes. Each next shawarma requires S minutes more to cook than the previous one.
HULK SMASHes!!! awaiting his shawarmas.
You should help Avengers to find out the time when all shawarmas ordered by Hulk will be ready and green giant will calm down. Of course, Jarvis could solve this task, but Iron Man's suit is broken and only air conditioner is working right now.
First line contains two integers N and M — number of shawarmas ordered by Hulk, and number of shawarmen who are going to complete his order.
Second line contains two integers T and S — time needed to cook the first shawarma and the difference of cooking time between two shawarmas in the row.
Print one integer — time needed to complete Hulk's order.
1 ≤ N, M, T ≤ 100
0 ≤ S ≤ 100
No.  Standard input  Standard output 

1 


2 


3 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Given an integer number A in decimal notation, your program must divide its digits between two integers B and C so that:
Input file contains a single integer A.
Output file must contain two integers B and C. If there is more than one solution, output any of them.
10 ≤ A ≤ 10^{9}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  佳木斯大学, A. Usmanov. Translation: V. Toropov.  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Aningaaq and his N brothers went to a casino. Today they are going to play following game. First they agree about their bet. They can't change this bet later. The game consists of several rounds. Each round, every player is going to bet or to pass. Winner is somehow determined and receives some prize (not money).
The oldest brother got the largest amount of money from parents. The second oldest brother got one dollar less than the oldest brother. The third oldest got two dollars less than the oldest brother. And so on. Aningaaq is the youngest brother. He got only M dollars.
Brothers are going to play while somebody has any money. And they are not supposed to give money to each other.
Aningaaq is worried that game can last very long and they are going to be late at home. Help him to find out the minimal possible number of rounds.
First line contains two integers N and M — number of Aningaaq's brothers and amount of money Aningaaq has.
Print one integer — minimal possible number of rounds.
0 ≤ N ≤ 40
1 ≤ M ≤ 1000
In the first test Aningaaq is alone, so he can bet all his money in the first (and single) round.
In the second test Aningaaq has 1 dollar. His brother has 2 dollars. Brothers can agree that the bet is one dollar. Then, in the first round Aningaaq will spend all his money and his brother will have one more dollar to play another round.
No.  Standard input  Standard output 

1 


2 


Author:  N. Grebenyuk, A. Usmanov. Translation: A. Logutova.  Time limit:  2 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Wilson got lost in a cave N × M cells. However, he has a map with the following notation keys:
'#' — an impassable cell (an abyss, a wall);
'.' — a free cell;
'X' — a wormhole — Wilson can teleport from this cell to any other wormhole with an equal probability;
'S' — a start cell;
'F' — a target cell — Wilson needs to get to this cell (an exit to the surface).
Movement through a wormhole is a risky process, because it takes a lot of Wilson's mind. When the level of his mind become too low, Wilson can be attacked by monsters.
Wilson's mind will be enough exactly for one teleportation. Therefore he wants to know the probability of him getting out of the cave using no more than one wormhole. Naturally, Wilson moves optimally, trying to maximize this probability.
Wilson can move in four directions: up, down, to the right and to the left.
Note that Wilson cannot step into a cell with a wormhole without using it.
The first line contains two integers N and M — dimensions of the cave.
It follows by N lines, M characters each — map of the cave.
It is guaranteed that there is one 'S' cell, at least one 'F' cell and at least two 'X' cells on the map.
Print the answer as an irreducible fraction by two integers (for example: if the answer is 50 / 74, you have to print "25 37").
2 ≤ N, M ≤ 1000
No.  Standard input  Standard output 

1 


2 


3 


4 


Author:  A. Usmanov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
In a chess, it is useful in some positions if two knight figures cover one another.
Sergey has already placed one knight on an empty chess board. Now he wants to know number of squares where he can place the second knight so that knights would cover each other.
First line contains position of the first knight in a format of HW, where H — column (file), W — row (rank).
Output a single integer — number of squares for the second knight.
H ∈ (a, b, c, d, e, f, g, h)
1 ≤ W ≤ 8
Remember that a knight moves in a shape of letter L. Knight moves for 1 square in one direction (vertically or horizontally), and for 2 squares in another direction.
In the first sample the second knight can be placed on squares c 1, g 1, c 3, g 3, d 4 and f 4.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  M. Sporyshev  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Young programmer Vasya goes to work and from work on the train every day.
When returning from work, Vasya is very tired, so he can fall asleep in the train.
On the route from work to Vasya's home there are N stations. Each of them is announced on the radio at the moment when the train is at the previous station. Vasya's station is announced on the Nth station.
If Vasya hears the name of his station, then he will not miss it for sure.
However, every time Vasya listens to the names of the stations, he can fall asleep with a probability of 0.5. In this case, he won't hear the announcement on the next M stations. After sleeping through the announcement of the station, Vasya would never get off the train on it.
Now Vasya thinks whether to give up such a habit of sleeping on the train. For this, he wants to calculate the probability of oversleeping the announcement of his station.
The first line of the input file contains integers N, M — total the number of stations and the number of stations that Vasya will sleep.
Output a single number — the probability to oversleep the announcement of the station with an accuracy of at least 5 digits after the decimal point.
1 ≤ M ≤ N ≤ 1000
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Usmanov, L. Verkhovtsev. Translation: A. Logutova.  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Leonid is an astronaut. His spaceship crashed on far unknown planet, full of natural resources. Leonid couldn't repair his spaceship, therefore he stayed on the planet. Many years later he achieved fantastic progress in planet exploration — he built an ore mining and processing mill.
The mill works in several stages:
1. N drills mine the ore. The speed of one drill is U_{N} kilograms per hour;
2. The ore gets to melting furnaces. The speed of one furnace is U_{K} kilograms per hour;
3. After furnaces, plates get to M machinetools. The speed of one machinetool is U_{M} kilograms per hour.
Leonid's mill pollutes the planet. This pollution disturbed inhabitants of the planet. Fictional arthropods have broken all furnaces.
Leonid is planning to build new furnaces and to renew manufacture. But at first he wants to calculate an optimal number of furnaces. We will call "surplus" the total quantity of the ore and plates, which is waiting for the processing. The number of furnaces is optimal if the surplus is minimal for the fixed period of time.
Help Leonid to calculate optimal number of furnaces. Obviously, Leonid wants to renew manufacture as fast as possible. Therefore among all possible answers, you should choose the minimal one.
The first line contains two integers N and M — the number of drills and machinetools respectively.
The second line contains three integers U_{N}, U_{K} and U_{M} — the speeds of one drill, one furnace and one machinetool respectively.
Print an integer — optimal number of furnaces.
If there are several possible answers, choose the minimal one.
1 ≤ N, M, U_{N}, U_{K}, U_{M} ≤ 10^{9}
Let's consider first test. Let's fix the period of time — T = 10 hours. Amount of produced resources is shown in the table.
Number of furnaces  Mined ore, kg  Melted ore, kg  Surplus ore, kg  Processed plates, kg  Surplus plates, kg  Surplus ore and plates, kg 

1  100  30  70  30  0  70 + 0 
2  60  40  60  0  40 + 0  
3  90  10  70  20  10 + 20  
4  100  0  70  30  0 + 30 
Surpluses are equal for three and four furnaces, which means that three furnaces is enough.
No.  Standard input  Standard output 

1 


2 


3 


Author:  N. Grebenyuk. Translation: A. Logutova, V. Toropov.  Time limit:  2 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
A group of scientists studied a sample of vanadium catalyst of new generation. It allows to form different linear hydrocarbons from gaseous mixture of carbon and hydrogen.
Hydrocarbon with a certain structure became the result of each scientists experiment. His formula was recorded by spectral analysis device as a linear line. However, such form of record is short. Therefore, scientists needed to transform this record to the full version.
The full version of any hydrocarbonic chain, received in this experiment, is formed by the following rules:
1. The hydrocarbonic chain is pictured as a linear sequence of carbons (pictured by symbol 'C'). The link between carbons can be single (pictured as '') or double (pictured as '=').
2. Each carbon is connected with hydrogens by single links, to be tetravalent. This means that each carbon should have 4 links (double link is counted as two links):
— first and last carbons are connected to form equal angles. Namely, if there are two hydrogens they are connected by diagonal links ('/', '\'). If there are three hydrogens they are connected by up (''), down ('') and side ('') links.
— the rest of carbons: single hydrogen is connected by up link and two hydrogens are connected by up and down links.
Short version of hydrocarbonic chain looks like a sequence CHa_{1} CHa_{2}...CHa_{N}, where a_{i} (2 ≤ a_{i} ≤ 4) is a number of hydrogens with i^{th} carbon. There is no number when it's only one hydrogen. And there is no 'H' symbol when carbon does not have any hydrogens.
Note that short record should have the same orientation as full record. Which means that the leftmost hydrocarbon in short record should match the leftmost hydrocarbon in full record.
Look carefully at sample tests for complete understanding.
First line contains a string with short version of hydrocarbonic chain.
It is guaranteed that given hydrocarbonic chain is correct.
Print 5 × (3 + 2 ⋅ N) characters, where N is the number of carbons in given chain.
All spaces not occupied by symbols of links or atoms should be filled with symbol '.'.
1 ≤ N ≤ 10000
No.  Standard input  Standard output 

1 


2 


3 


4 


Author:  N. Grebenyuk, A. Usmanov. Translation: A. Logutova.  Time limit:  3 sec  
Input / output:  interactive  Memory limit:  256 Mb 
This is an interactive problem.
As a punishment for Aleksey using his cellphone in the classroom, the teacher locked Aleksey's device with a password. This password is a sequence of N unsigned integers X_{i}, chosen by the teacher. However, the teacher did not want to waste his time for thinking up all numbers of the sequence. Therefore, he used a random number generator.
To unlock his device, Aleksey needs to guess the sequence. He can ask the teacher no more than Q questions: whether X_{i} is divisible by d. All numbers in the sequence are indexed from 1 to N.
Help Aleksey to regain access to his cellphone. He has already regretted his bad behavior during the class. He'll never do it again.
The first line contains one integer N — the length of the sequence.
It is guaranteed that the sequence is randomly generated before all Aleksey's questions and cannot be changed after that.
To give your answer to the teacher you have to print character "!" (without quotes), then print N spaceseparated guessed numbers X_{i}. Note that "!" and X_{1} should be separated by a space too. Your program should terminate immediately after you gave the answer.
Jury has fixed a number Q for each test — the maximum amount of questions, which you can ask the teacher. It is guaranteed that Q questions are enough to solve the problem. Q won't be given to your program as an input. If your solution asks more than Q questions, it will get "Wrong answer" for this test.
To ask a question your program has to print line "? i d" (without quotes), i (1 ≤ i ≤ N) and d (1 ≤ d ≤ 5000) are integers. Jury program gives your solution line "Yes" if X_{i} is divisible by d or "No" if it's not.
In the end of each question you have to print newline character \n and flush output buffer. To flush the buffer you can use (just after printing):
Language  C++  Pascal  Java  Python 
Command  cout.flush()  flush(output)  System.out.flush()  stdout.flush() 
100 ≤ N ≤ 400
1 ≤ X_{i} ≤ 5000
Q = min(150 ⋅ N, 5 ⋅ 10^{4})
Note that the first test doesn't satisfy the constraints of the problem (N = 2).
It was created only to demonstrate interaction of solution program and jury program.
Q = 2000 for the first test.
No.  Standard input  Standard output 

1 

