Problem A. Square sort

Author:StdAlg   Time limit:64 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 B. Lin-log sort 2

Author:StdAlg   Time limit:2 sec
Input file:input.txt   Memory limit:512 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

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

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 106, 1 ≤ K ≤ N,  − 231 ≤ Ai ≤ 231 − 1

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

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

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

Автор: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

Problem E. Bucket sort (LETTERS ONLY)

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

Задача F. Фонари

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

Условие

На улице длиной в 100 метров установлено N фонарей высотой y1, y2, …, yN метров на расстоянии x1, x2, … xN метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

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

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

  1. N ≤ 2

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

Во входном файле содержится число N, за которым следует N пар целых чисел x1 y1 x2 y2… xN yN.

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

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

Ограничения

1 ≤ N, yi ≤ 100, 0 ≤ xi ≤ 100.

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

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

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

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

Условие

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

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

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

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

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

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

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа xi и vi — координату i-й частицы и ее тип соответственно (x1 < x2 < x3 < ... xn). Частица e −  описывается значением vi =  − 1, а частица e +  описывается значением vi = 1.

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

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

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

Ограничения

1 ≤ n, m ≤ 200000

 − 109 ≤ xi, m ≤ 109

0 ≤ ti ≤ 109

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

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

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

Подзадача Баллы Ограничения Необходимые подзадачи
nximti
1351 ≤ n ≤ 100 − 100 ≤ xi ≤ 100m = 10 ≤ ti ≤ 100
2121 ≤ n ≤ 100 − 109 ≤ xi ≤ 109m = 10 ≤ ti ≤ 1091
3121 ≤ n ≤ 200 000 − 109 ≤ xi ≤ 109m = 10 ≤ ti ≤ 1091, 2
4411 ≤ n ≤ 200 000 − 109 ≤ xi ≤ 109 1 ≤ m ≤ 200 0000 ≤ ti ≤ 1091, 2, 3

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

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

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

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

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

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

Входной файл (linear.in) Выходной файл (linear.out)
1
4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3
4
2
0
0

0.558s 0.017s 25