Problem A. Ascending arrays ≡

Statement

There are three strictly increasing arrays of integers A₁, A₂, A₃ with lengths N₁, N₂, N₃.

Your program must find the count of triples of the same numbers simultaneously occurring in each of these arrays.

Input format

First line contains N₁, N₂, N₃.

Second line contains A₁₁, A₁₂, ..., A_1N1

Third line contains A₂₁, A₂₂, ..., A_2N2

Fourth line contains A₃₁, A₃₂, ..., A_3N3

Output format

Constraints

1 ≤ N₁, N₂, N₃ ≤ 10⁵

0 ≤ A_{i j} ≤ 10⁹

Sample tests

5 4 3
2 3 4 5 7
1 2 3 4
2 3 4

3

5 4 3
2 3 4 5 7
1 2 4 7
1 3 5

0

Problem B. Batteries ≡

Statement

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.

Input format

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.

Output format

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.

Constraints

3 ≤ len(s) ≤ 5

Explanation of the samples

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.

Sample tests

123AA

923 12

9AA

8 0

AAAA

0 9

Problem C. Comparison of graph layouts ≡

Statement

Young programmer Vasya is engaged in N-dimensional graph layout. As a result of the work of his algorithm, each vertex is assigned coordinates in the N-dimensional 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 format

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 format

Output data must contain V integers L_i — index of the second graph vertex corresponding to i-th vertex of the original graph.

If it is not possible to restore correspondences, the output a single number  − 1.

Constraints

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⁴, 0 ≤ E ≤ 2 ⋅ V,

10^− 6 ≤ ε  ≤ 1

Sample tests

3 4 5

-1.15000  3.50000 -5.03000
-5.67000  9.10000  6.10000
 4.20000  3.65000 -4.23000
 1.05000  3.50000 -5.00000

0 1
1 2
2 3
3 0
0 2

-5.67040  9.10372  6.10903
 1.05189  3.50070 -5.00731
-1.15060  3.50870 -5.03701
 4.20300  3.65001 -4.23079

0 3
2 0
3 1
2 3
1 2

0.1

2
0
3
1

3 4 5

-1.15000  3.50000 -5.03000
-5.67000  9.10000  6.10000
 4.20000  3.65000 -4.23000
 1.05000  3.50000 -5.00000

0 1
1 2
2 3
3 0
0 2

-5.67040  9.10372  6.10903
 1.05189  3.50070 -5.00731
-1.15060  3.50870 -5.03701
 4.20300  3.65001 -4.23079

0 3
2 0
3 1
0 1
1 2

0.1

-1

Problem D. Decision tree for matching ≡

Statement

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 i-th 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 format

Input data contains N, followed by exactly N strings of the original set.

Output format

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).

Non-leaf 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.

Constraints

It is guaranteed that all strings of the original set are distinct.
Their length does not exceed 32.

2 ≤ N ≤ 16

Sample tests

5
0010111000
0111101101
0110110001
0011100101
0010111101

> 9
= 0
> 6
> 7
= 2
= 3
> 5
= 1
= 4

3
000
111
110

> 2
> 1
= 0
= 2
= 1

Problem E. Equidistant shell ≡

Statement

The equidistant shell of a three-dimensional 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 format

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 format

Output data must contain the volume with an accuracy of at least 5 digits after decimal point.

Constraints

All faces are non-degenerate and convex.

Vertex coordinates are in the range from  − 10 to 10.

Count of elements of each kind does not exceed 100.

0 ≤ δ  ≤ 1

Sample tests

8
-1.00000 -1.00000 -1.00000
 1.00000 -1.00000 -1.00000
-1.00000  1.00000 -1.00000
 1.00000  1.00000 -1.00000
-1.00000 -1.00000  1.00000
 1.00000 -1.00000  1.00000
-1.00000  1.00000  1.00000
 1.00000  1.00000  1.00000

12
1 0
2 0
4 0
3 1
5 1
3 2
6 2
7 3
5 4
6 4
7 5
7 6

6
4 3 5 1 0
4 4 8 2 0
4 6 9 2 1
4 7 4 10 3
4 7 11 6 5
4 10 11 9 8

0.25

7.24355

Problem F. Four-dimensional polytope ≡

Statement

Consider some convex four-dimensional polytope that presented by a mesh composed of such elements as vertices, edges, faces and three-dimensional 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 three-dimensional bodies bounding it.

You program must calculate volume of a cross-section of the polytope by 3D sub-space with w = 0.

Input format

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 format

Output data must contain the volume with an accuracy of at least 5 digits after decimal point.

Constraints

It is guaranteed that all mesh elements are non-degenerate.

Vertex coordinates are in the range from  − 10 to 10.

