Author:  N. Grebenyuk  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Anastasia is standing in the beginning of a string (at the first letter), consisting of N lowercase Latin letters. She can make unlimited number of jumps to the next letter in the string. She also can make at most one hyperjump to any letter that is standing in alphabet later than the current letter. For example, if Anastasia is standing at letter 'x', she can jump to any of letters 'y' and 'z' in the string.
Anastasia is a very curious girl. She is interested what is the minimal number of jumps (a hyperjump is also counted as an one jump) she needs to reach the last letter (the letter number N).
The first line contains an integer N — number of letters in the string.
Second line contains string consisting of N lowercase Latin letters.
Print one integer — the minimal amount of jumps Anastasia needs to reach the last letter.
2 ≤ N ≤ 10^{5}
No.  Standard input  Standard output 

1 


2 


3 


Author:  N. Grebenyuk, A. Usmanov. Translation: A. Logutova.  Time limit:  2 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Nick is a skilled swimmer. He likes to swim in the high sea with a mask. But today he faced a problem — his way was blocked by a colony of Portuguese man o' war (a species of jellyfishes).
Nick noticed that they are arranged in N rows, length of each row is M meters. There is a gleam of 1 meter between each row, in which Nick can move freely to the right or to the left. In addition, there is free cells in some rows. Nick can use them to float between rows.
Nick has an underwater camera with him. That's why he decided to float through the colony and record a video to brag to friends after that.
However, boasting doesn't add courage. Therefore Nick wants to find out the length L (in meters) of the shortest way from the 1^{st} to the N^{th} row. L contains both: movements in a row and movements between rows. Nick can start swimming in any point of the first row and finish in any point of the last row.
The distance from the current row to the next is 1 meter. Note that Nick can only swim left/right in space between rows and forward (if there is no Portuguese man o' war in front of him). For a better understanding, look at the picture that illustrates the 2_{nd} example. The points in the picture mark the places where Nick stops in each row between his movements (Nick can't finish his swimming in the space between the rows, so the answer is always an integer number of meters).
The first line contains two integers N and M — measurements of the jellyfish colony.
It follows by N lines, M characters each — the colony description.
By '*' marked the place with jellyfish, by '.' — free place.
It is guaranteed that each row contains no less than 1 and no more than M − 1 Portuguese man o' war.
Print integer L — the length of the Nick's shortest way through the colony.
2 ≤ N, M ≤ 2000
No.  Standard input  Standard output 

1 


2 


3 


Author:  N. Grebenyuk  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Group of n scientists returned to their camp quite late. They were so tired so they didn't eat any of their m waffles.
However during the night every scientist woke up once, all at different time. Everyone thought that he woke up first, because all the rest were asleep, so if at the moment there were x waffles, he thought that he is allowed to eat xn waffles. In case xn was not an integer, a scientist could round it up or down, depending on how hungry he was. So every scientist ate ⌊ xn⌋ or ⌈ xn⌉ waffles, where x is the number of remaining waffles at the moment he woke up.
At the morning remained k waffles, after every scientist woke up during the night. Nobody remembers, neither when he woke, nor how many waffles were there at this moment, nor how hungry he was. They were interested, what could be minimal m_{min} and maximal m_{max} number of waffles in the beginning?
Notice that it's possible, that some scientists ate zero waffles.
The first line contains two integers n and k.
Print two space separated integers — m_{min} and m_{max}.
2 ≤ n ≤ 10^{5}
1 ≤ k ≤ 10^{9}
No.  Standard input  Standard output 

1 


2 


3 


Author:  N. Grebenyuk  Time limit:  2 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Ninja wants to gain an artifact located in the field of size N ⋅ M.
There are guards in the field. Each of them is looking in one direction and turns clockwise in the end of each second, so after four seconds a guard makes full rotation. A guard raises the alarm if he sees the ninja located on the line of guards sight, and nobody is located between them. The artifact is too small and doesn't obstruct guards sight.
Initially the ninja is located in the cell marked 'N', the artifact is in the cell marked 'A', guards are located in the cells marked '>', '<', '^', 'v' accordingly to their initial sight direction. In the end of each second ninja can move one cell in any of four direction or stay in the same place.
It is guaranteed that in the cell with guard there are no ninja, artifact or another guard. Initially (during the zero second) none of guards can see the ninja.
Your task is to find the minimal number of seconds the ninja needs to reach the artifact without being noticed or tell, that it's impossible.
The first line contains two integers N and M — field size. Then follow N strings of M symbols describing the field.
Print one integer — the minimal number of seconds the ninja needs to reach the artifact without being noticed, or "1" if it's impossible.
2 ≤ N, M ≤ 1000
No.  Standard input  Standard output 

