Author:  A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Your program must calculate total number of such pairs of integers (p, n) that p ≥ 1, n > 1 и A ≤ p^{n} ≤ B.
Input file contains two integers A and B.
Output file must contain a single integer — number of pairs.
2 ≤ A ≤ B < 2^{63}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
You are given a board of n × m cells, one of them is occupied by a chess knight. Some cells were removed from the board.
Your program must determine the minimal number of moves that a knight must perform to visit all cells of a given list in order, not visiting removed cells in the process.
On other words, given list of cells must be a subsequence of cells visited by the knight.
Input file contains integers n and m — board size.
Next there is an integer P, followed by P pairs of integers (a_{i}, b_{i}) — coordinated of removed cells.
Next there is an integer L, followed by L pairs of integers (x_{i}, y_{i}) — coordinates of cells to visit (starting with initial position of the knight).
Output file must contain a single integer — minimal number of moves.
If there is no solution, output −1.
0 < x_{i+1} − x_{i} + y_{i+1} − y_{i}, 2 ≤ (n, m) ≤ 100,
0 ≤ (a_{i}, x_{i}) < n, 0 ≤ (b_{i}, y_{i}) < m,
0 ≤ P ≤ 5000, 2 ≤ L ≤ 100
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 came back home from an internship in a large IT company. As a souvenir, he brought back a band with a sequence of M natural numbers embroiled on it.
Vasya does not care much about numbers, so he wants to gift a band to a friend. However, each one of M Vasya's friends has exactly one number he strongly dislikes, and so would not want a band containing that number as a gift. All numbers disliked by Vasya's friends are different.
In order to still make a gift out of the band, Vasya wants to cut it in such a way, that every piece of the band could be given to at least one of his friends (several pieces may go to the same friend).
Your program must determine minimal number of cuts Vasya must perform to be able to give all pieces as gifts.
First line of input file contains integer N — count of numbers on the band.
Second line of input file contains N integers a_{i} — a sequence of numbers on the band.
Third line of input file contains integer M — number of Vasya's friends.
Fourth line of input file contains M integers b_{i} — disliked number of ith friend. All b_{i} are different.
Output file must contain a single integer — minimal number of band cuts.
1 ≤ N ≤ 10^{5}
2 ≤ M ≤ 10^{5}
1 ≤ a_{i}, b_{i} ≤ 10^{9}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Vasya became the chef of an elite restaurant. His clients are many and has very particular taste preferences. One of the most important features of restaurant dishes are various spices.
Each client requires specific amount of every kind of spice, according to his taste. If his dish does not contain enough of some spice, client becomes dissatisfied.
Since there is only a limited amount of each kind of spice in the kitchen, sometimes it is impossible to satisfy all clients. Your program must help Vasya to minimize number of dissatisfied clients.
Input file contains integer number of kinds of spices M, followed by M integers A_{j} — amount of available spice of each kind.
Following is integer N — number of clients, and matrix P_{i j} — amount of spice of jth kind required by ith client. The order is: all spices for the first client, then all spices for the second client, etc.
Output file must contain indexes of clients who will remain satisfied. Clients are indexed from zero.
0 < M ≤ 5, 0 < N ≤ 50, 0 ≤ (A_{j}, P_{i j}) < 10
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 designer Vasya creates logo for his company. He imagines it to be a company name, each letter colored either blue or orange.
Vasya wants to color letters so that the name consisted of singlecolor substrings of equal length. Color of sequential substrings must alternate. In other words if first X letters are colored orange, next X must be colored blue etc.
For each letter of the alphabet, Vasya decided if it is allowed to be colored blue, orange, either of those colors, or not allowed to be used at all. Vasya wants to color company name in two colors so that his requirements for splitting into substrings and constraints on letter colors are satisfied.
Your program must calculate number of different ways Vasya may color his company name.
First line of input file contains a string of letters which may be colored blue.
Second line of input file contains a string of letters which may be colored orange.
Third line of input file contains a string of letters — company name which must be colored.
Output file must contain a single integer — number of different ways to color company name.
All strings consist of small Latin letters. String length is not more than 10^{5}.
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 
City government plans to install several food stalls and several security posts on the street where young programming Alice lives. A scheme of their locations was developed.
Scheme is represented by a string S consisting of characters:
'.
' — unoccupied place,
'F
' — food stall and
'S
' — security post.
To be eligible for federal financing, plan must satisfy requirements of Federal program of Postponing and Stalling. In particular, a report is required, where for ith security post there will be two numbers l_{i} and r_{i} — the number of stalls between this post and nearest post to the left (or the beginning of the street) and number of stalls between this post and nearest post to the right (or the end of the street).
Your program must generate the required report.
The only line of input file contains a scheme with the plan.
Output file must contain integer N — number of security posts, followed by N pairs of integers l_{i} and r_{i} — the number of food stalls to the left and to the right of ith post. Posts must be listed in order of their occurrence in the scheme from left to right.
Schema string is no longer than 10^{5}.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Baranov, A. Zhikhareva  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
There is a rectangular table with unsigned integer values in cells.
Initially table was stored on separate lines, however during the processing formatting was lost and all separators (including line feeds) were replaces by spaces (ASCII 32). It is known that values in every column were the same.
Your program must find possible number of rows for initial table.
Input file contains a sequence of cell values, separated by spaces.
Output file must contain all possible variants for number of rows, in increasing order.
All cell values are in range from 0 to 2^{31} − 1.
Total number of cells is not greater than 2 ⋅ 10^{5}.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Input file:  Standard input  Time limit:  1 sec  
Output file:  Standard output  Memory limit:  512 Mb 
Young programmer Vasya writes a "hello world" program in a simple programming language. Program consists of a single line and should look like that:
print("Hello,World")
Vasya is very bad at typing. While trying to enter the line above,
he pressed letter keys L times, special character keys C times
(including quotes, comma and parentheses).
Vasya also pressed backspace
key B times, erasing a single character every time.
Your program must determine if it is possible in principle that Vasya achieved the exact text above.
Input file contains integers L, C, B.
Output file must contain a single line YES
or NO
.
0 ≤ L, C, B ≤ 100
L + C ≥ B
No.  Standard input  Standard output 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
There are two triangles attached to a fixed point F. One triangle in fully inside of another. Each triangle is represented by vertices in polar coordinate system (varphi, r) with the origin at point F.
It is known that internal triangle may rotate around the fixed point until it touches the external triangle.
Your program must determine maximum range of possible rotation angles for internal triangle.
Input file contains 6 floating point numbers representing vertices of external triangle: varphi_{1}, r_{1}, varphi_{2}, r_{2}, varphi_{3}, r_{3}.
Followed by 6 floating point numbers representing vertices of internal triangle in similar manner.
Output file must contain the width of range of allowed rotation angles in radians, with at least 5 correct digits after decimal point.
All tests are designed to minimize errors due to machine loss of precision.
Both triangles are nondegenerate (vertices do not belong to the single line).
Fixed point F is inside of both triangles.
All angles varphi_{i} are in radians and in range from 0 to 2 ⋅ π.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 

