training_2009_12_12 - условия

Problem A. Lin-log sort ≡

problems
details
visible spaces
basic formulae
wide text

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 10⁹ 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. Bucket sort ≡

problems
details
visible spaces
basic formulae
wide text

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

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

задачи
детали
видимые пробелы
простые формулы
широкий текст

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

Условие

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

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

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

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

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

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

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 2³¹−1

1 ≤ K ≤ N ≤ 4 ⋅ 10⁷

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

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