Контрольная работа 2020/2021 #02

Введение

Тестовая система

Доступ к тестовой системе - тут

Время работы программы: не более 1 сек

Объем использованной памяти: не более 256M

Из стандартных библиотек можно использовать только <iostream> и <cassert>

Хотя бы в одной из задач надо использовать свои функции сортировки и бинарного поиска (если, конечно, они вам нужны).

Формат участия

Время выполнения: 2 урока

ВАЖНО: после завершения тестирования работы (файлы) нужно прислать: нам на почту (popovsg@1543.msk.ru; lyahovecao@1543.msk.ru)

Будет две оценки: по результатам контеста + за качество кода

Задачи

A - Слияние упорядоченных массивов чисел

Условие: Даны два массива чисел, каждый упорядочен по невозрастанию. Слейте их в один массив с сохранением порядка.

Вход: в стандартном входном потоке, через пробел: целое число M, затем M целых чисел 1-го массива, затем целое число N, затем N целых чисел 2-го массива

Выход: M+N чисел через пробел в стандартный выходной поток

Пример вводаПример выводаПояснение
4 10 7 7 -1 3 15 10 7
15 10 10 7 7 7 -1
 

B - Пересечение массивов чисел

Условие: Выведите в порядке возрастания те числа, каждое из которых встречается в обоих заданных массивах чисел (если число встречается по несколько раз, его всё равно надо вывести только один раз).

Вход: в стандартном входном потоке, через пробел: целое число M, затем M целых чисел 1-го массива, затем целое число N, затем N целых чисел 2-го массива

Выход: числа через пробел в стандартный выходной поток

Пример вводаПример выводаПояснение
4 0 -1 1 0 3 1 0 0
0 1
 

C - Все пары одинаковых чисел

Условие: Найдите количество всех пар одинаковых чисел среди данных N чисел.

Вход: в стандартном входном потоке, через пробел: сначала целое число N, затем N целых чисел

Выход: число в стандартный выходной поток

Пример вводаПример выводаПояснение
5 1 3 2 2 3
2
 
4 -1 -1 -1 -1
6
Пару одинаковых чисел образуют любые два числа последовательности,
поэтому ответом будет число пар, которое вообще может быть
(это пары чисел, стоящих на местах: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4))

D - Пары с заданной суммой

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

Вход: в стандартном входном потоке, через пробел: сначала целое число S - данная сумма, затем целое число N, затем N целых чисел

Выход: пары чисел через пробел в стандартный выходной поток

Пример вводаПример выводаПояснение
4 5 1 3 2 2 3
1 3 2 2
Есть только одна пара 1 3, так как нет второй единицы
-2 4 -1 -1 -1 -1
-1 -1 -1 -1
Здесь можно составить 2 пары -1 -1 из не повторяющихся
входных чисел

E - Восстановление порядка

Условие: Изначально были расположены в некотором порядке N различных чисел a1...aN. Затем были составлены (N-1) пар ai,ai+1. Эти пары в случайном порядке подаются на вход. Выведите N чисел в исходном порядке a1...aN.

Вход: в стандартном входном потоке, через пробел: сначала целое число N, затем N-1 пар целых чисел

Выход: N чисел через пробел в стандартный выходной поток

Пример вводаПример выводаПояснение
5 3 7 -2 3 7 0 9 -2
9 -2 3 7 0
Из исходных чисел получились пары соседних
9 -2, -2 3, 3 7, 7 0. Затем эти пары в каком-то порядке
и поступили на вход

F - Сортировка связанного списка

Условие: Образуйте из входных чисел связанный список. Преобразуйте его в список, числа в котором упорядочены по неубыванию (не переходя к массивам!). Выведите числа полученного связанного списка.

Вход: в стандартном входном потоке, через пробел: сначала целое число N, затем N целых чисел

Выход: N чисел через пробел в стандартный выходной поток