Задача A. Фонари ≡

Условие

На улице длиной в 100 метров установлено N фонарей высотой y₁, y₂, …, y_N метров на расстоянии x₁, x₂, … x_N метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

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

1. N ≤ 2

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

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

Ограничения

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

3
1 1 50 10 51 10

2

Problem B. Lin-log sort 2 ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Problem C. Bucket sort (исправленная) ≡

Statement

Input file format

Output file format

Constraints

Sample tests

4
KVN
ACM
FSB
GGG

ACM
FSB
GGG
KVN

Задача D. Большой линейный коллайдер ≡

Условие

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов "Большой линейный коллайдер" (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон e⁻, либо положительно заряженную частицу — позитрон e⁺. В эксперименте i-я частица исходно размещается в точке с координатой x_i. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: e⁻ частицы перемещаются по направлению уменьшения координаты, а e⁺ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

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

Ученые выбрали m различных моментов времени t₁, t₂, ..., t_m, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени t_j, не должны учитываться при подсчете количества частиц для этого момента времени.

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

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

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа x_i и v_i — координату i-й частицы и ее тип соответственно (x₁ < x₂ < x₃ < ...  < x_n). Частица e⁻ описывается значением v_i =  − 1, а частица e⁺ описывается значением v_i = 1.

Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые. Последняя строка содержит m целых чисел: t₁,t₂,...,t_m.

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

Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.

Ограничения

1 ≤ n, m ≤ 200000

 − 10⁹ ≤ x_i, m ≤ 10⁹

0 ≤ t_i ≤ 10⁹

v_i равно  − 1 или 1

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

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

Получение информации о результатах окончательной проверки

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

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

В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица e⁺ в точке  − 1, частица e⁻ в точке 0, частица e⁺ в точке 1 и частица e⁻ в точке 5.

В момент времени 0.5 первая частица e⁺ и первая частица e⁻ сталкиваются в точке с координатой  − 0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет.

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

4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3

4
2
0
0

Задача 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. Кондиционеры ≡

Условие

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

Все классы школы пронумерованы последовательно от 1 до n. Известно, что для каждого класса с номером i, требуется ровно один кондиционер, мощность которого больше или равна a_i ватт.

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

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

В первом примере нужно купить один единственно возможный кондиционер за 1000 рублей.

Во втором примере оптимально будет установить в первом и втором классах кондиционеры четвертого типа, а в третьем классе — кондиционер третьего типа. Суммарная стоимость этих кондиционеров будет составлять 13 рублей (3 + 3 + 7).

Система оценивания

Частичные решения для n, m ≤ 1000 будут оцениваться из 50 баллов.

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

Первая строка входного файла содержит одно целое число n — количество классов в школе.

Вторая строка содержит n целых чисел a_i — минимальная мощность кондиционера в ваттах, который можно установить в классе с номером i.

Третья строка содержит одно целое число m — количество предложенных моделей кондиционеров.

Далее, в каждой из m строк содержится пара целых чисел b_j и c_j — мощность в ваттах j-й модели кондиционера и его цена в рублях соответственно.

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

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

Ограничения

1 ≤ n ≤ 50 000;

1 ≤ a_i ≤ 1000;

1 ≤ m ≤ 50 000

1 ≤ b_j ≤ 1000, 1 ≤ c_j ≤ 1000;

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

1
800
1
800 1000

1000

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

13

Задача G. k-я порядковая статистика ≡

Условие

K-й порядковой статистикой N-элементного массива называется число А_k, которое будет стоять на K-м месте после сортировки этого массива по возрастанию.

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

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

Ограничения

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

3 2 
2 3 1

2

Задача H. Количество инверсий последовательнсти ≡

Условие

Пара элементов (A_i, A_j) последовательности A_N называется инверсией, если A_i > A_j и i < j.

Напишите программу, которая по заданной последовательности A_N посчитает количество инверсий.

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

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

Последующие N целых чисел задают саму последовательность

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

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

Ограничения

2 ≤ N ≤ 10⁵

0 ≤ A_i ≤ 10⁹

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

7 1 2 5 9 13 16 20

0

9
1 1 2 3 8 6 1 9 9

5

Problem A. Heapsort ≡

Statement

A well known algorithm called heapsort is a deterministic sorting algorithm taking O(n log n) time and O(1) additional memory. Let us describe ascending sorting of an array of different integer numbers.

The algorithm consists of two phases. In the first phase, called heapification, the array of integers to be sorted is converted to a heap. An array a[1…n] of integers is called a heap if for all 1 ≤ i ≤ n the following heap conditions are satisfied:

- if 2i ≤ n then a[i] > a[2i];

- if 2i + 1 ≤ n then a[i] > a[2i + 1].

We can interpret an array as a binary tree, considering children of element a[i] to be a[2i] and a[2i + 1]. In this case the parent of a[i] is a[i div 2], where i div 2 = floor(i / 2). In terms of trees the property of being a heap means that for each node its value is greater than the values of its children.

In the second phase the heap is turned into a sorted array. Because of the heap condition the greatest element in the heapified array is a[1]. Let us exchange it with a[n], now the greatest element of the array is at its correct position in the sorted array. This is called extract-max.

Now let us consider the part of the array a[1 ... n-1]. It may be not a heap because the heap condition may fail for i=1. If it is so (that is, either a[2] or a[3], or both are greater than a[1]) let us exchange the greatest child of a[1] with it, restoring the heap condition for i=1. Now it is possible that the heap condition fails for the position that now contains the former value of a[1]. Apply the same procedure to it, exchanging it with its greatest child. Proceeding so we convert the whole array a[1 ... n-1] to a heap. This procedure is called sifting down. After converting the part a[1 ... n-1] to a heap by sifting, we apply extract-max again, putting second greatest element of the array to a[n-1], and so on.

For example, let us see how the heap a=(5, 4, 2, 1, 3) is converted to a sorted array. Let us make the first extract-max. After that the array turns to (3, 4, 2, 1, 5). Heap condition fails for a[1] = 3 because its child a[2] = 4 is greater than it. Let us sift it down, exchanging a[1] and a[2]. Now the array is (4, 3, 2, 1, 5). The heap condition is satisfied for all elements, so sifting is over. Let us make extract-max again. Now the array turns to (1, 3, 2, 4, 5). Again the heap condition fails for a[1]; exchanging it with its greatest child we get the array (3, 1, 2, 4, 5) which is the correct heap. So we make extract-max and get (2, 1, 3, 4, 5). This time the heap condition is satisfied for all elements, so we make extract-max, getting (1, 2, 3, 4, 5). The leading part of the array is a heap, and the last extract-max finally gives (1, 2, 3, 4, 5).

It is known that heapification can be done in O(n) time. Therefore, the most time consuming operation in heapsort algorithm is sifting, which takes O(n * log (n)) time.

In this problem you have to find a heapified array containing different numbers from 1 to n, such that when converting it to a sorted array, the total number of exchanges in all sifting operations is maximal possible. In the example above the number of exchanges is 1+1+0+0+0 = 2, which is not the maximum. (5, 4, 3, 2, 1) gives the maximal number of 4 exchanges for n=5.

Input file format

Output file format

Constraints

Sample tests

6

6 5 3 2 4 1

Задача B. Жадная последовательность ≡

Условие

Дана последовательность из N целых чисел a_i. Над последовательностью M раз выполняется следующая операция. Из последовательности удаляются два наименьших числа и добавляется в конец число равное сумме двух удаленных. Если наименьших чисел более двух, следует выбрать числа с наименьшими номерами в последовательности.

Требуется написать программу, выводящую последовательность, которая получится после выполнения M операций.

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

Первая строка входного файла содержит целые числа N и M — количество элементов последовательности и количество операций.

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

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

В выходной файл требуется вывести элементы последовательности после M выполнений вышеописанной операции.

Ограничения

1 ≤ M < N ≤ 10⁵

 − 10⁴ ≤ a_i ≤ 10⁴

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

Баллы за подзадачи 1,2 начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Баллы за подзадачу 3 начисляются за каждый пройденный тест, если тесты необходимых подзадач пройдены.

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

4 1
1 2 3 4

3 4 3

4 2
3 2 1 1

3 4

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

Условие

Центральным элементом набора из 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

Перестановки ≡

Условие

Во входном файле задано число n (1 ≤ n ≤ 8). Выведите в выходной файл в лексикографическом порядке все перестановки чисел от 1 до n.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 8).

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

