Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Vasya likes to decrease numbers, but does not like negative numbers. So, he picks some integer A_{1} and starts to decrease it by 100 and take an absolute value of the result. In other words, on each step he calculates next number in the sequence A_{i + 1} = A_{i} − 100.
When Vasya calculates a number which was already present in the sequence, he gets bored and stops. Your program must, given A_{1}, determine the number of steps Vasya would perform.
For example, if A_{1} = 1 then A_{2} = 1 − 100 = 99, and A_{3} = 99 − 100 = 1, so Vasya performs 2 steps.
Input file contains a single integer A_{1}.
Output file must contain a single integer N — number of steps.
0 ≤ A_{1} ≤ 10^{9}
No.  Input file (input.txt ) 
Output file (output.txt ) 

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:  M. Sporyshev, I. Tuphanov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Programmer Vasya commutes to work by train every day. Vasya came to the train station today as usual, but forgot his wallet! There is no time to get back. Vasya decided to take the train without buying a ticket. Obviously, he wouldn't be happy to meet an inspector now.
The train consists of N carriages served by M inspectors. Luckily, Vasya always takes this train and knows A_{i} — numbers of carriages where inspectors are located at the moment he enters the train. He also knows the direction (toward the first or toward the last carriage) of each inspector and his (or her) speed V_{i} — the number of carriages that the inspector passes per hour. Thus every 1 / V_{i} hours the inspector moves to the next carriage in his (or her) direction. The inspector stops if there is no next carriage in that direction.
The trip to work is long, so Vasya wants to pick a carriage where he could stay as long as possible until the moment when an inspector shows up in his carriage. Help Vasya with this.
First string of the input contains integers N and M — the number of carriages and the number of inspectors accordingly.
Then M lines follow, ith line contains integers A_{i}, V_{i} — carriage number where the inspector i is located when Vasya gets on the train, and his (or her) speed. V_{i} is negative if the inspector is moving toward the first carriage, and positive otherwise.
Output the number of carriage which Vasya should get in to. Carriages are numbered from 1. If there are multiple solutions, output any of them.
1 ≤ N, M ≤ 200000
1 ≤ A_{i} ≤ N
− 10^{6} ≤ V_{i} ≤ 10^{6}, V_{i} ≠ 0
In the first sample input Vasya can stay in the carriage number 1 as long as he wants.
In the seconds sample input there are inspectors in carriages 1 and 5 at time 0. After 0.5 hours inspector 1 enters carriage 4. After 1 hour from the beginning of the ride, inspector 1 enters carriage 2, while inspector 2 enters carriage 3. Thus, both 2 and 3 are correct answers.
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  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, A. Zhikhareva  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
In the laboratory there is a weird construction consisting of N equal cylindrical flasks in a row.
Flask number i contains a_{i} milliliters of a liquid.
In a single step, you can pour any amount of liquid from a single flask to one or both its neighbours on the left and on the right in any proportion. The amount of liquid in each flask must remain integer value after each step.
Your program must perform the minimum number of aforementioned steps to make all flasks contain the equal amount of liquid.
The first line of the input file contains an integer N.
The second line contains N integers a_{i}. It is guaranteed that the total amount of liquid is divisible by N.
The first line of the output file must contain an integer S — the minimum number of steps.
Each of the following S lines contain three integers I, L, R — the index of the flask starting from 1, the amount of liquid to pour into the flask to the left and the amount of liquid to pour into the flask to the right respectively.
If there are several solutions, output any of them.
1 ≤ N ≤ 10^{5}
0 ≤ a_{i} ≤ 10^{9}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Usmanov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Arocdnicg to rsceearch at Cmabrigde Uinervtisy, it deosn’t mttaer in waht oredr the ltteers in a wrod are, the olny iprmoatnt tihng is taht the frist and lsat ltteer are in the rghit pcale. The rset can be a toatl mses and you can sitll raed it wouthit pobelrm. Tihs is buseace the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.
Alexey decided to test whether this property will also hold for integers. He picked an integer number N and now wants to rearrange its digits so that:
Additionally for each position except the first and the last one, digits located in this position before and after rearrangement must be different.
You program must rearrange digits of a given integers according to Alexey's requirements.
Input file contains a single integer N.
Output file must contain a single integer — an answer to the problem. If there are several solutions, output any of them.
If there is no solution, output − 1.
1 ≤ N ≤ 10^{9}
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 decided to start running every morning to keep himself in a good shape.
Vasya googled how to run properly if you have lead a sedentary lifestyle for too long and found an article where the following technique was offered.
You need to run along a circular track divided into N segments. Length of ith segment is a_{i} meters.
One should alternate slow and fast running: on the first, third and following odd segments — with the speed of V m/s, on the second, fourth and following even segments — with the speed of 2 V m/s.
Vasya wondered how far he would run in T seconds, given the sequence of segment lengths and the starting speed.
The first line of the input file contains integers N, V, T — the number of segments, the initial speed and the time that Vasya will run for.
The second line of the input file contains integers a_{i} — lengths of the segments along the track. The sum of the lengths of the segments is equal to the length of the track.
Output file must contain a single number — the distance that Vasya will run in the specified time with an accuracy of at least 5 digits after the decimal point.
1 ≤ N ≤ 10^{4}
1 ≤ a_{i} ≤ 10^{4}
1 ≤ V, T ≤ 10^{4}
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 
Given an integer number A in decimal notation, your program must split it into 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^{18}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 

