Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Artem made up three integers and told Eugene the average value of every pair of them. Eugene easily restored original integers. Now you try to do the same!
Input contains three numbers: x, y and z. Numbers are either integers or have fractional part of exactly 0.5. At least one number is not zero.
Output original integers in nondescending order (input data are such that the original numbers will turn out to be integer).
− 10^{8} ≤ x, y, z ≤ 10^{8}
In the sample x = 1.5, y = 2 and z = 3.5. These are pairwise averages for a = 0, b = 3 and c = 4. Indeed:
a + b2 = 0 + 32 = 1.5 = x;
a + c2 = 0 + 42 = 2 = y;
b + c2 = 3 + 42 = 3.5 = z.
No.  Standard input  Standard output 

1 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
In the "Three minnows" tavern for a gold coins you can buy three bread crusts and get back some change, or, for b gold coins — five bread crusts and some change. How many bread crumbs you are guaranteed to get for c golden coins?
One gold coin is equal to 100 silver coins. There are no other coin types in the country. One bread crust price is a whole number of silver coins. To get three bread crusts and a change for a gold coins means that three crusts cost strictly less than a golden coins, but four crusts cost more than a gold coins.
Input contains three integers a, b and c, one per line. Input data is such that the answer exists.
Output a single integer — problem answer.
1 ≤ a < b ≤ 10^{9}
1 ≤ c ≤ 10^{9}
No.  Standard input  Standard output 

1 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Find the smallest positive integer which is divisible by n and starts from digits 2021 in decimal notation.
Input contains a single integer n — the divisor of the required number.
Output a single integer — the answer.
1 ≤ n ≤ 10^{12}
No.  Standard input  Standard output 

1 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
In the Brothers Grimm's fairy tale, one of the tests for Cinderella was an episode when the evil stepmother scattered cereals in a heap on the floor and ordered her to sort them out on plates. The cereals vary depending on the version. In one fairy tale, Cinderella was sorting through millet and poppy seeds. In another, she arranged beans and lentils. In the third, barley was separated from oats. There were peas with rice, and buckwheat with millet, and bags of red and white beans. Which version is true is unknown, so in this problem the stepmother formed a bunch of decimal digits and demanded that Cinderella count the number of each digit in the heap.
In total, there are n levels in the heap, at the topmost there is a single digit d, on each next level there is one more digit than at the higher level. For convenience, let's imagine a heap (for n = 4 and d = 8) as shown in the picture.
Heap of numbers was formed by the stepmother according to certain rules. The very first number on the levels starting from the second is equal to the first number on the higher level, increased by 1 and taken modulo 10. For example, the first number on the second level is (8 + 1)% 10 = 9. The first number on the third level is (9 + 1)% 10 = 0, and so on.
The rest of the digits in the heap are formed as follows: take two numbers — to the left in the same level and on a higher level above the number just taken, they are added and the result is taken modulo 10. For example, the second number at the second level is (9 + 8) % 10 = 7.
If Cinderella knew what dynamic programming is, then the rules for filling the heap would look like this:
DP[1, 1] = d;
DP[i, 1] = (DP[i  1, 1] + 1) % 10;
DP[i, j] = (DP[i, j  1] + DP[i  1, j  1]) % 10.
Input contains two numbers: n and d.
Output ten integers — number of digits from 0 to 9 in the heap.
2 ≤ n ≤ 10^{5}
1 ≤ d ≤ 9
No.  Standard input  Standard output 