Ограничения

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

3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Задача A. Ответы к тесту ≡

Условие

Крокодил Гена решил поступить в университет. Для поступления ему нужно пройти тест, состоящий из Q вопросов. На каждый из них можно ответить либо "Да", либо "Нет". Количество баллов, получаемых абитуриентом за тест, равно количеству данных им правильных ответов. Все абитуриенты проходят тест с одними и теми же вопросами.

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

По этим данным Гена должен определить правильные ответы.

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

В первой строке входного файла содержатся числа P Q. Далее следует P описаний шушанчиков, по две строки на описание:

• В первой строке описываются ответы, данные шушанчиком. Они задаются строкой длинной Q, состоящей из символов + (ASCII 43) или - (ASCII 45) для ответов "Да" или "Нет" соответственно. На i-ой позиции строки находится ответ на i-ый вопрос.
• Во второй строке содержится целое число — количество баллов.

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

В выходном файле должна содержаться единственная строка, состоящая из Q символов + (ASCII 43) или - (ASCII 45) — правильные ответы к тесту. Если существует несколько вариантов правильных ответов, вывести любой из них. Так, во втором примере допустим также ответ -+++.

Ограничения

1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15

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

1 2
+-
0

-+

3 4
--++
3
----
1
---+
2

+-++

Задача B. Слово из кубиков ≡

