Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Today, in a mathematics lesson, Timofey studied the topic of "Proportions". He was too lazy to write down his homework in his notebook, relying on his memory, and here is the result — Timofey remembers three of the four members of the proportion, but does not remember where they stood! He is also sure that the answer to the problem (an unknown element of proportion) is as a natural number. Help Timofey find all the correct answers for this assignment.
The first line of the input contains three integers separated by space: a, b and c — known members of the proportion.
Output natural numbers in ascending order — all possible different solutions of the proportion. If there are no solutions — output the number 1.
1 ≤ a, b, c ≤ 10^{9}
In the first example, it is possible to make this proportion: 24 = 36.
In the second sample, there are no suitable solutions (with an integer answer).
In the third sample, it is possible to make these proportions: 24 = 816, 24 = 48, 12 = 48.
No.  Standard input  Standard output 

1 


2 


3 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Let there be two strings A and B, consisting of digits and lowercase Latin characters.
On the string A, we define the operation textSWAP(i, i + 1), which consists in exchanging the characters at positions i and i + 1.
It is required to determine the minimum number of such operations for transforming string A to string B.
Input contains two strings: A and B.
Output must contain a single integer.
It is guaranteed that the required transformation can be performed.
Line lengths do not exceed 2 ⋅ 10^{5}.
No.  Standard input  Standard output 

1 


2 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Today is Grisha's birthday! Each of his n friends brought a box of favorite sweets as a gift to the birthday boy. Since Grisha is not a greedy boy, he took all the sweets out of the boxes and put them on n + 1 plates and placed them in front of each guest (including himself). To everyone's delight, this was done without a remainder. Immediately after that, his mother returned from work and it was decided to put all the sweets on n + 2 plates. To everyone's surprise, this division was completed without a remainder.
Given the known number of sweets in one box k, determine the possible number of guests at the party.
The only line of the input contains a natural number k.
In the first line output single natural number g — the number of possible answers to the problem's question. In the second line print g natural numbers — possible number of guests in ascending order, separated by a space. It is guaranteed that there is at least one suitable answer.
1 ≤ k ≤ 10^{9}
In the sample, the number of candies in one box is 6.
If one guest came to Grisha, then the total number of sweets is also 6. It is easy to divide them equally without a remainder both into two and three plates.
If two guests came to Grisha, then the total number of sweets is 12. It is easy to divide them equally without a remainder both into three and four plates
There are no other solutions.
No.  Standard input  Standard output 

1 


Author:  Антон Карабанов, И. Блинов, А. Баранов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Zhenya drew a regular ngon on the board, labeled its vertices with numbers clockwise in ascending order: "1 2 3 ... n". Nikita came up and rearranged the numbers in the signature, erased all sides of Zhenya's figure and connected the vertices in the resulting new order (including the first and last vertices). Now a closed broken line flaunts on the board. How many pairs of line segments intersect?
The first line of the input contains single integer n. The second line contains n numbers a_{1}, a_{2}… a_{n} — a permutation of the polygon's vertices.
Output a single nonnegative integer — the answer to the problem question.
3 ≤ n ≤ 10^{5}
No.  Standard input  Standard output 

1 


2 


3 


4 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Consider a set of N twodimensional points represented by their coordinates (X_{i}, Y_{i}).
It is required to determine the number of all possible rectangles that satisfy the following conditions:
Input starts with integer N,
followed by 2 × N integers, representing point coordinates: X_{i}, Y_{i}.
The output should contain
the number of detected rectangles.
All input points are different.
− 10^{6} ≤ (X_{i}, Y_{i}) ≤ 10^{6},
4 ≤ N ≤ 10^{5}
No.  Standard input  Standard output 

1 


2 


