Square sort

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 3000. Sequence elements are less than 109 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 4 3 10 3 1
1 3 3 4 10

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

Author:StdAlg   Time limit:3 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives a sequence of words and sorts it in lexicographical order. Linear order on characters is given by ASCII codes.

Input file format

First line of input file contains integer N — the sequence length. Following N lines contain one word per line. Each word is exactly three letters long.

Output file format

Output file must consist of N lines, each containing one word from sorted sequence.

Constraints

0 ≤ N ≤ 1000000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
KVN
ACM
FSB
GGG
ACM
FSB
GGG
KVN

Задача 2. Сортировка подсчетом

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

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

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

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

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

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

Ограничения

0 ≤ N ≤ 100000, все числа находятся в диапазоне от 1 до 100000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 1
3 2 
2 3
3 4
1 3 2 4

Задача 3. Сортировка чисел

Автор:A. Klenin   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Дана последовательность из N целых чисел A1, ..., AN. Требуется отсортировать её по возрастанию.

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

Файл сожержит число N, за которым следует N чисел A1 ... AN

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

Файл должен содержать N чисел, отсоритрованных по возрастанию.

Ограничения

1 ≤ N ≤ 1000000, −231Ai ≤ 231−1.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 2 1
1 2 3
2
4
5 6 5 6
5 5 6 6

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

Автор:А. Жуплев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 15000

1 ≤ M ≤ 20000

1 ≤ K ≤ 3000

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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
2
10
B
C
D
F
G
E
R
C
A
G
3
C
G
R
B
E
E
1 5 -2

Задача 5. K-ая порядковая статистика

Автор:StdAlg   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Последовательность AN задаётся следующим образом. A1 = P, Ai = (Ai − 1 ⋅ Q) mod V.

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

Во входном файле содержатся целые числа Q V P N K

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

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

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 231 − 1

1 ≤ K ≤ N ≤ 4 ⋅ 107

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

Входной файл (input.txt) Выходной файл (output.txt)
1
343 32767 3 10 7
16478

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

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 105

0 ≤ Ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 1 2 5 9 13 16 20
0
2
9
1 1 2 3 8 6 1 9 9
5

Задача 7. Куча максимумов

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

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

Входной файл содержит числа N K, за которыми следуют N чисел — исходные данные задачи. Все числа целые.

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

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

Ограничения

1 ≤ N ≤ 106, 1 ≤ K ≤ min(N, 105),  − 231 ≤ Ai ≤ 231

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 
1 2 3
2 3

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

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ M < N ≤ 105

 − 104 ≤ ai ≤ 104

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
nm
1202 ≤ n ≤ 5m < nполная
2202 ≤ n ≤ 1000m < n1полная
3602 ≤ n ≤ 105m < n1,2полная

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1
1 2 3 4
3 4 3
2
4 2
3 2 1 1
3 4

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

Автор:И. Бураго   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 106,  − 109 ≤ ai ≤ 109.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 3 4
5 3 4
2
5
1 2 3 2 4
1 1 2 2 2

Problem A. Heapsort

Author:Andrew Stankevich (original idea, text, solution)   Time limit:2 sec
Input file:heapsort.in   Memory limit:64 Mb
Output file:heapsort.out  

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 2in 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

Input file contains n.

Output file format

Output the array containing n different integer numbers from 1 to n, such that it is a heap, and when converting it to a sorted array, the total number of exchanges in sifting operations is maximal possible. Separate numbers by spaces.

Constraints

1 ≤ n ≤ 50000

Sample tests

No. Input file (heapsort.in) Output file (heapsort.out)
1
6
6 5 3 2 4 1

Задача B. Knapsack problem

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

Дана последовательность из N целых чисел. Найдите любую из ее подпоследовательностей, сумма элементов которой равна w, либо установите, что искомой подпоследовательности не существует.

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

Во входном файле находятся числа N и w, а за ними следует последовательность из N целых чисел ai.

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

