Задача A1. Ближайшее число ≡

Условие

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

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

Входной файл содержит целое число N за которым следует N целых чисел a_i - исходная последовательность.

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

В выходной файл необходимо вывести N целых чисел b_i, таких что b_i является ответом на задачу для числа a_i.

Ограничения

1 ≤ N ≤ 10⁶

|a_i| ≤ 10⁹

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

4 1 2 3 4

2 3 4 4

1
1

1

Задача A2. Сбалансированное дерево ≡

Условие

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

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

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

Ограничения

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

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Задача A3. Максимум в скользящем окне ≡

Условие

Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r. Изначально оба они указывают на первый элемент массива. Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

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

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел a_i - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

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

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 10⁵

|a_i| ≤ 10⁹

0 ≤ m ≤ 2n − 2

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

4
-3 -2 -1 0
6
RRRLLL

-2 -1 0 0 0 0

10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL

4 4 4 4 5 8 8 8 8 8 8 6

Задача A4. Золотая середина ≡

Условие

Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер ⌈k / 2⌉, считая с единицы).

Числа добавляются в изначально пустой набор в заданном порядке. Требуется определить значения центрального элемента после добавления каждого числа.

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

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

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

Выходной файл должен содержать n целых чисел — значения центрального элемента после каждого добавления.

Ограничения

1 ≤ n ≤ 10⁶,  − 10⁹ ≤ a_i ≤ 10⁹.

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

3
5 3 4

5 3 4

5
1 2 3 2 4

1 1 2 2 2

Problem A5. Clustering of triangles ≡

Statement

Let there be a set of triangles represented by 3-dimensional vertex coordinates.

You must determine all maximal subsets of triangles such that triangles of each set belong to a single plane.

Input format

Input contains integer N, followed by 9 × N integers, representing vertex coordinates:

(X1i, Y1i, Z1i), (X2i, Y2i, Z2i), (X3i, Y3i, Z3i), where i = 0, 1, …, (N − 1).

Output format

Output must contain the number of subsets M, followed by M records of the following structure.

The number of triangles present in the set, followed by their indices in input (indexing starts at 0).

Both sets and triangles may be output in arbitrary order.

Constraints

It is guaranteed that there are no degenerate (zero area) triangles in input.

 − 1000 ≤ (Xki, Yki, Zki) ≤ 1000,

2 ≤ N ≤ 10⁵.

Sample tests

6

 166  -61 -108
-175  122  133
 -81   96   71

-100 -228  246
 -64   58  -68
 -85   12  -27

 131 -140 -101
  37 -114  -39
  72  -35  -46

 137 -186 -113
  84 -127  -70
  66   11  -34

-140 -143  121
 -45  -73   98
  34   31   25

-135 -170 -173
 -86   45 -252
  39  124   31

3

3 3 2 0
2 4 1
1 5

Задача B1. Лягушка-попрыгун ≡

Условие

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

Сама лягушка может прыгать только одним из следующих способов:

1. Прыгнуть на 2 клетки вверх

2. Прыгнуть на 2 клетки вправо

3. Прыгнуть на 1 клетку по-диагонали

Лягушка не может выходить за границы сетки

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

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

Входные данные состоят из двух чисел, записанных через пробел: N и M

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

Выходные данные должны содержать только одно число - количество способов добраться из нижнего левого угла в верхний правый, взятое по модулю 1000000007

Ограничения

2 ≤ N ≤ 10³

2 ≤ M ≤ 10³

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

3 3

3

5 2

0

4 4

7

Problem B2. Karousel ≡

Statement

Children theme park has opened a new attraction "Karousel" for n persons. According to safety regulations, when the attraction is running, children must be seated so that the center of mass of all riders coincides with the center of carousel and the distances between them alongside the circumference is equal. For example, for n = 6, 2, 3 or 6 children may ride simultaneously, while for n = 5 — only exactly 5. In other words, attraction is allowed to start if it has k children, where k — is a divisor of n and k ≠ 1.

There are d children waiting in the queue for the carousel. After finishing the ride children leave to other attractions. What is the minimum number of runs to let all children ride the carousel once each?

Input format

Two lines of input contain integers n and d.

Output format

Output a single integer — answer to the problem. If it is impossible for all children to get a ride, output -1.

Constraints

1 ≤ (d, n) ≤ 10⁵

Notes on sample

In the first sample n = 16 and d = 14 (16 seats on carousel, 14 children in the queue). It is enough to run carousel 3 times: first time for 8 children, second — for 4, third — for 2.

In the first sample n = 15 and d = 7. It is impossible to let all children ride since according to regulations only 3, 5 or 15 are allowed to ride at a time.

Sample tests

16
14

3

15
7

-1

Задача B3. Наибольшая возрастающая подпоследовательность ≡

Условие

Дана последовательность из N целых чисел. Найдите любую из ее наибольших строго возрастающих подпоследовательностей.

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

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

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

Ограничения

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

5
123 456 124 124 125

3
1 4 5

