Упражнения на передачу массивов в функцию и линейный поиск

A: Возрастает ли массив?

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

Выведите YES, если массив монотонно возрастает и NO в противном случае.

Решение оформите в виде функции bool is_ascending(const vector<int> & a). В данной функции должен быть один цикл while, не содержащий вложенных условий и циклов — используйте схему линейного поиска.

Ввод Вывод
3
1 7 9
YES

B: k-е вхождение

Дан массив чисел, число \(key\) и натуральное число \(k\) . Выведите индекс \(k\)-го по счету появления в массиве числа \(key\). Если число \(key\) встречается в массиве менее \(k\) раз, выведите число -1.

Решение оформите в виде функции int kth_appearance(const vector<int> & a, int key, int k). Задача должна решаться за однократный проход по массиву. Используйте схему линейного поиска.

Ввод Вывод
10
1 2 1 3 2 3 2 3 2 2
3 2
5
4
1 1 1 1
1 5
-1

Упражнения на реализацию квадратичных алгоритмов сортировки

C: Сортировка выбором

Дан массив целых чисел. Отсортируйте его в порядке невозрастания значений. Выведите полученный массив на экран.

Решите эту задачу при помощи алгоритма сортировки выбором. Решение оформите в виде функции void selection_sort(vector<int> & a).

Вспомогательным массивом пользоваться нельзя.

Ввод Вывод
5
1 4 2 3 4
4 4 3 2 1

D: Сортировка вставкой

Дан массив целых чисел. Отсортируйте его в порядке неубывания значений. Выведите полученный массив на экран.

Решите эту задачу при помощи алгоритма сортировки вставкой. Решение оформите в виде функции void insertion_sort(vector<int> & a).

Вспомогательным массивом пользоваться нельзя.

Ввод Вывод
5
1 4 2 3 4
1 2 3 4 4

E: Сортировка пузырьком

Дан массив целых чисел. Отсортируйте его в порядке невозрастания значений. Выведите полученный массив на экран.

Решите эту задачу при помощи алгоритма пузырьковой сортировки. Решение оформите в виде функции void bubble_sort(vector<int> & a).

Вспомогательным массивом пользоваться нельзя.

Ввод Вывод
5
1 4 2 3 4
4 4 3 2 1

Упражнения на применение стандартной сортировки

Обратите внимание, что в следующих задачах количество данных чисел столь велико, что для решения задач не получится использовать квадратичные алгоритмы сортировки. Используйте стандартную функцию sort библиотеки STL.

F: Создание архива

Системный администратор вспомнил, что давно не делал архива пользовательских файлов. Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.

Известно, какой объем занимают файлы каждого пользователя.

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

Программа получает на вход в одной строке число \(S\)  размер свободного места на диске, и число \(N\) — количество пользователей, после этого идет \(N\) чисел — объем данных каждого пользователя, записанных каждое в отдельной строке.

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

Используйте стандартную сортировку. Решение должно иметь сложность стандартной сортировки + \(O(N)\). Решение не должно модифицировать исходный массив после считывания и сортировки.

Ввод Вывод
100 2
200
50
1
100 3
50
30
50
2

G: Такси

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал \(N\) машин —ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

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

В первой строке записано число сотрудников \(N\le10^5\), во второй строке записаны \(N\) чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании. В третьей строке записаны \(N\) чисел — тарифы за проезд одного километра в такси.

Выведите одно целое число — наименьшую сумму, которую придется заплатить за доставку всех сотрудников.

Ввод Вывод
3
10 20 30
50 20 30
1700

H: Скидки

В супермаркете проводится беспрецедентная акция: “Покупая два любых товара, третий получаешь бесплатно*”, а внизу мелким шрифтом приписано “* — из трех выбранных вами товаров оплачиваются два наиболее дорогих”.

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

Программа получает на вход число \(N\) (\(1\le N\le 10^5\)), а затем \(N\) чисел — стоимости выбранных Васей товаров. Все стоимости — натуральные числа, не превышающие \(10000\).

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

Ввод Вывод Пояснение
6
1 5 4 3 5 7
19
Вася сначала пройдет через кассу с товарами стоимостью 1, 3 и 4 – заплатит 7 рублей и товар стоимостью 1 получит в подарок, а затем снова зайдет в супермаркет и купит товары стоимостью 5 и 7, еще один товар стоимостью 5 получив в подарок.
5
3 15 25 8 8
51
Вася в первый заход в супермаркет купит товары стоимостью 15 и 25 рублей, в качестве подарка взяв товар стоимостью 8 рублей. А во второй заход в супермаркет купит товары стоимостью 3 и 8, не взяв никакого подарка.

