Задача 1. Дошкольная сортировка ≡

Условие

Когда юному программисту Васе было три года, он уже знал, что буквы бывают "маленькие" (a, b, c, ..., z) и "большие" (A, B, C, ... Z), но ещё не выучил порядок букв в алфавите.

Мама играла с Васей в игру: она выписывала последовательность маленьких и больших букв, и спрашивала, "в порядке ли они". Если в последовательности шли сначала только маленькие буквы, а потом только большие, Вася отвечал YES (как будущий программист, он уже начал учить английские слова). Если в последовательности маленькие и большие буквы были перемешаны, Вася отвечал NO.

Напишите программу, которая будет действовать как Вася.

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

Входной файл содержит строку из больших и маленьких латинских букв.

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

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

Ограничения

Длина входной строки от 1 до 10 символов.

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

maMA

YES

pRograMma

NO

zzzz

YES

AA

YES

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

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

Условие

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

Задача 4. Топологическая сортировка ≡

Условие

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

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

Ограничения

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

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

2 4 3 5 6 1

Problem A. Altitude and visibility ≡

Statement

Consider a sequence of numbers a₁, …, a_N, representing heights. Let's say that element a_i has a visibility radius d if a_i ≥ a_j for all j such that 1 ≤ j ≤ N and |i − j| < d.

You task is to find maximum d_i for every a_i.

Input file format

Input file contains integer N followed by N integers a_i.

Output file format

Output file must contain N integers d_i — maximum visibility for every a_i. If maximum visibility radius for element a_i is unlimited, output d_i = 0.

Constraints

1 ≤ N ≤ 10⁶, 0 ≤ a_i ≤ 10⁹

Sample tests

1
10

0 

6
1 5 2 2 1 4

1 0 1 2 1 4 

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 C. Bucket sort (LETTERS ONLY) ≡

Statement

Input file format

Output file format

Constraints

Sample tests

4
KVN
ACM
FSB
GGG

ACM
FSB
GGG
KVN

Problem D. Caterpillar ≡

Statement

A caterpillar of length L crawls over rough terrain. Rough terrain can be represented as a one-dimensional array of N cells with different heights. A cell a_i is called a downhill if a_i > a_i + 1. A cell a_i is called an uphill if a_i < a_i + 1. Initially, the caterpillar occupies the first L cells.

In order to advance one cell, the caterpillar spends 1 second of time. However, if it occupies more downhills than uphills, and the head of the caterpillar is on the downhill, it immediately moves one cell to the right.

Determine after how many seconds the head of the caterpillar reaches the last cell.

Input format

The first line of the input file contains two integers L, N. The second line contains N integers a_i.

Output format

The output must contain one integer — time after which the caterpillar reaches the last cell.

Constraints

1 ≤ a_i, N, L ≤ 10⁶, L ≤ N, a_i ≠ a_i + 1

Sample tests

1 4
4 3 2 3

1

3 10
10 9 8 7 8 9 10 9 8 7

4

Problem E. 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 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. 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 H. 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 J. 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. Автомобильные номера ≡

Условие

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

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

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

Напомним, что автомобильные номера в России состоят из трех букв и трех цифр, упорядоченных следующим образом: буква, три цифры, затем две буквы. Фрагмент номера, который идентифицирует регион, в котором зарегистрирован автомобиль, мы будем игнорировать.

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

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

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

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

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

X772KX

9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача M. Бутылка на всех ≡

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

Задача N. Быстрая помощь ≡

Условие

В городе В случилась катастрофа: неожиданно наступила зима. Чтобы облегчить судьбу жителей В, из города М решено направить N самолётов с тёплой одеждой.

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности a_i минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

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

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

Требуется определить минимальное время в минутах, требуемое на перелёт и разгрузку всех самолётов.

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

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

Ограничения

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

2 10
8 5

25

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

Условие

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

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

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

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

Ограничения

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

4 3
1 2
1 3
3 4

1 3 2 4

Задача P. Гражданская оборона ≡

Условие

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

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

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

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

Третья строка входного файла содержит число m — количество бомбоубежищ. Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища.

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

Выведите в выходной файл n чисел — для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входном файле.

Ограничения

1 ≤ n, m ≤ 100000

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

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

4
1 2 6 10
2
7 3

2 2 1 1

Задача T. Конвертер графов ≡

Условие

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

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

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

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

• edges — список ребер. В этом случае первая строка описания графа должна содержать два целых числа N, M — количество вершин и количество ребер соответственно. Далее каждая следующая строка содержит два числа u и v — начало и конец очередного ребра.
• lists — списки смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее i-я строка (начиная со второй) содержит описание списка смежности (i − 1)-й вершины. Первое целое число в строке c_i — количество вершин, в которые выходят ребра из (i − 1)-й вершины. Далее через пробел следует c_i целых чисел — номера вершин, в которые выходят ребра из (i − 1)-й.
• mat — матрица смежности. В этом случае первая строка описания графа должна содержать целое число N — количество вершин графа. Далее следует N строк по N чисел 0 или 1 — описание матрицы смежности. Если в i-й строке на j-й позиции находится единичка, значит в графе есть ребро из (i − 1)-й вершины в j-ю.

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

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

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ N²

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

edges mat
3 4
1 2
2 3
1 3
2 2

3
0 1 1
0 1 1
0 0 0

mat lists
4
1 0 1 1
0 0 0 0
1 1 0 0
0 1 1 0

4
3 1 3 4
0
2 1 2
2 2 3