Условие

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

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

Ограничения

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

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

Задача C. Сумма с перестановкой ≡

Условие

Заданы три числа: a, b, c. Необходимо выяснить, существуют ли такие числа x и y, что:

1. x получается перестановкой цифр числа a;
2. y получается перестановкой цифр числа b;
3. x и y не содержат лидирующих нулей;
4. x + y = c.

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

Входной файл содержит целые числа a b c.

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

Если искомые числа существуют, вывести в первую строку выходного файла слово YES, а во вторую — числа x y, разделённые пробелом. В противном случае вывести слово NO.

Ограничения

1 < a, b, c < 10⁹

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

12 31 25

YES
12 13

12 31 26

NO

Problem D. Hot-keys ≡

Statement

Input file format

Input file contains number of captions N followed by N lines with captions.

Output file format

Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).

Constraints

1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.

Sample tests

3
yes
no
cancel

&yes
&no
&cancel

4
abc
bca
acb
aaaa

&abc
&bca
a&cb
aaaa

Задача E. Судьба математика ≡

Условие

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

В городе, где они живут, телефонные номера состоят из 6 цифр от 0 до 9 в любой комбинации (например, 000999 — правильный телефонный номер).

Между цифрами номера возможны 6 видов отношений: >, <, =, <=, >=, <>. Например, 2>5 означает, что вторая цифра в номере больше, чем пятая.

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

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

Ограничения

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

1<2
3=1
3>4

12000

Задача F. Слишком много способов ≡

Условие

Однажды школьник Вася пришел в недавно построенное новое здание университета на мастер-класс по информатике. Здание имеет форму куба, составленного из одинаковых аудиторий также кубической формы. Каждой аудитории присвоены три номера x, y, z — порядковые номера по ширине, длине и высоте соответственно. Самая первая аудитория имеет номера 1, 1, 1. Из каждой аудитории можно перейти в любую соседних, имеющих с ней общую стену.