Author:  И. Блинов  Time limit:  2 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Paulundra is playing a multiplayer shooter called Counterrant. Recently Counterrant launched a new season of the Battle Pass where you can get n of the m available weapon skins. The skin opening system is unusual: the player is given n runes, to use the rune, you need to insert two crystals of fixed colors into it, after which if the rune fits the weapon, the weapon opens. A rune matches a weapon if the weapon contains both colors contained in the rune. Each weapon skin contains exactly C colors.
The Battle Pass consists of k levels. For each level of the Battle Pass, exactly one crystal is given, for each level the reward is known in advance. For reaching level i, the reward will be a crystal with the color a_{i}. The player uses the crystals at his own discretion: inserts into any of the runes or does not use the crystal at all. Since it's hard to earn levels, Paulundra wants to know what is the minimum number of Battle Pass levels she needs to unlock in order to get at least p skins, assuming she distributes crystals and runes optimally.
The first line of the input contains five numbers m, C, n, p and k. This is followed by m lines containing C numbers c_{ij} each describing the colors of weapon skins with number i. The next n lines contain two numbers each a_{i1} and a_{i2} — rune descriptions. The last line of the input contains k number S_{i}, where S_{i} is the color of the crystal for getting level i
Print a single integer — the minimum number of levels you need to get to open at least p skins. If p skins cannot be opened print 1.
1 ≤ m ≤ 100
2 ≤ C ≤ 10
1 ≤ n, p ≤ 10
1 ≤ k ≤ 10^{6}
1 ≤ a_{i1}, a_{i2}, S_{i}, c_{ij} ≤ 10^{9}
a_{i1} ≠ a_{i2}
No.  Standard input  Standard output 

1 


2 


3 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Vasya found out that his grandfather has been fond of solving crossword puzzles for a very long time.
On his anniversary, Vasya decided to present him a game, which is a generalized version of the crossword puzzle — "graphword".
A playing field in it is an undirected graph the vertices of which are assigned lowercase letters of the Latin alphabet.
In the process of solving the "graphword" the player needs to compose words by moving along the edges of such a graph.
According to the rules of the game, each edge can be visited more than once.
However, it is forbidden for the current edge to coincide with the previous one.
When developing levels for his game, Vasya was faced with the task of determining the number of all possible paths,
forming some given word in a given graph.
Since the resulting number may be too large, the answer should be the remainder of its division by 10^{9}.
Input starts with the number of vertices N, followed by the set of characters assigned to each of the vertices.
Next, the number of edges M is given, followed by the edges themselves,
each of which is given by the indices of its vertices: a_{i}, b_{i}.
Vertices are numbered starting from zero.
Input is finished with the string W, for which calculation should be done.
Output must contain a single integer.
1 ≤ N ≤ 10^{4}, 0 ≤ M ≤ 10^{4}, a_{i} ≠ b_{i}, 1 ≤ W ≤ 10
No.  Standard input  Standard output 

1 


2 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
The city of N has a happy event! On the single street of the city, new street lamp will be installed and the new pharmacy will open. Help the city governor to find optimal places for these objects.
The street is represented by a segment of coordinate axis, where the leftmost house has coordinate 0. Let's assume house sizes to be negligibly small compared to the street length and represent houses as points on the axis.
The lamp has "brightness" parameter expressing the distance from the lamp where the light reaches. For example when brightness is equal to 10, lamp installed at the point x = 25 will light the street on the segment from 15 to 35 inclusive.
The pharmacy has "remoteness" parameter expressing the distance from it to the house such that people from that house will still visit. For example when remoteness is equal to 100, pharmacy located at point x = 25, will be visited by people living in houses with coordinates from 0 to 125 inclusive (there are no houses with negative coordinates).
First line of input contains three integers separated by spaces: n — number of houses, a — brightness и b — remoteness. The second line contains nonnegative integers x_{i} — coordinates of each house in ascending order.
Output a single nonnegative integer — maximum total number of houses illuminated by the lamp and convenient to visit pharmacy from. Both lamp and pharmacy may be located at points with the coordinate of some house.
1 ≤ n, a, b ≤ 10^{5}
0 ≤ x_{i} ≤ 10^{9}
Sample contains ten houses, lamp brightness is 15 and pharmacy remoteness is 20. Lamp can be installed, for example, at point 115 (three houses will be illuminated: 100, 110 and 120). Pharmacy may be located at point 20, in which case it can be visited by people from the first 5 houses. A greater number of houses having "access" to the lamp and pharmacy cannot be obtained.
No.  Standard input  Standard output 