Если искомая подпоследовательность существует, выведите N чисел 0 или 1, разделенных пробелами. Единица на позиции i означает, что элемент последовательности ai принадлежит найденной подпоследовательности, 0 означает обратное. В противном случае выведите  − 1.

Ограничения

1 ≤ N ≤ 40, 0 ≤ ai,w ≤ 10000000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 7
1 5 6
1 0 1

Задача C. Две кучки

Автор:М. Спорышев   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 20 1 ≤ Wi ≤ 100000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 1 2 3 4
0

Задача D. Двойные тетради Чебурашки

Автор:C. Пак   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

У Чебурашки есть NS одинарных и ND двойных тетрадей. Все одинарные тетради имеют вес WS, а все двойные — вес WD. Чебурашка учится N дней в неделю. Он изучает M предметов, пронумерованных от 1 от M. Вес, который Чебурашке придётся перенести за один день, равен сумме весов всех тетрадей, которые он должен будет взять.

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

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

Во входном файле содержатся числа N M NS ND WS WD. Далее следует расписание, состоящее из N дней. Каждый день описывается одной строкой. В начале строки содержится Ki — число уроков в i-ый день, за которым следует Ki чисел — номера предметов. Все числа во входном файле целые.

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

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

Ограничения

0 ≤ N ≤ 6

0 ≤ M ≤ 10

0 ≤ WS, WD ≤ 109

0 ≤ K1 + K2 + …  + KN ≤ 15

2 × ND + NS = M

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 4 0 2 2 2
2 1 2
2 3 4
2 1 2
2 3 4
8
2
4 4 2 1 0 2
2 1 2
2 3 4
2 1 2
2 3 4
4

Задача E. Барбара

Автор:A. Klenin   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

На некотором языке все слова записываются заглавными латинскими буквами, и состоят из слогов. Слогом называется непустая последовательность согласных, заканчивающаяся гласной. Все остальные последовательности букв словами этого языка не являются. Например, слово BARBARA состоит из трех слогов — BA, RBA и RA. Последовательности букв ААХ, Е, К, АНА словами не являются. Осмысленными считаются слова, в которых все согласные различны.

По данной последовательности из N заглавных латинских букв определить, является ли она осмысленным словом и, если да, то сколько различных слогов можно составить из букв этого слова. Например, из слова BARAKA можно составить 15 слогов — BA, KA, RA, BKA, KBA, BRA, RBA, KRA, RKA, BKRA, BRKA, RBKA, RKBA, KBRA, KRBA.

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

Входной файл содержит единственную строку — исходную последовательность букв.

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

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

Ограничения

1 ≤ N ≤ 20

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

Входной файл (input.txt) Выходной файл (output.txt)
1
BARAKA
15

Задача F. Перестановки с подстрокой

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Например, если S = dcba, P = bc, то получится 11 строк: bc, abc, bca, dbc, bcd, adbc, dabc, abcd, dbca, bcad, bcda.

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

Первая строка содержит строку S, вторая — строку P.

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

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

Ограничения

Длины строк находятся в диапазоне от 1 до 12 букв. Все буквы строки S различны.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
dbca
bc
11
2
xyz
xx
0

Задача G. Наградные конфеты

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В детском танцевальном конкурсе участвовало N школьников. Организаторы решили наградить всех участников конкурса конфетами K различных сортов. Чтобы никого не обидеть, всем школьникам решили выдать одинаковое количество конфет. А чтобы было интереснее, набор конфет каждого школьника должен отличаться от всех остальных.

Например, если имеется 6 школьников и 3 сорта конфет, то можно определить такие награды из двух конфет каждая: (1, 1), (1, 2), (2, 2), (1, 3), (2, 3), (3, 3).

В то же время, если имеется 7 школьников и 3 сорта конфет, то каждому школьнику придётся выдать уже по три конфеты.

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

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

Входной файл целые числа N K.

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

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

Ограничения

2 ≤ N ≤ 109; 2 ≤ K ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 3
2
2
7 3
3
3
100 2
99

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

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

