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

Задача B. Batteries ≡

Условие

Геологоразведочная партия возвращается из одной экспедиции и сразу же уходит в другую. Для восполнения ресурсов начальник экспедиции радиограммой направил список необходимого оборудования, которое необходимо подготовить.

Тимофей отвечает за обеспечение экспедиции батарейками. В его распоряжении батарейки двух типов: AA и AAA. Заявка, которую он получил, выглядит так: "количество тип" (без пробела). Например, строка "123AA" означает, что геологам требуется 123 батарейки первого типа, а строка "6AAA" означает, что им нужно 6 батареек второго типа.

Наконец, Тимофей получил долгожданную заявку и может приступить к работе. К сожалению, ровно один символ в полученной строке передан с ошибкой. Помогите Тимофею определить наибольшее количество батареек каждого типа, которое может понадобится геологам.

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

Единственная строка входного файла содержит строку s. Гарантируется, что в строке присутствуют только символы из набора "0123456789A". Гарантируется корректность исходного текста радиограммы (в частности, отсутствие ведущих нулей), а также то, что в ней заменен ровно один символ.

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

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

Ограничения

3 ≤ len(s) ≤ 5

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

В первом примере ошибка может быть в первом символе, и тогда исходная заявка (возможно) выглядела так: "923AA" (во втором и третьем символах ошибка тоже возможна, но Тимофею точно следует подготовить не менее 923 батареек первого типа). Также возможно, что вместо еще одного символа "A" передали символ "3" и исходная заявка выглядела так: "12AAA". Тогда Тимофею нужно подготовить не менее 12 батареек второго типа.

Во втором примере заявка может быть подана только на батарейки первого типа, а в третьем — только на батарейки второго типа.

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

123AA

923 12

9AA

8 0

AAAA

0 9

Задача C. Comparison of graph layouts ≡

Условие

Молодой программист Вася занимается N-мерной укладкой графов. В результате работы его алгоритма каждой вершине приписываются координаты в N-мерном пространстве. Однако он не учел, что при сохранении результатов в различных форматах точность может потеряться. Теперь он вынужден изучить полученные файлы, чтобы понять, в каком из них лежит тот или иной граф.

Пусть имеются два графа — исходный и считанный из файла. Из-за особенностей конвертации координаты вершин второго графа могли сместиться, но не более чем на заданное ε. Нумерация вершин также могла измениться.

Требуется сравнить указанные графы и по возможности восстановить соответствие между их вершинами между ними.

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

Во входных данных записано целое число N — размерность пространства, V — количество вершин и E — количество ребер.

После чего следует набор из N ⋅ V координат вершин исходного графа и набор из E его ребер, заданных парой целых чисел. Нумерация вершин начинается с нуля.

Далее аналогичным образом указан второй граф.

В конце входных данных указана используемая точность ε.

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

Выходные данные должны содержать V целых чисел L_i — номер вершины второго графа, соответствующей i-й вершине исходного графа.

Если установить соответствия не представляется возможным, выведите единственное число  − 1.

Ограничения

Вершины исходного графа расположены друг от друга на расстоянии не менее чем 10 ⋅ ε, а их координаты лежат в диапазоне от  − 10 до 10.

1 ≤ N ≤ 5, 1 ≤ V ≤ 2 ⋅ 10⁴, 0 ≤ E ≤ 2 ⋅ V,

10^− 6 ≤ ε  ≤ 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
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

Задача D. Decision tree for matching ≡

Условие

Пусть имеется набор из N строк одинаковой длины, состоящих из нулей и единиц. Далее из указанного набора будет выбрана некоторая заранее неизвестная строка, для которой необходимо угадать ее порядковый номер.

Требуется определить оптимальную в худшем случае последовательность сравнений, позволяющую однозначно распознать номер входной строки. Результат следует представить в виде дерева решений.

Каждый нелистовой узел такого дерева включает в себя номер позиции i, в которой необходимо произвести сравнение, и имеет число потомков, равное числу символов бинарного алфавита.

В случае, если в i-й позиции строки встречается символ с номером k, осуществляется переход в соответствующее поддерево, где и продолжается поиск.

Листы такого дерева соответствуют конечным состояниям поиска и хранят номера распознанных строк.

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

Во входных данных указано число N, за которым следует ровно N строк исходного набора.

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

Выходные данные должны содержать дерево решений, записанное в следующем виде.

Описание листового узла начинается с символа '=', за которым указывается номер строки
(нумерация строк начинается с нуля).

Для нелистового узла вначале идет символ '>',
после чего указан номер позиции, с которой нужно продолжить сравнение
(позиции также нумеруются с нуля).

Далее аналогичным образом записывается соответствующее поддерево.

Ограничения

Гарантируется, что все строки исходного набора различны,
а их длины не превосходят 32.

2 ≤ N ≤ 16

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

5
0010111000
0111101101
0110110001
0011100101
0010111101

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

3
000
111
110