Задача B4. Свинья-копилка ≡

Условие

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

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

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

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — C_i W_i. Все числа во входном файле — целые.

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

В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то в выходной файл следует записать число  − 1.

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

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

10 110 2
1 1
30 50

60

10 110 2
1 1
50 30

100

1 6 2
10 3
20 4

-1

Problem B5. Discount season ≡

Statement

Vasya has heard that the discount season has started in a shop nearby.

For a single visit to the shop buyer tries to purchase as many items as possible with total weight not greater than W_max, to be able to carry them out with him. There is just one item of every type in the shop. According to discount rules, one client is allowed no more than 3 visits.

You must write a program to calculate optimal sequence of purchases allowing to buy maximum number of items. Total cost of all items must not exceed P_max — the amount of money Vasya has. If several variants with maximum number of items exist, choose one with minimal number of visits.

Input format

Input starts with total number of items n, followed by n pairs of integers: P_i — price of i-th item, W_i — its weight.

Next in the input data are maximum allowed amount of money P_max (total for all visits) and W_max — maximum weight Vasya is able to carry in each visit.

Output format

Output must contain optimal sequence of purchases, described as follows.

First, a total number of visits Vasya has no make. Then for each visit: count of items purchased, followed by item numbers in any order. Items are numbered starting from zero.

If there are several optimal solutions, output any of them.

Constraints

0 < n ≤ 100, 0 < P_i ≤ P_max ≤ 100, 0 < W_i ≤ W_max ≤ 10

Sample tests

12

10 2
10 2
10 8
10 2
5 3
10 2
1 7
10 2
10 4
10 2
1 3
10 2

100 10

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

10

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

24 8

1
5 0 1 2 4 8

Задача B6. Домино (классика) ≡

Условие

Найти количество способов замостить домино 1 × 2 поле n × m.

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

Во входном файле содержатся числа n и m.

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

В выходной файл выведите ответ.

Ограничения

1 ≤ n ≤ 16;

1 ≤ m ≤ 10;

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

2 3

3

Задача C1. Дерево ≡

Условие

Дан неориентированный граф. Проверьте, является ли он деревом.

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

В первой строке входного файла заданы через пробел два целых числа n и m — количество вершин и рёбер в графе, соответственно. В следующих m строках заданы рёбра; i-я из этих строк содержит два целых числа u_i и v_i через пробел — номера концов i-го ребра. Граф не содержит петель и кратных рёбер.

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

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

Ограничения

1 ≤ n ≤ 10⁵

0 ≤ m ≤ 10⁵

1 ≤ u_i, v_i ≤ n

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

3 2
1 2
1 3

YES

3 3
1 2
2 3
3 1

NO

Задача C2. Лабиринт ≡

Условие

Дан квадратный лабиринт, размером N × N, координаты точки входа и точки выхода. Определите минимальное расстояние от входа до выхода.

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

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

В выходном файле должно содержаться единственное число — минимальное расстояние. Лабиринт проходим.

Ограничения

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

4 1 1 4 1
..#.
..#.
..#.
....

9

Problem C3. Dijkstra ≡

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

Output file format

Constraints

Sample tests

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

0 5 7 17 -1

Задача C4. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

Была составлена прямоугольная карта залива, разбитая на ячейки. Левый столбец ячеек примыкает к материку, а правый — к острову. По результатам работ каждая ячейка была помечена символом '#' (по ячейке может проходить водовод) или '.' — водовод по ячейке точно не проходит.

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

Дана карта, составленная по результатам работ. Необходимо определить, можно ли однозначно восстановить водовод по карте.

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

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

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

Если положение водовода может быть однозначно восстановлено, то выведите сначала слово YES, а затем набор чисел, содержащих описание самого водовода. Первое число в описании обозначает количество ячеек водовода, n, за которым следует n пар чисел вида r_i, c_i, обозначающих номер строки и номер столбца очередной ячейки (строки и столбцы нумеруются с единицы).

Если существует несколько способов восстановить положение водовода, то выведите сначала слово MULTIPLE, а затем два различных описания водовода в любом порядке. Если существует более двух вариантов, выведите любые два из них.

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

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

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Задача C5. Слон Пахом и разработка RPG ≡

Условие

Слон Пахом создаёт новую RPG, для игры ему потребовался уровень-лабиринт. Лабиринт содержит n × m платформ, n рядов по m платформ. Платформы бывают трёх видов:

1. Коридоры. В зависимости от ориентации обозначаются или символом "-" (находясь на такой платформе можно, пройти только влево или вправо) или "|" (находясь на такой платформе, можно пройти только вверх или вниз).
2. Перекрёстки. Обозначаются символом "+" (можно пройти в любую сторону).
3. Стены. Обозначаются символом "#" (по ним нельзя пройти).

С платформы на платформу можно перейти, только если платформы стыкуются между собой. Во время похождения по коридору игрок может повернуть платформу, на которой он находится, на 90 градусов и продолжить прохождение в любом направлении, или же оставить платформу нетронутой и пройти дальше.

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

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

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