I: Количество различных чисел

Дан массив чисел. Определите, сколько в нем различных чисел.

Программа получает на вход число \(N\) (\(1\le N\le 10^5\)), а затем \(N\) натуральных чисел, не превышающих \(10^9\).

Ввод Вывод
5
1 7 9 7 1
3

J: Два ближайших числа

Дан массив натуральных чисел, содержащий не менее двух элементов. Найдите в нем два ближайших друг к другу числа (то есть два числа с наименьшей разностью).

Выведите эти числа в порядке неубывания.

Программа получает на вход число \(N\) (\(1\le N\le 10^5\)), а затем \(N\) натуральных чисел, не превышающих \(10^9\).

Ввод Вывод
4
9 4 1 6
4 6

K: Свадьбы

Одна очень предприимчивая и симпатичная девушка решила собрать себе денег на роскошную жизнь. У нее есть \(N\) поклонников, про каждого из них она узнала размер его состояния \(P_i\). Девушка намерена выйти замуж и сразу же развестись с некоторыми из своих поклонников так, чтобы в результате получить максимально возможное состояние. По законам страны в случае развода каждый из супругов получает ровно половину их общего состояния.

Первая строка входных данных содержит число \(N\le10^5\)—  количество поклонников. Вторая строка содержит \(N\) натуральных чисел \(X_1\), ..., \(X_N\) — размеры состояний поклонников. Третья строка содержит одно число \(Y\) — состояние девушки.

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

Ввод Вывод
2
5 10
5
7.5
3
1 3 2
0
2.125
1
1
2
2.0

L: Выборы в США

Президент в США выбирается коллегией выборщиков в результате непрямых выборов. Рассмотрим упрощенную модель таких выборов.

Все избиратели делятся на \(N\) групп (необязательно равных по численности), каждая группа имеет одного представителя в коллегии выборщиков. Сначала в каждой группе проводится голосование по поставленному вопросу, если строго более половины избирателей группы высказывается “за”, то представитель этой группы в коллегии выборщиков голосует ”за“ от имени всей группы. Решение принимается, если строго более половины выборщиков (то есть групп) проголосовали “за”.

При такой системе решение может быть принято коллегией выборщиков, даже если “за” высказалось менее половины от общего числа избирателей.

Первая строка входных данных содержит число \(N\le10^5\) — количество групп. Вторая строка содержит \(N\) чисел — размеры групп.

Программа должна вывести минимальное количество изибираетелей, которое могло проголосовать “за”, если в итоге решение было принято коллегией выборщиков.

Ввод Вывод
3
5 5 7
6
5
4 2 1 3 7
5

M: Строительство магазина

В некотором городе на прямой улице расположено \(n\) домов. \(i\)-й дом задан неотрицательной величиной \(x_i\) — расстоянием от начала улицы до дома, таким образом, расстояние между двумя домами \(i\) и \(j\) равно \(|x_i-x_j|\).

В одном из этих домов необходимо открыть магазин таким образом, чтобы суммарное расстояние от магазина до остальных домов было наименьшим.

Первая строка входных данных содержит число \(N\le10^5\) — количество домов. Вторая строка содержит \(N\) чисел — координаты домов.

Программа должна вывести координату дома, в котором необходимо открыть магазин. Если возможных ответов несколько, необходимо вывести любой из них.

Подсказа. Это ОЧЕНЬ простая задача.

Ввод Вывод
4
1 2 3 4
2

N: Субботник

В классе учатся \(N\) человек. Классный руководитель получил указание разбить их на \(R\) бригад по \(C\) человек в каждой и направить на субботник (\(N = RC\)).

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

Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!

Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по четыре человека в каждой. Тогда одним из вариантов является такой:

1 бригада: люди с ростом 225, 205, 225, 260.

2 бригада: люди с ростом 160, 190, 170, 130.

При этом максимальное число неудобства будет во второй бригаде, оно будет равно 60, и это наилучший возможный результат.

Первая строка входных данных содержит два натуральные числа \(R\) и \(C\) — количество бригад и количество человек в каждой бригаде. Далее вводятся \(N = RC\) целых чисел по одному числу в строке — рост каждого из \(N\) учеников.

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

Ввод Вывод
2 4
170
205
225
190
260
130
225
160
60

