Восстановление дерева

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 32768 KB.

ввод: input.txt
вывод: output.txt

 

На доске было нарисованно неориентированное N-вершинное дерево. В ходе лекции по алгоритмам на графы для этого дерева были выписаны две последовательности:
1) перестановка вершин, соответствующая порядку в котором вершины попадают в очередь при запуске поиска в ширину из вершины 1;
2) перестановка вершин, соответствующая порядку в котором вершины начинают обрабатываться при поиске в глубину из вершины 1.
Оба поиска написаны так, что окружение каждой вершины перебирается в порядке возрастания номеров.

Входные данные

В первой строке записано натуральное N (1 <= N <= 200).
Во второй строке записана перестановка, соответствующая поиску в ширину; в третьей -- поиску в глубину.

Выходные данные

Выведите N-1 пару вершин, описывающую все ребра дерева. Пары и числа в парах разделяйте пробелами и/или переводами строк. Если решений несколько, выведите любое.

Пример

Ввод

5
1 2 3 4 5
1 2 4 5 3

Вывод

1 2
4 2
2 5
1 3

Палиндромы

ограничение времени на тест: 5 сек.
ограничение памяти на тест: 131072 KB.

ввод: input.txt
вывод: output.txt

 

Строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Например, abba - палиндром, а omax - нет. Для строки A будем обозначать A[i,j] ее подстроку длины j - i + 1 с i-й по j-ю позицию включительно (позиции нумеруются с 1).
Для заданной строки A длины N (1 <= N <= 100000) требуется подсчитать число Q пар (i,j), 1 <= i < j <= N, таких что A[i,j] является палиндромом.

Входные данные

Входной файл содержит одну строку A длины N, состоящую из маленьких латинских букв.

Выходные данные

В выходной файл выведите искомое число Q.

Пример

Ввод

Test #1
aaa

Test #2
abba

Test #3
omax

Вывод

Test #1
3

Test #2
2

Test #3
0

Общая подстрока

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

Заданы две строки, состоящие из 0 и 1. Рассмотрим все строки, которые являются подстроками обеих данных строк. Найдите среди них k-ую в лексикографическом порядке.
Строка S меньше строки T в лексикографическом порядке, если выполняется одно из двух условий:
- S является префиксом T;
- существует i, не превышающее длин строк S и T, такое что для j < i выполняется S [j] = T [j] и S [i] < T [i].

Входные данные

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

Выходные данные

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

Пример

Ввод

0100
0010
3

Вывод

01

Писатель

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 8192 KB.

ввод: input.txt
вывод: output.txt

 

Молодой писатель, наконец, закончил работу над текстом своего первого романа. Несомненно, это произведение прославит его в веках. Роман написан в жанре сюрреалистической постаппокалептической антиутопии. Для усиления масштабности романа он решил добавить интересный, интригующий эпиграф. Автор выбрал как эпиграф последовательность всех различных подстрок названия. Подстрокой он называл любую непустую последовательность идущих подряд символов из названия романа. Вам же он доверил не столь творческую работу. Он попросил Вас найти длину получившегося эпиграфа.

Входные данные

Во входном файле записано название романа - последовательность больших и малых латинских букв. Длина названия не превышает 8000 символов.

Выходные данные

Выведите единственное целое число - длину эпиграфа.

Пример

Ввод

BOBR

Вывод

19

Подстрочки

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 16384 KB.

ввод: input.txt
вывод: output.txt

 

В строке из 0 и 1 посчитать количество различных подстрок (не считая пустой).

Входные данные

Входной файл состоит из символов 0, 1 и пробельных символов (пробельные символы - это пробелы, символы табуляции и переводы строки). Пробельные символы должны игнорироваться. Общее число нулей и единиц не превышает 100000.

Выходные данные

В выходной файл вывести одно число, являющееся ответом задачи.

Пример

Ввод

Test #1
0 0 0
0000

Test #2
01011

Вывод

Test #1
7

Test #2
11

Гадание

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Девочка Катя очень любит гадать. Недавно ей встретился новый, интересный способ гадания. Гадают на то, какие отношения ждут с тем или иным человеком. Гадание осуществляется в несколько этапов. Сначала, загадывают имя человека, на которого гадают (длина имени должна быть не более 10 букв). Затем произвольно составляется таблица размерности NxM из K цифр от 1 до 9. Последний ряд таблицы может быть заполнен не полностью. После этого, в таблице вычеркиваются пары чисел, стоящие рядом по вертикали или горизонтали в сумме дающие P. После того, как вычеркнули все возможные пары, оставшиеся числа выписываются слева на право в новую таблицу, количество столбцов в которой, равно длине загаданного имени. Из полученной таблицы по тем же правилам вычеркиваются пары чисел, также дающие в сумме P. Далее опять составляется таблица шириной в длину загаданного имени. И так делается до тех пор, пока не останется таблица, из которой больше нельзя ничего вычеркнуть (это может быть и первая таблица, если в ней ничего нельзя вычеркнуть). В такой таблице девочка Катя находит сумму оставшихся цифр. Потом, она нумерует буквы загаданного имени от 1-го до полученной суммы, переходя от последней буквы к первой по кругу (например, в имени Андрей 9-ой буквой будет буква "д"). Именно по этой букве и осуществляется толкование.
Особенность этого гадания состоит в том, что, для того, чтобы получить наиболее правдивое толкование необходимо в каждой таблице вычеркивать максимальное количество пар.
У девочки Кати очень много знакомых людей, на имена которых она хотела бы погадать. И так как гадание весьма трудоемкое, она хотела бы иметь специальную программу, которая по заданному имени и первоначальной таблице выдавала бы найденную букву, а также пары вычеркиваемых чисел в формате "<номер строки 1 числа>, <номер столбца 1 числа>; <номер строки 2 числа>, <номер столбца 2 числа>". Не поможете ли вы девочке Кате?

Входные данные

В первой строке записано загаданное имя. Во второй строке через пробел записаны числа N (1<=N<=10) - количество столбцов, M (1<=M<=10) - количество строк, K (1<=K<=N*M) - количество чисел и P (1<=P<=18). В следующих M строках идет описание таблицы, придуманной девочкой Катей. Цифры в таблице записываются через пробел. В первоначальной таблице последний ряд может быть заполнен не полностью.

Выходные данные

Выведите в первой строке букву для толкования. Далее, на следующей строке выведите через пробел количества вычеркиваемых пар в каждой новой таблице (за исключением количества равного 0). А далее все вычеркиваемые пары в произвольном порядке, в заданном формате. Каждая новая пара должна быть на новой строке. Перечень пар для одной таблицы должен отделяется от перечня для другой пустой строкой.
Если в какой либо таблице в ходе гадания можно будет парами вычеркнуть все числа, то вместо искомой буквы выведите фразу "It is your best friend!". А если существует несколько решений - выведите любое.

Пример

Ввод

Test1
Andrew
6 3 17 6
5 1 3 2 1 7
4 6 2 4 5 3
2 4 5 1 3

Test2
Roman
4 3 12 7
2 3 4 5
1 2 5 6
3 1 6 4

Вывод

Test1
r
5 1
1,1; 1,2
1,5; 2,5
2,4; 1,4
3,1; 2,1
3,3; 3,4

1,1; 2,1

Test2
It is your best friend!
3 2 1
1,3; 1,2
2,2; 2,3
3,3; 3,2

1,1; 1,2
1,3; 1,4

1,1; 1,2