Count of elements of each kind does not exceed 1000.

Sample tests

5
-1.00000 -1.00000 -1.00000 -0.50000
 0.00000  1.00000 -1.00000 -0.50000
 1.00000  0.00000 -1.00000 -0.50000
 0.00000  0.00000  1.00000 -0.50000
 0.00000  0.00000  0.00000  0.50000

10
0 1
0 2
0 3
1 2
1 3
2 3
0 4
1 4
2 4
3 4

10
3 0 1 3
3 1 2 5
3 0 2 4
3 3 4 5
3 0 6 7
3 1 6 8
3 2 6 9
3 3 7 8
3 4 7 9
3 5 8 9

5
4 0 1 2 3
4 0 4 5 7
4 1 5 6 9
4 2 4 6 8
4 3 7 8 9

0.12500

Задача G. Greedy replacement ≡

Условие

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⁹

Примеры тестов

2
1 1

1 -1

3
1 2 -3

2 1

Problem H. Hamming sphere ≡

Statement

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 format

Input data contains four original strings.

Output format

Output data must contain answer or empty string, if answer does not exist.

Constraints

Length of original strings is from 1 to 32.

Sample tests

ABCDABCD
AABBAABB
AACCABCD
ABCDCCDD

AABDCACD

AAA
CBC
BCD
DDB

Задача I. Inner triangles ≡

Условие

Как-то раз Тимофей сидел на контрольной работе по математике. И свой вариант, и вариант соседки по парте, красавицы Алёны, давно были решены. От скуки Тимофей стал рисовать на клетчатом листочке-черновике.

Сперва от нарисовал большой квадрат со сторонами, лежащими на линиях клетчатой сетки и отметил все его вершины. Потом дополнительно отметил a точек на одной стороне квадрата, b на второй, c на третьей и d на четвертой. Теперь его интересует вопрос — сколько существует различных невырожденных треугольников с вершинами, лежащими в отмеченных точках?

Формат входных данных

Единственная строка входного файла содержит четыре натуральных числа, записанных через пробел: a, b, c и d.

Формат выходных данных

Выведите натуральное число — ответ на задачу.

Ограничения

0 ≤ a + b + c + d ≤ 1000

Пояснение к первому примеру

Примеры тестов

1 0 0 0

9

1 2 3 4

329

Problem J. Jumps of grasshopper ≡

Statement

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⁹ expected as answer.

Input format

Input data contains four integer numbers A, B, N и L.

Output format

Output data must contain obtained number.

Constraints

0 ≤ (B − A) ≤ 20, 1 ≤ N ≤ 40, (B − A) ≤ L ≤ 60

Sample tests

0 10 20 40

35498634

1 1 2 2

3

Задача K. Kit of gauge blocks ≡

Условие

Разбирая дедушкин гараж, Тимофей нашел под верстаком странную коробочку с керамическими пластинками разной длины. Папа объяснил ему, что это измерительный прибор, позволяющий сохранять и передавать меру длины. Пластинки просто приставляют друг к другу (их поверхности отполированы до такой степени, что держатся друг за дружку не распадаясь), пока не наберется нужная длина. К сожалению, многие пластинки оказались потеряны, поэтому теперь можно собрать лишь ограниченный набор различных длин. Тимофей хочет узнать, каков наиболее длинный диапазон последовательных натуральных значений, которые можно получить из оставшихся пластин.

Формат входных данных

Первая строка входного файла содержит натуральное число n — количество оставшихся пластин. Вторая строка содержит n натуральных чисел x_i — длины пластин, записанных через пробел в порядке не убывания.

Формат выходных данных

Выведите одно натуральное число — ответ на задачу.

Ограничения

1 ≤ n ≤ 100

1 ≤ x_i ≤ 1000

Пояснение к примеру

В примере дано пять пластинок длиной 1, 4, 5, 7 и 15. Из них можно составить длины [1], [4 .. 13], [15 .. 17], [19 .. 28], [31 .. 32] (числа в квадратных скобках [a .. b] означают, что возможно собрать любую длину от a до b включительно). Наиболее длинный диапазон последовательных натуральных значений равен 10, он достигается дважды для [4 .. 13] и [19 .. 28].

Примеры тестов

5
1 4 5 7 15

10

Problem L. LCA queries ≡

Statement

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.

Input format

The first line contains one integer N — height of the tree.

Interaction protocol

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 end-of-line (\n). Output buffers must be flushed after every line:

Constraints

1 ≤ N ≤ 10

1 ≤ X, Y < 2^N

Explanation of the samples

The first sample contains the next tree:

Sample tests

3

2

5

7

? 3 6

? 1 5

? 2 4

! 7

1

! 1