1 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Novice programmer Vasya develops his own vector graphics editor. In addition to the usual primitives (like rectangles, circles, straight lines) his editor also supports working with objects of complex shapes, which are described using spline curves.
Each such curve consists of several pieces, in sequence one after the other, each of which is given by a parametric equation of the following form:
X_{i}(t) = AX_{i} ⋅ t^{3} + BX_{i} ⋅ t^{2} + CX_{i} ⋅ t + DX_{i};
Y_{i}(t) = AY_{i} ⋅ t^{3} + BY_{i} ⋅ t^{2} + CY_{i} ⋅ t + DY_{i},
where t — scalar parameter, changing in range of [0, 1].
Vasya uses closed spline curves to describe complex shapes. One of his tasks is to determine for every given point whether it lies inside such a figure.
The beginning of the input contains an integer N, followed by 8 × N real numbers, specifying the coefficients of the corresponding splines
AX_{i}, BX_{i}, CX_{i}, DX_{i},
AY_{i}, BY_{i}, CY_{i}, DY_{i}.
Next there is integer M, followed by 2 × M real numbers, specifying the coordinates of the points (X_{j}, Y_{j}).
Output must contain M integers (answers to each query):
1 — if the point is inside the contour,
0 — if it is outside.
Within the specified accuracy, the contour is continuous and does not have selfintersections.
The distance from each point to the boundary of the contour is not less than 10^{ − 5}.
The contour lies entirely within the rectangular area [ − 10, 10] × [ − 10, 10].
1 ≤ N ≤ 1000, 1 ≤ M ≤ 10^{5}.
No.  Standard input  Standard output 

1 


Author:  Иван Кобец  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
The young programmer Ilya was presented with a sequence of numbers a_{i} of length n for his birthday. Ilya decided to select fine segments from this sequence. A fine segment is a sequence of successive elements of a_{i} containing some element equal to the sum of its first and last elements. For example, the sequence [1, 2, 5, 4] is fine because the sum of the leftmost and rightmost elements is 5, and the number 5 is in this sequence; the sequence [1, 2, 3, 4] is not fine because the sum of the leftmost and rightmost elements is 5, and the number 5 is not in this sequence. Your program must count the number of fine segments in a given sequence.
The first line contains an integer n — the length of the sequence. The second line contains n integers a_{i} — the elements of the sequence. All elements of the sequence are different.
Output a single integer — number of fine segments in the sequence.
1 ≤ n ≤ 10^{3}
1 ≤ a_{i} ≤ 10^{5}
First sample has one fine segment: [3, 7, 5, 4].
Second sample has two fine segments: [1, 5, 4] и [1, 5, 4, 7, 6].
No.  Standard input  Standard output 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
A palindrome is a string of characters that reads equally in both directions (left to right and right to left).
Given an arbitrary string S, consider an lexicographically ordered list of all the different palindromes that can be obtained by deleting and rearranging characters in the original string.
It is required to exclude from the specified list those palindromes which are lexicographically less than given string T.
If after that list is still longer than n, the extra palindromes from the end should also be removed.
The first two lines of the input contain strings S and T, consisting of digits and lowercase letters of the Latin alphabet.
They are followed by an integer n.
The output must contain all the remaining palindromes in the list in lexicographic order.
If there are none, the output should be an empty string.
0 < T ≤ S ≤ 100,
0 < n ≤ 2 ⋅ 10^{4}
No.  Standard input  Standard output 

1 


2 


Author:  Антон Карабанов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
We are already used to advanced algorithms for automatic image processing. With their help, it costs us nothing to remove the background from the photo, cover up the wrinkles and even make a joint collage with any celebrity. But have you ever wondered how such programs work? Is it difficult to write them? You are presented with a simple task: find and remove a single extra character from an ASCII picture.
A picture of size n × m contains an image of an empty rectangle one pixel thick and one extra pixel, denoted by "#" symbols (ASCII code 35). The rectangle is at least three pixels long and three pixels wide, and its sides are parallel to the edges of the image. The background of the picture is filled with "." (ASCII code 46).
The first line of the input contains two integers: n and m. The next n lines contain strings of length m, consisting of the characters "#" and ".".
Output n lines of m characters each — the same image with an extra pixel removed.
3 ≤ n, m ≤ 100
No.  Standard input  Standard output 

1 


2 


3 