Первая строка входных данных содержит два целых числа n и m. Следующие n строк содержат по m символов каждая — описание лабиринта.

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

Первая строка выходных данных должна содержать "YES", если лабиринт проходимый, в противном случае "NO".

Если лабиринт проходимый, то следующая строка должна содержать целое число k — минимальное количество поворотов, необходимое для прохождения лабиринта.

Ограничения

1 ≤ n, m ≤ 10³

Описание подзадач и системы оценивания

Решения, работающие для n = 1, оцениваются из 30 баллов. Баллы выставляются за каждый успешно пройденный тест.

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

5 5
+++++
+++++
+++++
+++++
+++++

YES
0

1 8
+-------

YES
0

1 8
+------|

NO

5 6
|-----
|-###-
#|---#
####|#
+++#|-

YES
5

1 1
#

NO

Задача D1. Расстояние от корня ≡

Условие

В заданном корневом дереве найдите вершины, максимально удалённые от корня. Расстоянием между вершинами считается количество рёбер в пути.

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

В первой строке задано n "--- количество вершин в дереве. В следующих n − 1 строках заданы вершины, являющиеся предками вершин 2, 3, …, n. Вершина 1 является корнем дерева.

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

В первой строке выведите максимальное расстояние от корня до остальных вершин дерева.

Во второй строке выведите, сколько вершин дерева находятся от корня на таком расстоянии.

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

Ограничения

1 ≤ n ≤ 10⁵

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

3
1
1

1
2
2 3

3
1
2

2
1
3

Задача D2. Радиус дерева ≡

Условие

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

Напишите программу, принимающую описание дерева и выводящую радиус дерева.

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

Входной файл содержит целое число N, за которым следует N − 1 описаний рёбер. Описание ребра номер i содержит два целых числа u_i v_i — номера вершин, которые соединены этим ребром.

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

Выходной файл должен содержать единственное целое число — радиус дерева.

Ограничения

2 ≤ N ≤ 10⁵, 1 ≤ u_i, v_i ≤ N.

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

2
1 2

1

3
1 2
1 3

1

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

2

Задача D3. Листовая медиана ≡

Условие

Деревом называется связный неориентированный граф без циклов. Для заданного дерева требуется выбрать такую вершину, чтобы суммарное расстояние от неё до всех листьев было максимальным.

Напишите программу, принимающую описание дерева и выводящую вершину с максимальным суммарным расстоянием до листьев. Если таких вершин несколько, выведите минимальную по номеру.

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

Входной файл содержит целое число N, за которым следует N − 1 описаний рёбер. Описание ребра номер i содержит два целых числа u_i v_i — номера вершин, которые соединены этим ребром.

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

Выходной файл должен содержать единственное целое число — номер искомой вершины.

Ограничения

2 ≤ N ≤ 10⁵, 1 ≤ u_i, v_i ≤ N.

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

2
1 2

1

3
1 2
1 3

1

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

3

Задача D4. Удлинители ≡

Условие

В компьютерном классе имеется одна розетка. Для того, чтобы подключить к ней компьютеры, используется N + 1 удлинителей. Один из удлинителей включается розетку, а каждый из остальных N — в другой удлинитель. При этом гарантируется, что каждый удлинитель в конце концов подключен к розетке.

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

Назовём электрическим расстоянием от удлинителя до розетки количество удлинителей, которые должен пройти электрический ток от данного удлинителя до розетки.

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

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

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

Входной файла содержит целые числа N K, за которыми следуют N чисел p_i, где p_i — номер удлинителя, к которому подключен i-й удлинитель, i = 1… N. К розетке подключен удлинитель номер 0.

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

Выходной файл должен содержать два целых числа S T, означающие, что удлинитель номер S следует отключить от удлинителя номер p_S и подключить к удлинителю номер T. Если оптимальных решений несколько, выведите любое из них.

Ограничения

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

6 2
0 1 2 1 6 0

3 6

1 5
0

1 0

Задача E1. Простые числа ≡

Условие

Необходимо вывести N простых чисел в порядке их возрастания.

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

Входной файл содержит одно целое неотрицательное число N.

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

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

Ограничения

0 ≤ N ≤ 1000

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

1

2

3

2 3 5

Задача E2. НОД и НОК ≡

Условие

Необходимо вычислить НОД и НОК для пары целых положительных чисел a и b.

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

Входной файл содержит два целых положительных числа.

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

Выходной файл должен содержать НОД и НОК пары чисел.

Ограничения

1 ≤ a,b ≤ 10⁶

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

2 3

1 6

24 28

4 168

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

Условие

Даны три числа: A, N, P. Требуется возвести число A в степень N по модулю P.

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

Три целых положительных числа: A N P

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

Выходные данные должны содержать единственное число - A^N

Ограничения

0 < A, N < 2⁶⁴

2 ≤ P < 2³²

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

2 2 3

1

2 4 10

6

5 7 3

2