Сортировки

Передача массива в качестве параметра

Массивы можно передавать функции в качестве параметра. Но при этом размер создаваемого массива может быть неопределен на момент компиляции программы, поэтому функция не может знать размер полученного массива. Поэтому в функции нужно передавать два параметра - указатель на начала массива (например, для массива целых чисел это int *, и количество элементов в массиве.

Например, функция поиска наименьшего значения в массиве int A[n] может быть объявлена так:

int Min (int * A, int n)
{
    int result;
    // Вычисляем ответ
    return result;
}

Соответственно, внутри функции main мы объявляем массив int A[n] и вызываем функцию Min, передав в качестве параметров массив A и его размер n:

int main()
{
    int n, i;
    cin >> n;
    int A[n];
    for (i = 0; i < n; ++i)
    {
        cin >> A[i];
    }
    cout << Min(A, n) << endl;
    return 0;
}

Упражнения

Во всех (почти) задачах этого листа основной алгоритм решения задачи должен быть описан в виде функции, получающей в качестве параметра массив и количество элементов в нем (а также, возможно, и дополнительные параметры). Функция main при этом считывает данные, вызывает основную функцию, выводит результат. Входные массивы задаются в виде: сначала количество элементов массива (положительное), затем сами элементы массива.

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

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

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

Решение оформите в виде функции bool IsAscending(int * A, int n). В данной функции должен быть один цикл while, не содержащий вложенных условий и циклов — используйте схему линейного поиска.

3
1 7 9

YES

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

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

Решение оформите в виде функции int KthAppearance(int * A, int n, int a, 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: Количества цифр

Дана последовательность чисел, состоящая только из чисел 1, ..., 9. Последовательность завершается числом 0. Подсчитайте, сколько раз в этой последовательности встречаются значения 1, 2, ..., 9. Программа должна вывести ровно 9 чисел: количество единиц, двоек, ..., девяток в данной последовательности. Последовательность может быть настолько большой, что сохранить ее всю в массиве невозможно.

1 2 3 4 5 1 1 1 2 2 0

4 3 1 1 1 0 0 0 0

D: Противоположные элементы в массиве

Дан массив. Определите, есть ли в нем два противоположных (то есть дающих в сумме 0) числа.

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

5
1 2 3 -2 -4

1 3

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

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

Решите эту задачу при помощи алгоритма сортировки выбором. Решение оформите в виде функции void SelectionSort(int * A, int n).

В алгоритме сортировки выбором мы находим наибольший элемент в массиве и ставим его на первое место, затем находим наибольший элемент из оставшихся и ставим его на второе место и т.д. Таким образом, в решении имеется цикл for(i = 0; i < n - 1; ++i), внутри которого находится наибольший элемент среди A[i], A[i+1], ..., A[n-1], который устанавливается на место A[i].

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

5
1 4 2 3 4

4 4 3 2 1

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

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

Решите эту задачу при помощи алгоритма сортировки вставкой. Решение оформите в виде функции void InsertionSort(int * A, int n).

В алгоритме сортировки вставкой в каждый произвольный момент начальная часть массива уже отсортирована. В решении имеется цикл for(i = 1; i < n; ++i), внутри которого в предположении, что элементы массива A[0], A[1], ..., A[i-1] уже отсортированы, элемент A[i] добавляется в отсортированную часть. Для этого находится позиция, в которую необходимо вставить элемент A[i], затем осуществляется циклический сдвиг фрагмента уже отсортированной части.

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

5
1 4 2 3 4

1 2 3 4 4

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

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

Решите эту задачу при помощи алгоритма пузырьковой сортировки. Решение оформите в виде функции void BubbleSort(int * A, int n).

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

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

5
1 4 2 3 4

4 4 3 2 1

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

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

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

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

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

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

100 2
200
50

1

100 3
50
30
50

2

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

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

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

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

60 2
60 63

2

35 5
30 40 35 42 35

2

J: Результаты олимпиады

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

Упорядочите список участников олимпиады в порядке убывания набранных баллов.

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

Выведите список участников (только фамилии) в порядке убывания набранных баллов.

3
Ivanov 15
Petrov 10
Sidorov 20

Sidorov
Ivanov
Petrov

K: Личные дела

Однажды неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям.

В первой строке входных данных записано число \(N\) (\(1 \le N \le 1000\)) — количество личных дел. Далее записано \(N\) строк, каждая из которых состоит из фамилии учащегося (строка без пробелов) и номера класса (целое число от 1 до 11).

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

3
Ivanov 10
Petrov 9
Sidorov 9

9 Petrov
9 Sidorov
10 Ivanov

L: Такси

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

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

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

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

3
10 20 30
50 20 30

1700

M: Сортировка дробей

В этой задаче вам нужно научиться сортировать не числа, а рациональные дроби. Программа получает на вход \(N\) дробей: сначала задается число \(N\), потом идет \(N\) строк, в каждой из которых записана одна дробь. Дробь записана в виде \(a/b\), где \(a\) и \(b\) —натуральные числа.

Программа должна вывести список этих дробей в порядке неубывания. Если в списке есть две равные дроби \(a/b=c/d\), то раньше выводится дробь, у которой меньше числитель.

При решении этой задачи нельзя использовать действительные числа.

Указание. Удобно отдельно хранить числитель дроби, отдельно — знаменатель. Для того, чтобы считать дробь, записанную в виде a/b можно делать так:

int a, b;
char slash;
cin >> a >> slash >> b;

3
4/2
2/6
1/2

2/6
1/2
4/2

N: Коньки

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

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

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

4
41 40 39 42
3
42 41 42

2

O: Скидки

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

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

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

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

6
1 5 4 3 5 7

19

5
3 15 25 8 8

51

P: Чемпионат по стрельбе

Региональный этап Всероссийской олимпиады школьников по информатике, 2011 г.

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

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

Будем считать, что участник соревнования занял \(k\)-е место, если ровно \(k-1\) участников чемпионата набрали строго больше очков, чем он. При этом победителями считались все участники чемпионата, занявшие первое место.

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

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

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

7
10 20 15 10 30 5 1

6

3
15 15 10

1

3
10 15 20

0

Q: SMS-голосование

На телевизионном шоу зрители голосуют за участников шоу, отправляя SMS-сообщение с номером участника. Определите победителя шоу на основе присланных SMS-сообщений.

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

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

Неверные номера, присланные телезрителями (то есть большие чем \(N\)) необходимо игнорировать.

3
7
1 2 2 1 3 2 3

2

2
4
1 2 2 1

1 2

3
3
4 3 4

3

R: Сортировка подсчетом

Дан массив из \(N \) элементов (\(3\le N\le 10^6\)), которые принимают целые значения от 0 до 100.

Отсортируйте этот массив в порядке неубывания элементов.

Решение оформите в виде функции void CountSort(int * A, int n, int maxval), которая модифицирует передаваемый ей массив.

5
1 3 2 3 1

1 1 2 3 3

S: Клавиатура

Региональный этап Всероссийской олимпиады школьников по информатике, 2009 г.

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

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

Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.

Первая строка входных данных содержит целое число \(N\) (\(3\le N\le 1000\)) — количество клавиш на клавиатуре. Вторая строка содержит \(N\) целых чисел — \(c_1\), \(c_2\), ..., \(c_N\), где \(c_i\) (\(3\le c_i\le 10^5\)) — количество нажатий, выдерживаемых \(i\)-ой клавишей. Третья строка содержит целое число \(k\) (\(3\le k\le 10^5\)) — общее количество нажатий клавиш, и последняя строка содержит \(k\) целых чисел \(p_j\) (\(3\le p_j\le N\)) — последовательность нажатых клавиш.

Программа должна вывести \(N\) строк, содержащих информацию об исправности клавиш. Если \(i\)-я клавиша сломалась, то \(i\)-ая строка должна содержать слово YES, если же клавиша работоспособна — слово NO.

5
1 50 3 4 3
16
1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5

YES
NO
NO
NO
YES

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

Даны два массива int A[n] и int B[m] упорядоченных по неубыванию. Объедините их в один упорядоченный массив int C[n+m]. Решение оформите в виде функции void merge (int * A, int n, int * B, int m, int * C). Алгоритм должен иметь сложность \(O(n+m)\).

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

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

3
1 5 7
4
2 4 4 5

1 2 4 4 5 5 7

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

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

Решение оформите в виде функции int Intersection(int * A, int n, int * B, int m, int * C). Функция должна возвращать количество элементов в объединении этих множеств.

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

5
1 3 4 7 9
5
2 3 7 10 11

3 7

V: Наибольшее произведение двух чисел

Дан массив, заполненный целыми числами, не превосходящими по модулю \(10^6\). Найдите в этом списке два числа, произведение которых максимально. Выведите эти числа. Количество исходных чисел в списке не превосходит 100.

Не забывайте, что при перемножении двух чисел порядка \(10^6\) результат будет иметь порядок \(10^{12}\).

5
4 3 5 2 5

5 5

5
-4 3 -5 2 5

-5 -4

W: Наибольшее произведение двух чисел за O(N)

Решите предыдущую задачу для случая, когда количество чисел в списке не превосходит 100000. Решение должно иметь сложность \(O(n)\). Стандартной сортировкой пользоваться нельзя.

X: Задача Иосифа Флавия

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

Определите номер человека, который останется в кругу последним.

Программа получает на вход числа \(N\) и \(K\), не превосходящие 100 и должна вывести одно число от 1 до \(N\).

5 7

4

В этом примере люди выбывают в таком порядке: 2, 5, 1, 3, остался номер 4.

Y: Наибольшее произведение трех чисел

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

Решение должно иметь сложность \(O(N)\).

Выведите три искомых числа в любом порядке.

Тесты к этой задаче закрытые.

9
3 5 1 7 9 0 9 -3 10

9 10 9

3
-5 –30000 –12

-5 –30000 -12

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

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

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

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

3
2 1 3

2 1 2
1 1 3
2 2 1
1 3 1