## Problem A. Lin-log 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 ≤ 100000. 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 B. 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.

1 ≤ n ≤ 50000

### Sample tests

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

## Задача C. Передовики производства ≡

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

### Условие

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

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

В первой строке входного файла содержатся целые числа N M, разделенные пробелами. Далее следуют N чисел Ai, обозначающих производительность i-рабочего. Завершают входной файл M пар чисел Numi Vali, обозначающие номер рабочего, производительность которого изменилась и величину изменения соответственно.

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

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

### Ограничения

(1 ≤ N, M ≤ 100000, 1 ≤ NumiN, −1000 ≤ Vali, Ai ≤ 1000)

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 4
7 4 9
2 3
1 4
2 10
2 -10
9
11
17
11

## Задача D. 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

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

• задачи
 Автор: 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

## Задача F. Результаты квалификации ≡

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

### Условие

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

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

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

Когда гонщик завершает очередной круг, в журнал записываются числа Bi и Ti — номер его машины и разность между временем, за которое он проехал этот круг, и текущим лучшим среди всех гонщиков временем. (Ti измеряется в тысячных долях секунды, T1 всегда равно 0). Если Ti < 0, то время, показанное этим гонщиком, становится лучшим.

Требуется определить результат квалификации по записям в журнале.

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

Входной файл содержит число N — общее количество кругов, сделанных всеми гонщиками в квалификации.

Далее содержатся N пар целых чисел Bi Ti — записи в журнале в хронологическом порядке.

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

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

### Ограничения

1 ≤ N ≤ 105

Разница между лучшим и худшим временем не превышает 109 тысячных секунды

1 ≤ Bi ≤ 106

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

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


## Задача G. Финишные позиции ≡

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

### Условие

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

Требуется написать программу, которая по заданному списку машин определит их финишные позиции.

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

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

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

Далее следуют N чисел, задающие список.

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

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

### Ограничения

1 ≤ N ≤ 106

Номера машин являются целыми неотрицательными числами, не превосходящими 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 1 10
5 1 10
2
8
4 7 8 7 4 8 7 4
7 4 8
3
16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222
17 39 88 222222222

## Задача I. Дипломы ≡

• задачи
 Автор: Центральная предметно-методическая комиссия по информатике Ограничение времени: 2 сек Входной файл: diploma.in Ограничение памяти: 64 Мб Выходной файл: diploma.out

### Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

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

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

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

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

В выходной файл необходимо вывести ответ на поставленную задачу.

### Ограничения

1 ≤ W, H, N ≤ 109

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

Входной файл (diploma.in) Выходной файл (diploma.out)
1
2 3 10
9

## Задача J. Заколдованный аквариум ≡

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

### Условие

По мотивам романа А. и Б. Стругацких “Понедельник начинается в субботу”.

Очередной понедельник выдался в НИИЧАВО (Научно-Исследовательский Институт ЧАродейства и ВОлшебства) на удивление беспокойным. Началось все с проблем в отделе исследования живой, мёртвой и водопроводной воды, куда на прошлой неделе завезли новый аквариум. Туда и вошел Привалов в самый интересный момент беседы между Амвросием Амбруазовичем Выбегалло и заведующим отделом смысла жизни Кристобалем Хозевичем Хунтой. Сейчас Кристобаль Хозевич в красках описывал, какие могут возникнуть повреждения всей новейшей системы безопасности, недавно установленной в институте, от всего того количества воды, которым сейчас затапливался его отдел.

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

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

— Нет, это категорически невозможно! — Возражал Выбегалло, — как вы себе это представляете? Мы проводим важнейший эксперимент!

— Может быть, объясните, что здесь все-таки происходит? - вмешался в разговор Привалов

— Позвольте, я объясню, начал было Выбегалло, но Кристобаль Хозевич не дал ему закончить, и, сделав руками несколько пассов, произнес, — вот теперь порядок, ничего не вливается и не выливается, можете объяснять.

— Ну, раз вы все-таки запечатали отверстия, то спешки особой нет, — продолжил Амвросий Амбруазович, — на прошлой неделе мне, доставили новый большой аквариум, необычной конструкции, а если быть точным, с несколькими прямоугольными отверстиями на лицевой стороне, вот посмотрите.

Привалов, наконец, осмотрел новый аквариум. Он представлял собой прямоугольный параллелепипед размерами W × H × L метров без верхней крышки, на лицевой стороне которого было вырезано N квадратных отверстий c длиной стороны ai метров. Сверху над аквариумом висела большая труба, через которую в него поступало M кубических метров воды в секунду.

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

— А более сухого способа вы не нашли, — вставил свою реплику Хунта

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

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

Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме. Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой: через отверстие площадью b квадратных метров в одну секунду будет вытекать V × b кубических метров воды.

В начале эксперимента аквариум пуст. Через некоторое время после того, как из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется (либо аквариум переполнится). Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.

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

Входной файл содержит числа V M N — соответственно скорость вытекания воды (в м / с), поток втекающей воды (м3 / c) и количество отверстий в лицевой стороне аквариума. Далее следует N троек чисел xi yi ai — координаты нижнего левого угла и длина стороны. отверстия номер i. Отверстия не пересекаются и не соприкасаются друг с другом.

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

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

### Ограничения

0 < V, M ≤ 1000, 0 ≤ N ≤ 100, 0 ≤ xi, yi, ai ≤ 106.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 4 3
1.0 1.0 4.0
6.0 2.0 4.0
11 5.0 3.0

2.0


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

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

### Условие

Однажды под новый год Гассан Абдуррахман ибн Хоттаб решил помочь Вольке нарядить ёлку. Среди ёлочных украшений Хоттабычу больше всего понравилась гирлянда, состоящая из 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 символов.

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

Входной файл (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

0.591s 0.014s 35