> 2
> 1
= 0
= 2
= 1

Задача E. Equidistant shell ≡

Условие

Эквидистантной оболочкой трехмерного тела называется множество внешних по отношению к нему точек, удаленных от него не более чем на заданное расстояние δ. На рисунке можно видеть пример эквидистантной оболочки для куба, представленной в разрезе.

Даны произвольный выпуклый многогранник и значение δ. Требуется написать программу, вычисляющую объем эквидистантной оболочки.

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

В начале входных данных хранится исходный многогранник, записанный в следующем виде.

Вначале идет целое число V, за которым следует ровно 3 ⋅ V вещественных чисел, задающих координаты вершин.

Далее целое число E, за которым следует ровно 2 ⋅ E номеров вершин, попарно задающих ребра.

Далее идет целое число F, за которым следует ровно F граней, записанных в следующем виде.

Вначале целое число ребер N, за которым следует N номеров ребер этой грани в произвольном порядке.

Нумерация всех указанных элементов начинается с нуля.

В конце входных данных записано вещественное значение δ.

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

Выходные данные должны содержать объем с точностью не менее 5 знаков после запятой.

Ограничения

Все грани являются невырожденными и выпуклыми.

Координаты вершин лежат в диапазоне от  − 10 до 10.

Число элементов каждого вида не превосходит 100.

0 ≤ δ  ≤ 1

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

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

Задача F. Four-dimensional polytope ≡

Условие

Пусть имеется некоторый выпуклый четырехмерный политоп, заданный в виде сетки, составленной из таких топологических элементов, как вершины, ребра, грани и трехмерные тела, для которых выполняются следующие условия.

Каждая вершина такого политопа задается четырьмя своими координатами (x, y, z, w). Каждое ребро представляет собой прямолинейный отрезок и задается парой соединяемых им вершин. Каждая грань представляет собой выпуклый многоугольник и задается набором своих ребер. Каждое тело представляет собой выпуклый многогранник и задается набором своих граней.

Сам политоп задается набором ограничивающих его трехмерных тел.

Требуется написать программу, вычисляющую объем сечения указанного политопа трехмерным подпространством при w = 0.

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

Во входных данных последовательно хранятся наборы сеточных элементов.

Вначале идет целое число V, за которым следует ровно 4 ⋅ V вещественных чисел, задающих координаты вершин.

Далее целое число E, за которым следует ровно 2 ⋅ E номеров вершин, попарно задающих ребра.

Далее идет целое число F, за которым следует ровно F граней, записанных в следующем виде.

Вначале целое число ребер N, за которым следует N номеров этих ребер.

Аналогичным образом записываются тела, заданные номерами своих граней.

Нумерация сеточных элементов каждого вида начинается с нуля.

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

Выходные данные должны содержать объем с точностью не менее 5 знаков после запятой.

Ограничения

Гарантируется, что все сеточные элементы являются невырожденными.

Координаты вершин лежат в диапазоне от  − 10 до 10.

Число элементов каждого вида не превосходит 1000.

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

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

Задача J. Jumps of grasshopper ≡

Условие

Сверчок движется вдоль числовой прямой, совершая скачки целочисленной длины. При этом он может скакать как в положительном, так и в отрицательном направлении. Размер одного скачка не может равняться нулю.

Требуется посчитать число всех различных способов, которыми сверчок может добраться из точки A в точку B, совершив при этом не более N скачков, суммарная длина которых не превосходила бы некоторое заданное L.

Так как полученное число может оказаться слишком большим, в качестве ответа следует вывести остаток от его деления на 10⁹.

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

Во входных данных записаны четыре целых числа A, B, N и L.

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

Выходные данные должны содержать полученное число.

Ограничения

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

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

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

Задача L. LCA queries ≡

Условие

Данная задача является интерактивной и предполагает взаимодействие с сервером путем отправки и приема сообщений определенного вида.

Пусть у нас имеется полное двоичное дерево высоты N, состоящее из максимально возможного числа вершин.

Полагается, что все вершины такого дерева пронумерованы от 1 до 2^N − 1.

Требуется определить номер корневой вершины, оперируя запросами на получение наименьшего общего предка (LCA) двух заданных вершин. Можно сделать не более N запросов.

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

В первой строке входных данных записано одно целое число N — высота дерева.

Протокол взаимодействия

Чтобы сделать запрос, ваша программа должна вывести "? X Y", где X и Y — целые числа, номера вершин. На каждый запрос программа жюри ответит целым числом — номер вершины наименьшего общего предка.

Когда ваша программа определит корень дерева, она должна вывести "! X" и завершиться.

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error". Если ваша программа превысит допустимое количество запросов, то она получит вердикт "Wrong answer".

Каждый запрос и вывод окончательного результата должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Ограничения

1 ≤ N ≤ 10

1 ≤ X, Y < 2^N

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

В первом примере задано дерево:

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

3

2

5

7

? 3 6

? 1 5

? 2 4

! 7

1

! 1