Вася находится в аудитории (x_B, y_B, z_B). Мастер-класс пройдет в аудитории (x_M, y_M, z_M). Вася решил посчитать, сколькими способами можно попасть из текущей аудитории в ту, где проходит мастер-класс, за наименьшее число переходов между аудиториями.

Однако Вася частенько прогуливает мастер-классы и не знает как это сделать, поэтому он отправил смс-ку вам, в надежде, что вы подскажете ему ответ.

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

Входной файл содержит 6 целых чисел x_M y_M z_M x_B y_B z_B.

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

Выходной файл должен содержать единственное целое число — количество способов. Так как ответ на вопрос Васи может быть слишком большим, выведите в его остаток от деления на 10⁹ + 7.

Ограничения

1 ≤ x_M, y_M, z_M, x_B, y_B, z_B ≤ 1000.

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

1 1 1 2 2 2

6

1 1 1 3 3 3

90

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

Условие

Найдите наибольшую общую подпоследовательность двух строк.

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

В первой строке находится первая строка, во второй строке находится вторая строка. Строки состоят только из маленьких латинских букв.

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

Вывести наибольшую общую подпоследовательность. Если решений несколько, вывести любое.

Ограничения

Длина каждой строки не менее 1 и не превосходят 1000.

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

ababaca
acaba

aaba

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

Условие

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

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

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

В первой строке входного файла содержатся числа 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

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

Условие

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

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

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

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

Ограничения

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

5
123 456 124 124 125

3
1 4 5

Problem D. Hall of water life ≡

Statement

The main hall of the Nearsea Institute of Unspecified Underwater Studies has a shape of a long corridor. Along the corridor, there are N aquariums exhibiting various sea creatures. Aquariums are located at distances x₁, …, x_N from the hall entrance (x_i < x_i + 1).

The institute has recently got a new director, who decided that the aquarium maintenance is too costly, and issued an order to remove M (0 ≤ M ≤ N − 2) aquariums.

To minimize the disruption to the looks of the hall, it was decided that:

1. the first and the last aquariums should be left in their places;
2. the maximum distance between the adjacent aquariums must be as small as possible.

Your program must select aquariums for removal in such a way that the above conditions are satisfied.

Input file format

Input file contains integers N M followed by N integers x_i.

Output file format

Output file should contain a single integer — the smallest possible maximum distance.

Constraints

Sample tests

5 2
1 2 3 4 5

2

4 1
10 21 30 40

19

Задача E. Коммивояжёр возвращается! ≡

Условие

Коммивояжёр возвращается в систему Альфы Центавра! Население системы с нетерпением ждёт его прибытия — каждый хочет приобрести что-нибудь с далёких планет!

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

Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!

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

В системе Альфы Центавра n планет. Это число записано в первой строке входного файла. Следующие n строк содержат по n чисел каждая: j-ое число на i-ой из этих строк — стоимость перемещения a_ij от i-ой планеты до j-ой. Числа в каждой строке разделены пробелами. a_ij = -1 означает, что из планеты i нельзя на прямую добраться до планеты j.

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

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

Ограничения

1 ≤ n ≤ 19, a_ij ≤ 10⁸

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

3
-1 1 6
3 -1 7
4 9 -1

5

4
-1 1 1 1
1 -1 1 1
1 1 -1 1
1 1 1 -1

3

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

Условие

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

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

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

Ограничения

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

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

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

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

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

Примечание: на текущий момент возможности CATS не позволяют автоматически распознать алгоритм решения задачи. В этой редакции предлагается решать задачу с использованием скип-листов или хэш-таблиц.

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

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

Ограничения

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

3 2 1 3 0

1 2 3

5 -1 6 -5 5 0

5 6

Задача C. Антон и магазин радиодеталей ≡

Условие

