Author:  G.Korneev, A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
A company wants to name a new product. Marketing department determined, that a name for a product is appropriate, if:
Your program must calculate the number of possible appropriate names. Note that English vowels are: 'a', 'e', 'i', 'o', 'u', 'y'.
First line of input file contains two integers N M — name length and number of offensive substrings.
Following M lines contain offensive substrings s_{i}, one per line.
Output file must contain a single integer — number of appropriate names modulo 10^{9} + 7.
1 ≤ N ≤ 50, 0 ≤ M ≤ 50, 1 ≤ length(s_{i}) ≤ N.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  M. Sporyshev  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Young game developer Alice has created a new game and sent it to friends for betatesting.
Young gamer Vasya wants to impress Alice by finishing the game completely.
At the final level Vasya fights the main boss — Binary King. At the beginning of the fight, Binary King generates a sequence K of N binary digits. After that, Vasya must present his own binary sequence V of the same length.
Vasya's sequence is scored as follows. For each position i, if V_{i} = 1 and K_{i} = 0, Vasya gains 1 point; if V_{i} = 0 and K_{i} = 1, Vasya loses 2 points.
Since Vasya plays at the hardest difficulty, each prefix of his sequence must contain at least as many zeroes as ones.
To win, Vasya must get maximum possible number of points.
Input file contains N characters 0 and 1 — King's sequence.
Output file must contain N characters 0 and 1 — Vasya's sequence scoring maximum number of points. If there are several optimal solutions, output any of them.
1 ≤ N ≤ 10^{5}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Baranov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Let us consider a rectangular domain D = {(x, y): Ax ≤ x ≤ Bx, Ay ≤ y ≤ By} covered by the uniform grid (twodimensional array of cells):
Ω_{i j} = {(x, y): x_{i} < x < x_{i+1}, y_{j} < y < y_{j+1}}, where x_{i} = Ax + (i − 1) ⋅ Sx, y_{j} = Ay + (j − 1) ⋅ Sy, i = 1, 2, …, Nx, j = 1, 2, …, Ny,
Sx = (Bx − Ax) / Nx, Sy = (By − Ay) / Ny — grid steps for x and y respectively.
The grid is defined by four real parameters (Ax, Ay, Sx, Sy) and two integer parameters (Nx, Ny).
Note that cells are open rectangles not including their boundaries.
Your program must count grid cells that have common points with the ring defined by its center (x_{0}, y_{0}), internal and external radius (r_{1}, r_{2}).
Input file contains parameters of the grid: Ax, Ay, Sx, Sy, Nx, Ny, followed by parameters of the ring: x_{0}, y_{0}, r_{1}, r_{2}.
Output file must contain a single integer — number of cells intersecting the ring.
All input values have no more than 5 digits after the decimal point.
− 10 < (Ax, Ay) < 10, 1 ≤ (Bx − Ax) < 10, 1 ≤ (By − Ay) < 10, 0 < (Nx, Ny) ≤ 10^{6},
−10 < (x_{0}, y_{0}) < 10, 0 ≤ r_{1} ≤ r_{2} < 10
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Baranov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
You have a document that needs to be signed by university president. It's hard to get president's time, but luckily you know his current location in the university campus. You also know that he is heading to his office now, so you can try to intercept him on the way and ask for a signature. Even more, everyone at university knows that president always takes fastest path wherever he goes. However, if there are several fastest paths, the president chooses any of them.
You need to write a program that determines whether you can guarantee meeting the president no matter which of the fastest path he picks, if you start moving from your room at the same time as the president.
More formally, university campus map is given as an undirected graph. ith edge is given by its vertices (a_{i}, b_{i}) and traversal time t_{i} (this is a traversal time for any human, either you or the president). Initially, the president is located at vertex p_{1} and is taking one of the fastest paths to his office located at vertex f. You are initially located at vertex p_{2}. You can get the signature if you meet the president at vertex v such that:
Input file starts with two integers: n — the number of vertices and m — the number of edges.
Then m edges are given by integers a_{i}, b_{i}, t_{i}. Vertices are numbered starting from 0.
Finally, there are three integers f, p_{1}, and p_{2}.
Output file must contain the number of vertices where it is possible to get the signature, followed by the list of vertex numbers in ascending order.
It is guaranteed that the graph is connected, i.e. it's possible to get from any vertex to any other vertex.
There is no more than one edge between each pair of vertices (a_{i}, b_{i}).
2 ≤ n ≤ 1000, 1 ≤ m ≤ n(n − 1) / 2
0 ≤ a_{i}, b_{i}, p_{1}, p_{2}, f < n
a_{i} ≠ b_{i}, p_{1} ≠ p_{2}
0 < t_{i} ≤ 1000
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Young physicist Masha studies lasers. Masha wants to create a simplest 2dimensional waveguide, consisting of two very long parallel mirrors, one coinciding with the Ox axis, and another located h millimeters above the first.
Masha's laser is located at coordinates (0, y) and emits light in direction (1, −1). Masha wants to hit a target located at coordinates (x_{t}, y_{t}) by choosing a good value for h. All coordinates are in millimeters.
Note that laser itself must fit into the waveguide, so h ≥ y. Both mirrors and laser are perfect, so light is always fully reflected at 45 degrees angle.
Input file contains three integers y x_{t} y_{t} — coordinates of laser and target.
Output file must contain a single integer — value of h. If there are several solutions, output the smallest one. If there are no solutions, output −1.
1 ≤ y, x_{t}, y_{t} ≤ 10^{9}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Wellknown store chain "Three cats" decided to create a marketing lottery. Customers were given tickets with sequential integer numbers, and each month a single ticket number was selected as a winner.
To promote company image, it was decided that winning number must be divisible by 3.
For the first month of the lottery, company selected a ticket and printed it on a large banner to hang inside the store. Unfortunately, a person from marketing who selected a ticket did not know math, and selected ticket number which is not divisible by 3.
To quickly fix the banner, your program must change exactly one digit in the number so that:
Input file contains a string of N decimal digits. First digit is nonzero.
Output file must contain a string of N decimal digits — fixed ticket number. If there is more than one solution, output numerically smallest of them. If there is no solution, output string IMPOSSIBLE.
2 ≤ N ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Baranov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Let us consider 3dimensional area that is split by uniform rectangular grid. Some cells contain ants. Each second every ant can either stay put or move to the neighboring cell in any of the six directions: up, down, right, left, forward and backward.
Your program must, given coordinates of starting cell for each ant, find minimum possible number of seconds (starting from zero) until any two ants meet in the same cell.
Input file contains integer N followed by N triples of integer indices X_{i}, Y_{i}, Z_{i} — coordinates of starting cells for each ant.
Output file must contain a single integer — minimal number of seconds until two ants meet.
−10^{6} ≤ (X_{i}, Y_{i}, Z_{i}) ≤ 10^{6}, 2 ≤ N ≤ 5 ⋅ 10^{4}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  M. Sporyshev  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Young programmer James decided to practice horticulture and brought home N plants.
Plant number i has starting height of a_{i} centimeters and grows by v_{i} centimeters per day. Vasya has a girlfriend Alice, who is currently traveling away from home. Alice does not like tall plants, so Vasya decided to cut his plants shorter from time to time.
Vasya can reduce height of any plant by exactly X centimeters (but not make it negative) in one cut. Vasya's endurance in not very good, so he can make no more than M cuts per day. Every day, plants grow after all cutting is finished.
Alice will return in T days. Vasya would like to cut plants in such a way as to make on the day of her arrival the height of the highest plant as small as possible.
First line of input file contains integers N, T, M, X.
Second line contains N integers a_{i} — initial plant heights.
Third line contains N integers v_{i} — plant growth speeds.
Output file must contain a single integer — minimal height of the tallest plant after T days.
1 ≤ N ≤ 10^{5}
1 ≤ T ⋅ M ≤ 10^{5}
1 ≤ X, a_{i}, v_{i} ≤ 10^{5}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  М. Спорышев  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Sorted array of integers is represented implicitly. Instead of each element, a set of that element and its neighbors on the right and on the left is known. First and last array elements have no more than one neighbor. Note that the set does not represent neither the order of elements nor duplicate values.
Your program must output explicit representation of the array (all elements in order).
First line of input file contains integer N — number of elements in array.
Following N lines contain implicit representation of array elements: set size s_{i} and s_{i} different integers a_{ij} — a set of ith array element and its neighbors.
Output file must contain N integers — elements of original sorted array.
1 ≤ N ≤ 10^{5}
−10^{9} ≤ a_{ij} ≤ 10^{9}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Let's define that a positive integer is a jubilee if it is divisible by 5 and is no less than 10. (i.e. 10, 15, 20, …).
Your program must, given a sequence of N decimal digits, find maximum number of jubilees which can be made by splitting this sequence into disjoint subsequences. In other words, every digit of sequence must be used no more than once and original order of digits must be preserved.
In the first sample, sequence 2535 can be split into 25 and 35.
In the second sample, sequence 1115005000 can be split into 10, 10, 10, 50 and 50.
Input file contains a string of N decimal digits. First digit is nonzero.
Output file must contain a single integer — number of jubilees.
1 ≤ N ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Your program must output large letter 'K'.
Letter is drawn using '#' (ASCII 35) characters and is composed of vertical line of V characters, upper diagonal of H characters, and lower diagonal of L characters.
Diagonals must connect in the middle of the vertical line. If vertical line has even length, diagonals must connect on the character above the middle.
Letter image must be the smallest possible rectangle including the letter. Parts of rectangle not occupied by the letter must be filled with '.' (ASCII 46) character.
Input file contains three integers V H L.
Output file must contain letter image.
3 ≤ V ≤ 20
1 ≤ H, L ≤ 20
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 

