Input file:  Standard input  Time limit:  1 sec  
Output file:  Standard output  Memory limit:  256 Mb 
There are three strictly increasing arrays of integers A_{1}, A_{2}, A_{3} with lengths N_{1}, N_{2}, N_{3}.
Your program must find the count of triples of the same numbers simultaneously occurring in each of these arrays.
First line contains N_{1}, N_{2}, N_{3}.
Second line contains A_{11}, A_{12}, ..., A_{1N1}
Third line contains A_{21}, A_{22}, ..., A_{2N2}
Fourth line contains A_{31}, A_{32}, ..., A_{3N3}
1 ≤ N_{1}, N_{2}, N_{3} ≤ 10^{5}
0 ≤ A_{i j} ≤ 10^{9}
No.  Standard input  Standard output 

1 


2 


Author:  A. Karabanov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  64 Mb  
Output file:  Standard output 
A team of geologists is about to return from an expedition, but already prepares for the next one. The expedition leader sent a list of required items by radio.
Timofey is responsible for battery supplies. He has batteries of two types: AA and AAA. The message that he received looks like "quantity type" (without space). For example, a string "123AA" means that geologists need 123 batteries of the AA type, while a string "6AAA" means that they need 6 batteries of the AAA type.
Finally Timofey can get to work. Unfortunately, exactly one character in the message contains an error. Help Timofey to determine the maximum number of batteries of each type that geologists may require.
The only string in the input file is the string s. It's guaranteed that the string contains only characters from the following set: "0123456789A" (no quotes). It's guaranteed that the original radio message was valid (in particular, there was no leading zeros), and that exactly one character in it was changed.
The output must contain two nonnegative integers separated by a space — the largest number of if batteries of types AA and AAA respectively, which geologists may need according to their message.
3 ≤ len(s) ≤ 5
In the first sample the error may be in the first character. Then the original message could look like "923AA". The error could be in the second or in the third character, but Timofey still need to prepare at least 923 AA batteries. It's also possible that one of "A" characters was replaced with "3", and the original message was "12AAA". Thus Timofey needs at least 12 AAA batteries.
In the second sample the message could only be about AA batteries, while in the third one it could only be about AAA batteries.
No.  Standard input  Standard output 

1 


2 