Количество чисел находится в диапазоне от 0 до 106, сами числа — в диапазоне от  − 231 до 231 − 1.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 1 3 0
1 2 3
2
5 -1 6 -5 5 0
5 6

Задача HZ. Код Хаффмана

Автор:stdalg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Построить код Хаффмана для алфавита из N символов и соответствующих им частот встречаемости.

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

Во входном файле содержится число N, за которым следуют N чисел fi — частота встречаемости i − го символа.

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

Выходной файл должен содержать N строк вида hi — коды Хаффмана для символов в порядке, соответствующем входному файлу. Каждый код должен представлять собой строку из цифр 0 и 1. Если существует несколько решений, вывести любое из них.

Ограничения

2 ≤ N ≤ 100, 0 ≤ fi ≤ 100000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6
45
13
12
16
9
5
0
101
100
111
1101
1100

Задача I. Дорога в аэропорт

Автор:И. Олейников   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

Во входном файле находятся числа N и K, за которыми идут N строк по K вещественных чисел ai, j в каждой — ограничение скорости на j-м участке i-й полосы (в км/час).

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

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

Ограничения

1 ≤ N ≤ 10, 1 ≤ K ≤ 1000, 1 ≤ ai, j ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 3
70 60 40
0.559
2
3 2
1 10000
1 1
100 1
10.001

Задача J. Табуретки-2 (30 баллов)

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины. На табуреткоизготовительную фабрику поступило N ножек, имеющих слегка различающиеся длины L1, L2, … LN. Научно-исследовательский отдел фабрики обнаружил, что выпуск табуреток можно увеличить, если укорачивать некоторые ножки. При этом отпиленная часть выбрасывается.

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

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

Входной файл содержит число N, за которым следуют N чисел Li — длины ножек. Все числа целые.

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

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

Ограничения

1 ≤ N ≤ 10000, N mod 4 = 0, 1 ≤ Li ≤ 100.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8
18 16 17 17 16 17 17 19
2

Задача K. Лягушка на деревьях (65 баллов)

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

Вдоль лесной тропинки растёт N деревьев высотой h1, h2, …, hN метров соответственно. Расстояние между соседними деревьями равно 1 метру.

Лягушка сидит на дереве с номером A и хочет попасть на дерево с номером B. Поскольку лазить по деревьям она не может, ей остаётся только перепрыгивать с одной вершины дерева на другую. При этом лягушка может развивать начальную скорость от 0 до v м/с, и прыгать под углом от 0 до α градусов.

Требуется найти минимальное количество прыжков, которое потребуются лягушке, или определить, что достичь цели невозможно. Ускорение свободного падения g следует принять равным 10 м/с2.

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

Входной файл содержит числа N A B v α, за которыми следует N чисел h1 h2hN. Числа v и α — вещественные, остальные числа — целые.

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

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

Ограничения

1 ≤ A, BN ≤ 100, 1 ≤ hi ≤ 1000, 0.01 ≤ v ≤ 1000, 0.01 ≤ α ≤ 90.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1 2 10 80 
5 6
1

Задача L. R2D2

Автор:М. Спорышев   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Перед сражением с ситхами Энакен Скайуокер решил протестировать своего дроида R2D2. Для проверки системы передвижения он решил поместить робота на специальную горизонтальную площадку, имеющую форму прямоугольника. Площадка разделена на квадратные клетки со сторонами длины 1. На некоторые клетки можно перемещаться, на некоторые - нет. R2D2 разрешено перемещаться только вверх, вперед, влево, вправо на соседние клетки.

Для первого теста Энакен хочет заставить робота пройти от начальной клетки площадки до конечной всеми возможными способами, проходя через каждую клетку ровно 1 раз. Чтобы заставить робота двигаться, юному джедаю надо записать все траектории, которые следует пройти роботу, в виде последовательностей символов 'l', 'r', 'u', 'd'. Символ 'l' означает, что робот должен перейти в левую соседнюю клетку, 'r', 'u', 'd' - в правую, верхнюю, нижнюю соответственно. Энакену лень записывать таким образом все способы перемещения, и он просит вас написать программу, которая напишет их за него.

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

