Задача A. Сложение неотрицательных длинных чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

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

3
5

8

100000000000000000000
29

100000000000000000029

Задача B. Возведение в степень ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

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

3 5

243

10 20

100000000000000000000

Задача C. Умножение неотрицательных длинных чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

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

3
5

15

100000000000000000000
29

2900000000000000000000

Задача D. Привлекательный треугольник ≡

Условие

Назовём отрезок симпатичным, если он параллелен одной из координатных осей. Если в треугольнике хотя бы одна из сторон — симпатичный отрезок, то треугольник также называется симпатичным. Симпатичный треугольник является привлекательным, когда проекции всех его вершин на все прямые, содержащие симпатичные стороны, попадают на эти стороны.

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

1. можно ли по ним построить треугольник (должно выполняться неравенство треугольника),
2. если можно, то является ли он привлекательным,
3. если треугольник привлекательный, то какова его красивость.

Формат входного файла

Во входном файле содержатся целые числа x₁ y₁ x₂ y₂ x₃ y₃, по одному числу в строке. Входной файл также заканчивается переводом строки.

Формат выходного файла

• −1, если треугольник построить невозможно или он не является привлекательным;
• красивость треугольника — в противном случае.

Ограничения

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

-1
-3
5
-1
-1
5

18

-3
-4
-7
-7
4
-4

-1

-3
-3
-1
-7
4
-4

-1

Задача E. Хоттабыч и гирлянда ≡

Условие

Однажды под новый год Гассан Абдуррахман ибн Хоттаб решил помочь Вольке нарядить ёлку. Среди ёлочных украшений Хоттабычу больше всего понравилась гирлянда, состоящая из N цветных лампочек. Приглядевшись, Хоттабыч насчитал K различных цветов лампочек.

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

Рекомендуется рассмотреть частичные решения

• K ≤ 2
• N ≤ 100

Формат входного файла

В первой строке входного файла содержится число N.

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

В N+2-й строке входного файла содержится число M.

В последующих 2*M строчках содержатся запросы Хоттабыча (по две строки на запрос).

Формат выходного файла

Выходной файл должен содержать M чисел — ответы для каждого запроса в порядке поступления.

Если в запросе указан цвет, отсутствующий на гирлянде, то в качестве ответа следует вывести −1.

Если лампочки обоих цветов есть, но пару найти невозможно, следует вывести −2.

Ограничения

2 ≤ N ≤ 15000

1 ≤ M ≤ 20000

1 ≤ K ≤ 3000

Строка, задающая цвет, состоит из латинских букв, её длина не превышает 255 символов.

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

10
Red
Green
Blue
Red
Brown
Green
Yellow
Black
Green
Red
6
Red
Green
Blue
Brown
Yellow
Green
Red
Black
Black
Blue
Orange
Green

0
1
0
1
4
-1

10
B
C
D
F
G
E
R
C
A
G
3
C
G
R
B
E
E

1 5 -2

Задача F. Код Грея ≡

Условие

Дана строка, состоящая из N символов 0 и 1. Требуется построить последовательность из всех возможных строк длиной N, состоящих из 0 и 1, такую что:

• первая строка последовательности — входная строка;
• каждая строка входит в последовательность один раз;
• соседние строки последовательности отличаются друг от друга ровно в одном символе.

Формат входного файла

Во входном файле содержится строка из символов 0 и 1

Формат выходного файла

Выходной файл должен содержать 2^N строк — искомую последовательность.

Ограничения

1 ≤ N ≤ 15

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

1

1
0

110

110
111
101
100
000
001
011
010