1 


Author:  A. Usmanov, A. Baranov  Time limit:  1 sec  
Input / output:  interactive  Memory limit:  512 Mb 
The problem is interactive and involves interacting with the jury program by sending and receiving messages in specific format.
Let there be a twodimensional point, it's known that the point is located inside a circle with radius 1.0 and the center at axes origin.
You're allowed to send queries in the form "check if circle with a center (x, y) contains the given point".
For the first query circle radius is 0.9. For each of the next queries the radius is reduced by 0.1.
You are to send exactly 8 queries in such a way, that the last one contains the point in question.
For each query print to output stream (stdout) two numbers (x, y) specifying the circle center.
Do not forget to flush the stream after each query.
As a response input stream (stdin) will receive a single integer:
1 — the circle contains the point;
0 — otherwise.
For the program to work correctly a line break
should be output and flush
should be performed
after each query sent to the output thread.
Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Student Vasily, having returned to his home village for the holidays, celebrates his successfully passed exams on a grand scale. He's walking along a single street, the schematic of which is shown on the picture. The street has a houses (with numbers 1, 3, 5, …, a × 2 − 1) on the left and b houses (with numbers 2, 4, 6, …, b × 2) on the right. There's a huge puddle in the middle of the street, so one can only cross the street at either start or end of it.
Standing next to a house in an altered state of mind Vasily randomly decides where to go next (each of the two possible directions is chosen with the probability 12). If he finds himself next to a tavern (house with the number t), he will immediately walk in and continue to party till morning, but if he is next to his home (house with the number h), he will decide that this is the sign of fate and he is to stop having fun. What is the probability that Vasily reaches his home and stops the celebration if currently he's standing next to the house with number n?
The first line of input contains two natural numbers separated by space: a and b — street description. The second line contains three natural numbers t, h and n separated by space — houses description. The consistency of the input data is guaranteed. It is guaranteed that the numbers t, h and n are distinct.
Output two spaceseparated natural numbers — the numerator and denominator of the irreducible fraction expressing the probability of the described event.
1 ≤ a, b ≤ 10^{9}
1 ≤ t ≤ a × 2 − 1, if t is odd.
2 ≤ t ≤ b × 2, if t is even.
Constrains for t are similar to h and n.
See picture. The street in the sample only has three houses (with number 1, 2 and 3). Houses on the left side have numbers 1 and 3, while on the right side there's only one house with the number 2. In this sample one it's possible to walk from any house to any other house. Vasily can reach either his home or tavern with equal probability 12.
No.  Standard input  Standard output 

1 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
The expression n − (n − 1) − (n − 2) − (n − 3) − ... − 3 − 2 − 1 is written on the board (for example, if n = 5 it will be written as 5 − 4 − 3 − 2 − 1). To avoid a failing grade in mathematics, Gavrila needs to put left and right parentheses in this expression, so that the result is zero. How many ways does he have to do it?
Input contains natural number n.
In the first line output a nonnegative integer m — the number of ways to arrange the parentheses in the required way. In the next m lines print two spaceseparated natural numbers a and b — the position of the parentheses (numbers from a to b inclusive will be inside the brackets). Output numbers a and b in descending order, and output pairs of numbers in order of descending a.
4 ≤ n ≤ 10^{5}
In the first example, n = 5 is given. Unfortunately, Gavrila won't succeed, for the given n there is no way to place the brackets in the required way.
In the second example n = 7 is given. If all numbers from 5 to 3 are enclosed in brackets, then an expression with the desired value will be obtained: 7 − 6 − (5 − 4 − 3) − 2 − 1 = 1 − ( − 2) − 3 = 0.
In the third example, for n = 12 there are several ways to solve the problem.
No.  Standard input  Standard output 

1 


2 


3 