Инженер Антон зашёл в магазин радиодеталей. В магазине ровно N стеллажей. На i-м стеллаже лежат радиодетали типа a_i (на двух различных стеллажах тип радиодеталей может повторяться). Антон обходит с тележкой стеллажи в порядке от первого до N-го.

Когда Антон подходит к очередному стеллажу, он смотрит в тележку. Если в тележке нет радиодеталей такого типа, как на стеллаже, Антон берёт деталь со стеллажа и складывает в тележку. Если радиодеталь такого типа в тележке уже лежит, Антон просто идет дальше.

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

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

Примечание

Рекомендуется рассмотреть частичные решения для N ≤ 1000, a_i ≤ 10⁵.

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

Входной файл содержит целое число два целых числа N и K, вторая строка содержит N чисел a_i.

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

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

Ограничения

1 ≤ N, K ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

3 3 
1 2 3

3

5 2
1 1 1 2 2

2

7 3
8 2 3 1 1 2 2

4

Модули ≡

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

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

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

Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел a_i a_j, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

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

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

Ограничения

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

3 1
2 3

2

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

Условие

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

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

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

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

Ограничения

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

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

9

Задача 2. Бюрократия ≡

Условие

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

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

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

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

Ограничения

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

4 3
1 2
1 3
3 4

1 3 2 4

Problem A. Eulerian cycle ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2
2 3
3 1

1 2 3 1

Problem B. Biconnectivity ≡

Statement

Input file format

Output file format

Constraints

Sample tests

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

1 1

Problem E. 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

Problem F. Fast Dijkstra ≡

Statement

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

Problem G. Ford-Bellman ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3 1
1 2 5
1 3 10
2 3 2

0 5 7

Problem H. Floyd-Warshall ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 5
1 3 10
2 3 2

0 5 7
  0 2
    0

Problem I. SST for sparse graph ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3
1 2 10
2 3 10
3 1 10

20

Задача K. Перехватчик ≡

Условие

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

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

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

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

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

В начале входного файла "input.txt" записаны два натуральных числа: n — число вершин и m — число соединяющих их ребер.

Далее следует набор из m таких ребер, каждое из которых представлено тройкой целых чисел: (a_i, b_i) — номера вершин, w_i — вес ребра. При этом полагается, что нумерация вершин начинается с нуля.

В конце входного файла хранятся три числа f, p₁ и p₂, указывающие номер финишной вершины и стартовые позиции каждого из игроков.

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

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

Ограничения

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

2 ≤ n ≤ 1000, 1 ≤ m ≤ (n ⋅ (n − 1)) / 2,

0 ≤ (a_i, b_i) < n, 0 < w_i ≤ 1000,

p₁ ≠ p₂

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

8 9

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

3
0
5

1
4
7
3

8 9

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

3
0
5

Задача A. Выборы заведующего кафедрой ≡

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

• m_i  — уровень познаний в математике;
• p_i  — уровень познаний в программировании;
• t_i  — преподавательское мастерство;

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

Напишите программу, составляющую список кандидатов на должность заведующего кафедрой.

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

Входной файл содержит натуральное число n  — количество преподавателей. Далее следует n троек натуральных чисел m_i p_i t_i.

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

Требуется вывести в выходной файл номера отобранных преподавателей в порядке возрастания.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

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

4
2 3 4
1 1 3
2 1 8
3 2 10

1 4

Задача B. Доклад с картинками ≡

Условие

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

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

Зная высоту каждой картинки в сантиметрах h_i, определите порядок следования картинок, при котором полученный документ будет иметь наибольшее количество страниц.

В тестовом примере имеется 4 картинки с высотами 6 см, 4 см, 6 см и 4 см. Высота страницы составляет 10 см. Одно из оптимальных решений — расположить картинки в следующем порядке: 4, 4, 6, 6. Тогда первые две картинки окажутся на первой странице, а оставшиеся две картинки займут по одной странице каждая. Таким образом, весь доклад займёт 3 страницы.

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