3 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Young programmer Vasya is engaged in Ndimensional graph layout. As a result of the work of his algorithm, each vertex is assigned coordinates in the Ndimensional space. However, he did not take into account that the accuracy may be lost when the results are saved in different formats. Now he must examine files to determine which of them contains which graph.
We are given two graphs — original one and one read from file. Due to conversion vertex coordinates of the second graph may be shifted, but no more than by a given ε. Vertex indexing may be changed as well.
It is required to compare given graphs and reconstruct correspondence between their vertices if possible.
Input data contains integer N — dimension of the space, V — number of vertices and E — number of edges.
Following is a set of the N ⋅ V coordinates of vertices of the original graph and set of the E edges specified by index pairs. Vertices are indexed from zero.
Next the second graph is given in the same format.
The ε precision is the last item of the input.
Output data must contain V integers L_{i} — index of the second graph vertex corresponding to ith vertex of the original graph.
If it is not possible to restore correspondences, the output a single number − 1.
Distance between any pair of vertices of the original graph is no less than 10 ⋅ ε, and all coordinates are in the range from − 10 to 10.
1 ≤ N ≤ 5, 1 ≤ V ≤ 2 ⋅ 10^{4}, 0 ≤ E ≤ 2 ⋅ V,
10^{ − 6} ≤ ε ≤ 1
No.  Standard input  Standard output 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Let we have set of the N strings of the same length are consisted by 0 and 1. Next some previously unknown string from this set will be selected, whose index need to guess.
It is required to define optimal in the worst case sequence of compares that allows to recognize index of the input string. Result need presented as decision tree.
Each non leaf node of this tree contains i — position number in which comparison need to perform. It has exactly 2 childs (for each character of the alphabet).
If in the ith position of the string there is a character with the number k, transition to the appropriate subtree where the search will be continued is performed.
Leafs of this tree correspond to terminal states of search and contain indices of recognized strings.
Input data contains N, followed by exactly N strings of the original set.
Output data must contain decision tree written in the next format.
Leaf node starts from symbol '=', followed by string number
(indices of strings starting by zero).
Nonleaf node starts from '>',
followed by position number in which comparison will be performed.
(position starting by zero).
Next the according subtree is written in same way.
It is guaranteed that all strings of the original set are distinct.
Their length does not exceed 32.
2 ≤ N ≤ 16
No.  Standard input  Standard output 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
The equidistant shell of a threedimensional body is the set of points external to it, within a distance of no more than a given δ. Example of equidistant shell of cube with its cross section is presented on picture.
Given an arbitrary convex polyhedron and a value of δ. You program must calculate volume of the equidistant shell.
Input data contains original polyhedron presented in a following format.
First there is the integer V, followed by exactly 3 ⋅ V real numbers that are coordinates of the vertices.
Next, integer E, followed by exactly 2 ⋅ E numbers of the vertices, defining the edges pairwise.
Next is the integer F, followed by exactly F faces represented in the following format.
First integer number of edges N, followed by N indices of edges of this face in an arbitrary order.
Indices of the all elements start from zero.
The floating point value of δ is written at the end of the input data.
Output data must contain the volume with an accuracy of at least 5 digits after decimal point.
All faces are nondegenerate and convex.
Vertex coordinates are in the range from − 10 to 10.
Count of elements of each kind does not exceed 100.
0 ≤ δ ≤ 1
No.  Standard input  Standard output 

1 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Consider some convex fourdimensional polytope that presented by a mesh composed of such elements as vertices, edges, faces and threedimensional bodies.
Each vertex is represented by four coordinates (x, y, z, w). Each edge is a straight line segment and is represented by a pair of vertices connected by it. Each face is a convex polygon and is represented by a set of its edges. Each body is a convex polyhedron and is represented by a set of its faces.
The polytope itself is specified by set of threedimensional bodies bounding it.
You program must calculate volume of a crosssection of the polytope by 3D subspace with w = 0.
Input data contains sequence of the mesh elements.
First there is the integer V, followed by exactly 4 ⋅ V real numbers that are coordinates of the vertices.
Next, integer E, followed by exactly 2 ⋅ E numbers of the vertices, defining the edges pairwise.
Next is the integer F, followed by exactly F faces represented in the following format.
First integer number of edges N, followed by N indices of edges of this face.
The bodies specified by set of their faces are written in the same way.
Indices of the all elements start from zero.
Output data must contain the volume with an accuracy of at least 5 digits after decimal point.
It is guaranteed that all mesh elements are nondegenerate.
Vertex coordinates are in the range from − 10 to 10.
Count of elements of each kind does not exceed 1000.
No.  Standard input  Standard output 

1 


Author:  M. Sporyshev  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  512 Mb  
Output file:  Standard output 
Let we have array of integers a_{i}. You can select in it no more than one number and replace it to other. Cost of this replacement is absolute difference new and old numbers.
It is required to find replacement with a minimum cost, so that a pair of same elements appears in the array of prefix sums of this array.
First line of input data contains single number N — length of the array.
Second line contains the N integers a_{i}.
Output data must contains two integer numbers — index of element for replacement (starting by zero) and signed difference between new and old its values.
If there are many solutions, than output any from them.
2 < N < 100000
a_{i} ≤ 10^{9}
No.  Standard input  Standard output 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Four strings of the same length are composed of four characters ('A', 'B', 'C' and 'D').
Your program must find such a string that Hamming distance from it to any strings of original set is the same.
Moreover, such string must have the same length as the original strings.
If there are many answers, select any string that gives the minimum of distance.
Input data contains four original strings.
Output data must contain answer or empty string, if answer does not exist.
Length of original strings is from 1 to 32.
No.  Standard input  Standard output 