1 


2 


3 


4 


Author:  N. Grebenyuk  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
«To infinity and beyond»
You are now in the Kingdom of Infinity.
In order to escape you need to find the value of the endless expression √[3]n + √[3]n + √[3]n + ... with specified accuracy (of course, that you are in the Kingdom of Infinity, decimal representation of the expression can be infinitely long).
Your answer will be accepted if it has absolute error at most 10^{−5}. More specifically, if your answer is a and the jury answer is b, your answer will be accepted if a − b ≤ 10^{−5}.
The first line contains an integer n.
Print the value of this infinite expression with specified accuracy.
−10^{18} ≤ n ≤ 10^{18}
No.  Standard input  Standard output 

1 


2 


3 


Author:  N. Grebenyuk  Time limit:  3 sec  
Input / output:  interactive  Memory limit:  256 Mb 
At the moment T (where T is an integer), Thanos was located in the point X, Y, Z (where X, Y, Z are also integers) and snapped his fingers. A radiation wave with intensity maxIntensity appeared immediately at this point. In rest points of space at this moment radiation was equal to 0.
Radiation wave is an expanding sphere. Radius of sphere increases one unit in one second, for example, it is equal to a after a seconds. At the time a any point of sphere surface (that is any point which distance to X, Y, Z is equal to a) has intensity equal to maxIntensity. Intensity is gradually decreasing in points inside the sphere.
To be more specific, let's consider a point located at the distance dist (dist ≤ a) from the point X, Y, Z. Intensity of radiation in this point is equal to maxIntensity − (a − dist). Intensity of radiation in points outside the sphere is equal to 0.
See the picture below for clarification. In this picture sphere surface with the maximal intensity (maxIntensity) is marked red. The space inside the sphere with gradually decreasing intensity is colored lighter. Notice, that there are limitations to parameter t we consider in this task, and it's guaranteed that maxIntensity is large enough that any point that gets in the sphere in moment t or earlier will never decrease to the intensity 0 or lower.
Tony stark decided to determine the place and the time of the snap of Thanos. He wants to use his chronotunnel he can send sensors with. A sensor can be sent in some specific time t in any point x, y, z. It measures radiation intensity in this point at the moment t, sends result to Tony Stark as a decimal number and burns. Stark has Q sensors in total, and he wants you to help him determine the place and the time of the snap using not more than Q sensor measurements. (Stark has not figured out yet, that he can go back in time and steal sensors from himself).
To provide the answer print the symbol "!" and then space separated integers T, X, Y, Z. Notice, that "!" and T also should be space separated. You should terminate immediately after printing the answer.
It is guaranteed that Q measurements are enough to solve the problem. If your solution uses more than Q sensors, it will get "Wrong answer" for this test.
To send a sensor parameters description your program has to print line "? t x y z" (without quotes), where 0 ≤ t ≤ 3 ⋅ 10^{8} and t, x, y, z are integers. Jury program gives you one decimal value — result of the measurement at time t in the point x, y, z.
At the end of each sensor parameters description and after printing answer 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() 
0 ≤ T, X, Y, Z ≤ 10^{8}
0 ≤ t ≤ 3 ⋅ 10^{8}
0 ≤ x, y, z ≤ 10^{8}
3 ⋅ 10^{8} < maxIntensity ≤ 10^{9}
Q = 250
No.  Standard input  Standard output 

1 


Author:  N. Grebenyuk  Time limit:  2 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Aleksey lost his favourite array a! He remembers that the array consisted of n nonnegative integers, and its sum was equal to sum.
Recently Aleksey found his calculations on this array. His calculations consist of n numbers b_{i} such that
b_{i} = (a_{i} + a_{i + 1})mod k for 1 ≤ i < n
b_{n} = (a_{n} + a_{1})mod k (a_{i} — favourite array numbers)
Help Aleksey to find any correct favourite array a corresponding to the array b, or tell him that he has made a mistake, and there is no such array. Notice, that all elements of source array are nonnegative integers that are not greater than 10^{4}.
The first line contains three integers n, k, sum.
The next line contains n nonnegative integers b_{i}.
If the answer exists, print "YES" in the first line and n space separated numbers of array a in the second line. If there are multiple answers, print any of them.
Print "NO" if there is no such array.
2 ≤ n, k ≤ 10^{4}
0 ≤ sum ≤ 10^{9}
0 ≤ a_{i} ≤ 10^{4}
0 ≤ b_{i} < k
No.  Standard input  Standard output 

1 


2 


3 

