Примеры входа и выхода

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

 

Упорядочить последовательность натуральных чисел по не убыванию. Использовать алгоритмы сортировки обменами, выбором, пузырьком.

 

Вход

Во входном файле записано не более 10⁴ натуральных чисел (для сортировки пузырьком не более 10⁵ чисел). Каждое число не превосходит 10⁶.

Выход

Запишите в выходной файл числа из входного файла в порядке не убывания.

Примеры входа и выхода

input.txt	output.txt
3 2 1 5 4	1 2 3 4 5

Упражнение «Быстрые сортировки»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 3 секунды на тест

 

Упорядочить последовательность натуральных чисел по не убыванию. Использовать алгоритмы сортировки слиянием, QUICKSORT, HEAPSORT, Шелла.

 

Вход

Во входном файле записано не более 3∙10⁶ натуральных чисел. Каждое число не превосходит 10⁶.

Выход

Запишите в выходной файл числа из входного файла в порядке не убывания.

Примеры входа и выхода

input.txt	output.txt
3 2 1 5 4	1 2 3 4 5

 

Упражнение «Сортировки линейной сложности»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 3 секунды на тест

 

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

 

Вход

Во входном файле записано не более 3∙10⁶ натуральных чисел. Каждое число не превосходит 10⁶.

Выход

Запишите в выходной файл числа из входного файла в порядке не убывания.

Примеры входа и выхода

input.txt	output.txt
3 2 1 5 4	1 2 3 4 5

 

Упражнение «Порядковые статистики»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

 

В последовательности целых чисел найти K-ое по величине число.

 

Вход

В первой строке входного файла записано число K (1 ≤ K ≤ 10⁶). В остальных строках файла записаны целые числа x_j. Количество чисел не меньше, чем K, и не больше 10⁶. Числа x_j по модулю не превосходят 2∙10⁹.

Выход

Запишите в выходной файл K-ое по величине число из входного файла

Примеры входа и выхода

input.txt	output.txt
3 2 1 5 4

 

 

Упражнение «Бинарный поиск»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

 

В упорядоченной по не убыванию последовательности неповторяющихся целых чисел найти заданное число.

 

Вход

Первая строка входного файла содержит символ C и целое число K (С = ‘<’ | ‘>’ | ‘=’, | K | ≤ 2∙10⁹). В остальных строках файла записаны в порядке не убывания целые числа x_j. Количество чисел не больше 10⁶. Числа x_j по модулю не превосходят 2∙10⁹. Если C = ‘<’, то требуется найти в последовательности x_j наибольшее число, не большее K, если C = ‘>’, то требуется найти в последовательности наименьшее число, не меньшее K, если C = ‘=’, то требуется найти в последовательности число, равное K.

Выход

Запишите в выходной файл номер найденного числа в последовательности. Если нужного числа нет в последовательности, запишите в выходной файл число ноль.

Примеры входа и выхода

input.txt	output.txt
< 5 1 2 7 8 10
> 5 1 2 7 8 10
= 5 1 2 7 8 10

 

 

Упражнение «Метод бисекции»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

 

Найти корень уравнения , где a, b, c, d – заданные вещественные числа.

Вход

Во входном файле записаны вещественные числа a, b, c, d (0 < a, b, c, d ≤ 10⁹). Гарантируется, что при таких значениях параметров корень уравнения положителен.

Выход

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

Примеры входа и выхода

input.txt	output.txt
1 0.5 2 1.5	1.463702

 

 

Упражнение «Тернарный поиск»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

 

Задана числовая последовательность X_i, i = 1, …, n. Существует 1 ≤ k ≤ n: подпоследовательность X_i, i = 1, …, k не убывает и подпоследовательность X_i, i = k, …, n не возрастает. Методом тернарного поиска найти наибольший элемент последовательности.

 

Вход

Во входном файле записаны целые числа X_i. Количество чисел не больше 10⁶. Числа X_i по модулю не превосходят 2∙10⁹.

Выход

Запишите в выходной файл наибольшее число последовательности.

Примеры входа и выхода

input.txt	output.txt
1 2 2 2 2 3 3 4 4 4 5 5 5
1 2 3 4 5 4 3 2 1
5 4 3 2 1

 

 

Упражнение «Хеширование»

Входной файл: input.txt

Выходной файл: output.txt

Ограничение времени: 1 секунда на тест

 

Выполнить последовательность операций «добавить», «удалить» и «найти» над хеш-таблицей.

 

Вход

Во входном файле записана последовательность команд вида +s или -s или ?s или E. Здесь s - слово длиной не более 10 символов. Команда +s означает добавить в хеш-таблицу слово s, команда -s означает удалить из хеш-таблицы слово s, команда ?s - найти в хеш-таблице слово s. Команда E означает завершить операции с хеш-таблицей. Каждая команда записана в отдельной строке, начиная с первой позиции, и не содержит пробелов. Гарантируется, что количество слов в хеш-таблице не превысит 5000.

Выход

Запишите в выходной файл результаты выполнения команд ?s в том порядке, в котором они присутствуют во входном файле. Если слово найдено, запишите в отдельной строке символ «+» и найденное слово, в противном случае - символ «-» и не найденное слово.

Примеры входа и выхода

input.txt	output.txt
+глокая +куздра ?бокра -куздра ?куздра ?глокая E	-бокра -куздра +глокая