1 


2 


Author:  A. Karabanov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  64 Mb  
Output file:  Standard output 
Timofey was sitting on a math test. His test was completed, he even solved the test of his neighbour, beautiful Alena. Timofey was bored, so he started to draw on checkered sheet of paper.
At first, he drew a square with lines, parallel to sheet sides, and marked all vertices of this square. Then he marked additional a points on the first side of square, b additional points on second side of the square, c additional points on the third side and d aaditional points on the last side. Now he is interested, how many different nondegenerate triangles with vertices in marked points are there?
The only line of input contains four spaceseparated natural numbers: a, b, c ї d.
Print one integer — number of different nondegenerate triangles with vertices in marked points.
0 ≤ a + b + c + d ≤ 1000
No.  Standard input  Standard output 

1 


2 


Author:  A. Baranov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  256 Mb  
Output file:  Standard output 
Grasshopper moves along number line by jumps of integer length. It can jump both to positive and negative directions. Length of each jump can't equal zero.
It is required to calculate count of all different ways that grasshopper can get from point A to point B
making at most N jumps,
whose total length shouldn't exceed some given L.
Since obtained count may be very great, remainder of its division by 10^{9} expected as answer.
Input data contains four integer numbers A, B, N и L.
Output data must contain obtained number.
0 ≤ (B − A) ≤ 20, 1 ≤ N ≤ 40, (B − A) ≤ L ≤ 60
No.  Standard input  Standard output 

1 


2 


Author:  A. Karabanov  Time limit:  1 sec  
Input file:  Standard input  Memory limit:  64 Mb  
Output file:  Standard output 
When Timofey was cleaning garage of his grandfather, he found a strange box under the workbench. There were ceramic plates of different lengths. His father explained to him that it was a measuring device that allowed you to store and transmit a length. The plates are simply placed against each other (their surfaces are polished to such an extent that they hold on to each other without breaking up) until the desired length is reached. Unfortunately, many plates were lost, so now it's possible to have only a limited set of lengths. Timofey wants to find out what is the longest range of consecutive natural numbers that can be obtained from the remaining plates.
The first line contains one integer n — the number of available plates. The second line contains n natural numbers x_{i} — spaceseparated lengths of plates, sorted in nondescending order.
Print one natural number — length of longest range of consecutive natural numbers that can be obtained from the remaining plates.
1 ≤ n ≤ 100
1 ≤ x_{i} ≤ 1000
In the example you are given five plates with lengths 1, 4, 5, 7 and 15. It's possible to obtain lengths [1], [4 .. 13], [15 .. 17], [19 .. 28], [31 .. 32] ([a .. b] means, that it's possible to obtain any length from a to b inclusive). The longest range has length equal to 10, for example range [4 .. 13] or [19 .. 28].
No.  Standard input  Standard output 

1 


Author:  A. Usmanov  Time limit:  1 sec  
Input / output:  interactive  Memory limit:  256 Mb 
This is an interactive problem. You will interact with a server by sending and receiving particular messages.
You are given a complete binary tree of height N having maximum possible number of nodes.
Nodes are numbered from 1 to 2^{N} − 1.
Your task is to determine the number of root. You can perform requests to find least common ancestor (LCA) of any two nodes to achieve this. You are allowed to perform no more than N requests.
The first line contains one integer N — height of the tree.
To make a request print a line "? X Y
",
where X and Y — are integer numbers of nodes.
After such a request you receive one integer —
the number of least common ancestor of these two nodes.
When your program determines the root of the given tree, it should print "! X
" and immediately stop.
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 ≤ 10
1 ≤ X, Y < 2^{N}
The first sample contains the next tree:
No.  Standard input  Standard output 

1 


2 