Первая строка входного файла содержит два целых числа N, M - длины сторон прямоугольника. За ними следует N * M чисел A[i, j], которые равны 0, если в клетку с координатами i, j перемещаться нельзя, или 1 - можно. Первое число задает верхнюю левую клетку (она является начальной), последнее - нижнюю правую(конечная). Гарантируется, что есть хотя бы один путь из начальной клетки в конечную.

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

В выходной файл выведите число C - количество способов перемещения из начальной клетки в конечную, за которым следует C строк - способы перемещения в виде последовательностей символов 'l', 'r', 'u', 'd'. Последовательности можно выводить в любом порядке.

Ограничения

2 ≤ N,M ≤ 5

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1
1
1
1
d
2
2 2 
1 0
1 1
1 
dr

Problem M. Breadth First Search

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives an unweighted undirected graph and writes all its vertices in order of increasing distance from given vertex S. Distance between vertices A and B is the length of the shortest path from A to B. If there are several vertices such that their distances to S are equal, they may be printed in arbitrary order.

Input file format

Input file contains three integers N, M and S, where M is the number of edges, S is the starting vertex. Vertices are numbered with integer numbers from 1 to N. Each of next M lines contains a pair of integers — numbers of vertices connected by an edge.

Output file format

Output file must contain sequence of vertex numbers sorted by increasing distance from S. If some vertex is not reachable from S, output a single number  − 1.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2 1
1 2
2 3
1 2 3

Задача N. Дерево

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:256 Мб

Условие

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

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

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

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

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

Ограничения

1 ≤ n ≤ 105

0 ≤ m ≤ 105

1 ≤ ui, vi ≤ n

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2
1 3
YES
2
3 3
1 2
2 3
3 1
NO

Problem O. Topological sorting

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

Input file format

Input file contains two integers N and M, followed by M pairs of integers. Integers in each pair are different, and represent starting and ending vertex of a graph edge.

These pairs may also be considered comparisons where the first number precedes the second one.

Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number  − 1.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

Задача P. Обход в глубину

Автор:Жюри ВКОШП-2008   Ограничение времени:2 сек
Входной файл:dfs.in   Ограничение памяти:256 Мб
Выходной файл:dfs.out  

Условие

Недавно на кружке по программированию Петя узнал об обходе в глубину. Обход в глубину используется во многих алгоритмах на графах. Петя сразу же реализовал обход в глубину на своих любимых языках программирования — паскале и си.


var
  a: array [1..maxn, 1..maxn] 
       of boolean;
  visited: array [1..maxn] 
       of boolean;

procedure dfs(v: integer);
var 
  i: integer;
begin
  writeln(v);
  visited[v] := true;
  for i := 1 to n do begin
    if a[v][i] and 
        not visited[i] then 
    begin
      dfs(i);
      writeln(v);
    end;
  end;
end;

procedure graph_dfs;
var
  i: integer;
begin
  for i := 1 to n do
    if not visited[i] then
    	dfs(i);
end;

int a[maxn + 1][maxn + 1];
int visited[maxn + 1];

void dfs(int v) {
  printf("%d\n", v);
  visited[v] = 1;
  for (int i = 1; i <= n; i++) {
    if ((a[v][i] != 0) && 
        (visited[i] == 0)) {
      dfs(i);
      printf("%d\n", v);
    }
  }
}

void graph_dfs() {
  for (int i = 1; i <= n; i++) {
    if (visited[i] == 0) {
      dfs(i);
    }
  }
}

Петина программа хранит граф с использованием матрицы смежности в массиве "a" (вершины графа пронумерованы от 1 до n). В массиве "visited" помечается, в каких вершинах обход в глубину уже побывал.

Петя запустил процедуру "graph_dfs" для некоторого неориентированного графа G с n вершинами и сохранил ее вывод. А вот сам граф потерялся. Теперь Пете интересно, какое максимальное количество ребер могло быть в графе G. Помогите ему выяснить это!

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

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

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

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