Author:  A. Usmanov  Time limit:  1 sec  
Input / output:  interactive  Memory limit:  512 Mb 
This is an interactive problem. You will interact with a jury program by sending and receiving particular messages.
Jury made up a secret bit string X of length N.
Your program must make a queries of the form "? M L R
".
Answer to the query is a result of lefttoright and righttoleft
comparison of two substrings of M bits: starting with position L and staring from position R. Bits are numbered right to left.
You must determine the value of X by making of not more than ⌈ N + 12⌉ queries.
First line of input contains integer N — number of bits in X.
To make a query, your program must output "? M L R
", where
M — number of bits to compare, L and R — positions to compare.
Jury program answers each query with two characters —
results of lefttoright and righttoleft comparisons.
Possible comparison results are: < , > и = .
Queries must not require access to bits outside boundaries of X.
When your program determines X, it must output "! X
",
where X
— string of bits X.
After printing the answer your program must finish execution.
If your program makes incorrect query, it will receive "Presentation error" verdict. If your program exceeds allowed number of queries, it will receive "Wrong answer" verdict.
Every query and final output must be a single line ending with single endofline (\n
).
Output buffers must be flushed after every line:
Language  C++  Pascal  Java  Python 
Code  cout.flush() 
flush(output) 
System.out.flush() 
stdout.flush() 
1 ≤ N ≤ 60
0 < X < 2^{N}
1 ≤ M ≤ N
0 ≤ L, R < N
L + M, R + M ≤ N
In the first sample secret number is 01101. First query compares 101 with 011 and 101 with 110, thus the answer is > < .
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 blackboard in the math classroom had number n written on it. There were no zeros anywhere in the number. While passing along, Timofey decided to play a joke and swapped neighboring digits in the number k times. What is the largest possible resulting number?
Input contains integers n and k, one per line.
Output a single integer — problem answer.
11 ≤ n ≤ 10^{250}
k ≤ 10^{9}
In the first sample n = 97 and a single swap, giving 79.
In the second sample it is optimal to move three to the first place and get 312
No.  Standard input  Standard output 

1 


2 


3 


Author:  Антон Карабанов,Игорь Блинов  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
A group of students decided to create a startup to replace QR codes with new improved system.
They decided to represent binary data as a string of digit patterns for 0 and 1, displayed on a picture below.
Picture also contains a representation of a binary string 1001
.
Digits in the code are separated by one column of '.' characters, first and last digit are located right on the edges of the code. If the image taken by camera does not exactly coincide with the digit patterns, then the number of differing pixels is called recognition error.
System must determine the minimal recognition error which can be obtained by picking the bit string most closely resembling given image.
First line of input contains integer n — image width. Following three lines contain the image. Each character is either '#' (ASCII 35), or '.' (ASCII 46).
Output single integer — minimum possible recognition error.
2 ≤ n ≤ 100000
No.  Standard input  Standard output 

1 


2 


Author:  Антон Карабанов  Time limit:  2 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Two students are preparing for exam, when they will get a single question out of n possible ones. They decided to split questions to study as follows:
First student picks a number a from 1 to n and learns a questions numbered a, a + 1, a + 2, ... , a + a − 1. If some number exceeds n, numbering continues from 1. For example, if n = 5 and a = 1, the first student will only learn question 1, when a = 2 he will learn questions 2 and 3, when a = 4 — questions 4, 5, 1 and 2, when a = 5 — all questions.
Second student also picks a number b ≠ a from 1 to n and learns b questions numbered b, b + 1, b + 2, ... , b + b − 1. Similarly, if some number exceeds n, numbering continues from 1.
Given number of questions n determine number of different ways to choose a and b, such that every question will be learned by at least one of students.
Input contains an integer n.
Output an integer — number of ways to choose a and b.
2 ≤ n ≤ 10^{6}
In the first sample all possible choices of a и b result in learning all questions.
In the second sample there are four questions. If a = 1, and b = 2, question number 4 will not be learned by either student.
If a = 1, and b = 3, question number 2 will not be learned by either student.
In other cases all questions will be studied.
No.  Standard input  Standard output 

1 


2 