O: Обувной магазин

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

Первая строка входных данных содержит количество пар обуви в магазине \(N\le 10^5\) и размер ноги покупателя \(S\). Во второй строке записаны \(N\) чисел — размеры каждой пары обуви в магазине через пробел. Все размеры — натуральные числа, не превосходящие \(10^9\). Покупатель не сможет надеть обувь, размер которой меньше \(S\).

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

Ввод Вывод
2 60
60 63
2
5 35
40 35 41 30 42
2

P: Коньки

В 179 школе есть много коньков самых разных размеров. Школьник может надеть коньки любого размера, который не меньше размеров его ноги. Известны размеры всех коньков и размеры ног школьников. Определите, какое наибольшее число школьников сможет одновременно пойти покататься.

Первая строка входных данных содержит количество коньков \(N \le 10^5\). Во второй строке записаны \(N\) чисел — размеры коньков. В третьей строке записано количество школьнико \(M \le 10^5\). В четвертой строке записаны \(M\) чисел — размеры ног школьников. Все размеры — натуральные числа, не превосходящие \(10^9\).

Выведите единственное число — наибольшее количество школьников, которое сможет пойти на каток.

Ввод Вывод
4
41 40 39 42
3
42 41 42
2

Q: Несоставляемая масса

Дано \(N\) гирек, массы которых — целые числа. Определите минимальную целочисленную массу груза, которую нельзя уравновесить на чашечных весах при помощи какого-то подмножества данного набора гирек.

Программа получает на вход число \(N\le 10^5\), затем \(N\) чисел — массы гирек (целые числа, не превосходящие \(10^9\)). Программа должна вывести одно число — искомую массу.

Обратите внимание, что для хранения ответа в этой задаче недостаточно типа int.

Ввод Вывод
4
1 1 5 1
4
4
1 2 4 8
16

R: World of tanks

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

Первая строка входных данных содержит количество танков \(N\le 10^5\). Следующие \(N\) строк содержат по два числа \(x_i\) и \(y_i\) — координаты танков (\(0\lt x_i\le 10^3\), \(-10^3\le y_i\le 10^3\)).

Программа должна вывести одно число — необходимое количество выстрелов.

Ввод Вывод
4
1 0
1 -1
2 2
3 3
3

Упражнения на слияние массивов и реализация сортировки слиянием

S: Слияние массивов

Даны два массива a и b упорядоченных по неубыванию. Объедините их в один упорядоченный массив res. Решение оформите в виде функции void merge(const vector <int> & a, const vector <int> & b, vector <int> & res). Алгоритм должен иметь сложность \(O(n+m)\) (\(n\) — размер первого массива, \(m\) — размер второго массива).

Программа получает на вход число \(n\), затем последовательность из \(n\) неубывающих чисел — элементы первого массива, затем число \(m\), затем последовательность из \(m\) неубывающих чисел — элементы второго массива.

Программа должна вывести \(n+m\) чисел, полученных объединением двух массивов в порядке неубывания.

Ввод Вывод
3
1 5 7
4
2 4 4 5
1 2 4 4 5 5 7

T: Пересечение множеств

Даны два множества чисел, упорядоченных по возрастанию (каждое множество состоит из различных элементов). Найдите пересечение данных множеств, то есть те числа, которые являются элементами обоих множеств. Алгоритм должен иметь сложность \(O(n+m)\).

Решение оформите в виде функции void intersection(const vector <int> & a, const vector <int> & b, vector <int> & res).

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

Ввод Вывод
5
1 3 4 7 9
5
2 3 7 10 11
3 7

U: Сортировка слиянием

Сортировка слиянием (англ. merge sort) позволяет отсортировать данный массив при помощи \(O(n\log n)\)) сравнений элементов.

Проще всего реализовать сортировку слиянием при помощи рекурсивной функции. Если длина данного массива равна 0 или 1, то массив уже отсортирован. Иначе необходимо разделить этот массив на две части равной (или отличающейся на 1) длины, каждую из них отсортировать рекурсивно, затем слить результат двух полученных массивов в исходный массив.

Реализуйте алгоритм сортировки слиянием.

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

Ввод Вывод
7
4 1 4 8 6 6 5
1 4 4 5 6 6 8

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

В этих задачах не требуется использовать стандартную функцию sort — достаточно использовать какой-либо квадратичный алгоритм. Более того, стандартные сортировки могут быть просто неприменимы в этих задачах...

V: Оладьи

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