Ограничения

1 ≤ n ≤ 300

1 ≤ l ≤ 2 n − 1

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

Входной файл (dfs.in) Выходной файл (dfs.out)
1
6 10
1
2
3
2
4
2
1
5
6
5
6
1 2
1 3
1 4
2 3
2 4
5 6

Задача Q. Интернет по ЛЭП

Автор:И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору. Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод, назовем нагрузкой на данный провод для i-го ретранслятора. Максимум из нагрузок на все провода для i-го ретранслятора называется нагрузкой на данный ретранслятор. Известно, что по проводам электросети сигнал может пройти от одного ретранслятора к другому единственным образом.

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

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

Во входном файле содержится число N — количество ретрансляторов, за которыми следуют N − 1 пар чисел ui vi, означающих, что i-ый провод соединяет ретрансляторы ui и vi.

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

В выходном файле должно содержаться N чисел a1 a2… aN, где ai — нагрузка на i-ый ретранслятор.

Ограничения

1 ≤ N ≤ 100000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2
2 3
2 1 2
2
4
1 2
1 3
1 4
1 3 3 3

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

Автор:ACM ICPC 2009-2010, NEERC, Northern Subregional Contest   Ограничение времени:3 сек
Входной файл:bureau.in   Ограничение памяти:256 Мб
Выходной файл:bureau.out  

Условие

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

Много веков спустя юристы обнаружили, что в королевстве было только два вида законов:

Закон считается активным если и только если нет активного закона, отменяющего его.

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

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

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

Следующие n описывают по одному закону каждая. Каждое описания удовлетворяет одному из следующих форматов:

Законы нумеруются с единицы.

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

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

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

Входной файл (bureau.in) Выходной файл (bureau.out)
1
5
declare
cancel 1
declare
cancel 2
cancel 3
3
1 4 5

Problem S. Shortest Spanning Tree

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N ≤ 1000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

Problem T. SST for sparse graph

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

Problem U. Ford-Bellman

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3 1
1 2 5
1 3 10
2 3 2
0 5 7

Problem V. Dijkstra

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

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

First line of input file contains three integers N M and S, where M is the number of edges. Next M lines contain three integers each — starting vertex number, ending vertex number and weight of some edge respectively. All weights are positive. There is at most one edge connecting two vertices in every direction.

Output file format

Output file must contain N integers — distances from source vertex to all vertices. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N ≤ 1000. All weights are less or equal than 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Problem W. Fast Dijkstra

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted directed graph and finds all distances from fixed 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 arcs.

Input file format

Input file contains two integers N, M and S. Vertices are numbered with integer numbers from 1 to N. S is the number of source vertex. M is the number of arcs. Each of next M lines contain three integers — numbers of starting and ending vertices of some arc and its weight respectively. All weights are positive. There is at most one arc connecting two vertices in every direction.

Output file format

Output file must contain N numbers. Each I-th number is the distance from vertex S to vertex I. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Problem X. Floyd-Warshall

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances between all pairs of vertices in a directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N and M, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a matrix of size NxN. Element in the j-th column of i-th row mush be the shortest distance between vertices i and j. The distance from the vertex to itself is considered to be 0. If some vertex is not reachable from some other, there must be empty space in corresponding cell of matrix.

Constraints

0 ≤ N ≤ 100. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 5
1 3 10
2 3 2
0 5 7
  0 2
    0

Problem Y. Knuth-Morris-Pratt

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

Constraints

Length of each string does not exceed 100000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16

Задача Z. Длинный текст и много слов (revisited)

Автор:A. Klenin   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Имеется текст и N слов. Длина текста составляет L символов, длина каждого слова — от 1 до 1000 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из маленьких латинских букв.

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

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

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

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

Ограничения

1 ≤ L ≤ 250000, 1 ≤ N ≤ 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
longlongstring
2
short
string
0 1

2.125s 0.013s 87