Входной файл содержит два целых числа — n k, за которыми следуют n целых чисел — h₁… h_n.

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

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

Ограничения

1 ≤ n ≤ 15;

1 ≤ k ≤ 10⁸;

1 ≤ h_i ≤ k;

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

4 10
4 6 4 6

4 4 6 6

Задача C. Лифт ≡

Условие

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

В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й сотрудник подходит к лифту в секунду t_i на этаже a_i, чтобы спуститься на первый этаж.

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

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

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

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

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

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

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

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

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

Первая строка входных данных содержит целые числа n и m — количество людей, вызывающих лифт, и количество этажей в здании.

Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых числа t_i и a_i — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на котором это происходит.

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

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

Ограничения

1 ≤ n ≤ 10⁵, 2 ≤ m ≤ 10⁹

1 ≤ t₁ ≤ t₂ ≤ ...  ≤ t_n ≤ 10⁹, 2 ≤ a_i ≤ m

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

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

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

Использованные в пояснении к примеру обозначения

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

5 4
2 3
2 4
5 2
5 3
9 3

6
12
6
12
12

Задача D. Размещение данных ≡

Условие

Телекоммуникационная сеть крупной IT-компании содержит n серверов, пронумерованных от 1 до n. Некоторые пары серверов соединены двусторонними каналами связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.

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

На рис. 1 показан пример сети и отказоустойчивого множества из серверов с номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При недоступности канала между серверами 1 и 2  — с сервера 4, при недоступности канала между серверами 2 и 3  — с сервера 1. На серверы 3 и 5 при недоступности любого канала связи можно по другим каналам передать данные с сервера 4.

Рис. 1. Пример сети и отказоустойчивого множества серверов.

В рамках проекта группе разработчиков компании необходимо разместить свои данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики хотят продублировать свои данные, разместив их одновременно на нескольких серверах, образующих отказоустойчивое множество. Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов выбора такого множества, и поскольку это количество способов может быть большим, необходимо найти остаток от деления этого количества способов на число 10⁹ + 7.

Требуется написать программу, которая по заданному описанию сети определяет следующие числа: k  — минимальное количество серверов в отказоустойчивом множестве серверов, c  — остаток от деления количества способов выбора отказоустойчивого множества из k серверов на число 10⁹ + 7

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

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

Следующие m строк содержат по два целых числа и описывают каналы связи между серверами. Каждый канал связи задается двумя целыми числами: номерами серверов, которые он соединяет.

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

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

Выведите два целых числа, разделенных пробелом: k  — минимальное число серверов в отказоустойчивом множестве серверов, c  — количество способов выбора отказоустойчивого множества из k серверов, взятое по модулю 10⁹ + 7

Ограничения

2 ≤ n ≤ 200000, 1 ≤ m ≤ 200000

Система оценки и описание подзадач

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

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

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

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

В приведённом примере отказоустойчивыми являются следующие множества из двух серверов: {1, 3}, {1, 4}, {1, 5}.

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

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

2 3

Problem E. Fibonacci level ≡

Statement

For arbitrary non-empty strings S₁ and S₂, the Fibonacci sequence of strings is defined by a recurrence S_i + 2 = S_i + 1 + S_i, where the '+' sign denotes string concatenation.

Let's say that string T has Fibonacci level n if there exists some Fibonacci sequence of strings which contains S_n = T. Note that any string of length 2 or more has Fibonacci level 3.

Your program must, given a string T, find its maximum Fibonacci level n as well as two starting strings S₁ and S₂ of corresponding Fibonacci sequence of strings.

Input file format

Input file contains a single string T, consisting of lowercase Latin letters.

Output file format

Output file must contain 3 lines: integer n followed by strings S₁ and S₂.

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

Constraints

2 ≤ |T| ≤ 10⁶

Sample tests

oxax

3
xax
o

cabccab

5
ab
c

axaxax

4
ax
ax