Сортировка стопки осуществляется серией “переворотов” оладий. Переворот заключается в том, что вы помещаете лопатку между двумя оладьями и переворачиваете всю стопку, оказавшуюся на лопатке, то есть меняете порядок следования оладий над лопаткой на обратный.

Стопка определяется заданием диаметра каждой оладьи в стопке в порядке следования (сверху вниз). Переворачивание определяется количеством оладий, которое переворачивается. Например, из стопки 7 3 9 1 5 переворачиванием трех оладий получится стопка 9 3 7 1 5.

Вам дана стопка оладий, выведите последовательность переворачиваний (то есть количество оладий, которое нужно переворачивать за один раз), сортирующую данную стопку.

Первая строка входных данных содержит натуральное число \(N\) (\(1 \le N \le 1000\)) — количество оладий в стопке. Далее идет \(N\) натуральных чисел, не превосходящих \(10^9\) — размеры оладий в стопке (сверху вниз).

Программа должна вывести последовательность натуральных чисел, не превосходящих \(N\), соответствующую количеству оладий, которое необходимо переворачивать для правильной сортировки стопки. Количество переворотов не должно превосходить \(10000\).

Ввод Вывод
3
1 3 2
2
3
2

В этой задаче вам понадобится переворачивать фрагмент массива. Для этого можно использовать функцию reverse из заголовочного файла algorithm, которая, как и функция sort получает в качестве параметров два итератора и разворачивает фрагмент массива от первого итератора (включительно) до второго итератора (не включительно).

Например, вызов reverse(a.begin(), a.begin() + i) развернет i первых элементов вектора, то есть до элемента a[i] не включительно. А вызов reverse(a.begin() + i, a.end()) развернет элементы начиная с a[i] и до конца вектора.

W: Число из кусочков

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

Первая строка входных данных содержит количество кусочков \(N\le100\). Следующие \(N\) строк содержат последовательности цифр, записанных на кусочках, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.

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

Ввод Вывод
4
2
20
004
66
66220004

Указание. Эта задача — не про числа.

X: Кузнечики возвращаются

\(N\) кузнечиков сидят вдоль числовой прямой, в точках 1, 2, ..., \(N\). На кузнечиках написаны числа от \(1\) до \(N\). Необходимо расставить кузнечиков по порядку, чтобы каждый кузнечик оказался в точке, соответствующей его номеру.

Длина прыжка кузнечика равна 2 или 3. Одновременно в одной точке не могут находиться два кузнечика, поэтому единственно возможная операция перестановки кузнечиков заключается в том, что два кузнечика, сидящих в точках \(i\) и \(j\) одновременно прыгают и меняются местами. Это возможно сделать только в том случае, если \(|i-j|=2\) или \(|i-j|=3\).

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

В первой строке входных данных дан размер массива \(N\) (\(5\le N\le 100\)), во второй строке записана некоторая перестановка чисел от \(1\) до \(N\) через пробел — номера кузнечиков.

Программа должна вывести последовательность обменов кузнечиков. В каждой строке выводится два числа \(i\) и \(j\), означающих, что необходимо переставить переставить кузнечиков, сидящих в точках \(i\) и \(j\), при этом \(1\le i\le n\), \(1\le j\le n\), \(2\le|i-j|\le3\).

Ввод Вывод
5
3 4 1 5 2
2 4
1 3
2 5

Y: Ожерелье

В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из \(N\) колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до \(N\), начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.

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

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

Первая строка входных данных содержит число \(N\) (\(2 \le N \le 50\)). Во второй строке через пробел следуют \(N\) различных чисел от 1 до \(N\) — номера колечек, расположенных вдоль нити по часовой стрелке.

Программа должна вывести описание процесса упорядочения.

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

Количество выводимых строк не должно превышать 50000.

Ввод Вывод
4
3 1 2 4
4 2
4 1
0

Z: Ханойская сортировка

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

Программа получает на вход число дисков n≤10. Во второй строке записаны n чисел — номера дисков на первом стержне сверху вниз.

Перемещать диск можно только в том случае, если он кладется на диск большего номера. Выведите последовательность перекладываний, размещающая диски на любом стержне в порядке возрастания номеров. Формат вывода одного перекладывания: A B C, где A  номер перемещаемого диска (1≤A≤n), B — номер стержня с которого снимается диск, C — номер стержня на который кладется диск.

Ввод Вывод
3
2 1 3
2 1 2
1 1 3
2 2 1
1 3 1