e-olymp 1462. Хитрая сортировка

Задача

Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих чисел.

Входные данные

Первая строка содержит число [latex] n [/latex] ([latex] 1 \leqslant n \leqslant 100 [/latex]), а вторая — сами натуральные числа, не превышающие [latex] 32000 [/latex].

Выходные данные

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

Входные данные Выходные данные
1 7
12 15 43 13 20 1 15
20 1 12 13 43 15 15
2 10
82 22 19 90 34 17 588 921 200 121
90 200 121 921 22 82 34 17 588 19
3 4
162 9801 37 14
9801 162 14 37

Код программы

 

Решение задачи

Для решения этой задачи необходимо объявить массив, с размером [latex] n [/latex], который будет хранить все числа, введенные пользователем.
Сортировку будем проводить в циклах for для сравнения соседних чисел и смены их позиции с помощью функции swap. Если последняя цифра следующего числа меньше предыдущего, то эти числа меняются местами. Если их последние цифры одинаковые, то сравниваются сами числа.
В конце выводим массив array[n].

Ссылки

Условие на e-olymp

Решение на e-olymp

Решение на ideone.com

e-olymp 1462. Хитрая сортировка

Задача

Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих чисел.

Входные данные

Первая строка содержит число  $n \ (1 \leqslant n \leqslant 1000)$, а вторая — сами натуральные числа, не превышающие $32000$.

Выходные данные

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

Входные данные Выходные данные
1 7
12 15 43 13 20 1 15
12 33 14 44 64 77
2 4
345 112 999 29
112 345 29 999
3 9
78 33 13 0 12 89 20 78 9990
0 20 9990 12 13 33 78 78 89

Код

Решение

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

Ссылки

e-olymp 2662. Метод минимума

Условие задачи

Массив сортируется методом выбора по возрастанию. Сколько раз меняет свое место первый по порядку элемент?

Входные данные

Первая строка содержит количество элементов в массиве $n$ $\left(1\leqslant n\leqslant1000\right)$. Во второй строке задан сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10^9$.

Выходные данные

Вывести количество перемещений первого элемента.

Тесты

Ввод Вывод
1 3

1 3 2

0
2 2

2 1

1
3 4

4 1 5 3

3
4 6

23 5 56 2 87 3

1
5 7
15 1 6 3 9 8 13
4

Код программы

Решение

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

Подробное изложение алгоритма сортировки можно найти в  этой статье .

Ссылки

e-olymp 2663. Сортировка пузырьком

Условие

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

Входные данные

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$$9$.

Выходные данные

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

Тесты

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

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

Код программы

Ссылки

решение на e-olymp
код на ideone

e-olymp 9410. Студенческая любовь

Задача

Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношенияКоэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?

Входные данные

Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.

Выходные данные

Выведите одно число — ответ на задачу.

Тесты

Входные данные

Выходные данные

1
2
-3 -5
3 5
0
2 1
5
-2
0
3 5
-5 -2 -1 0 4
5 4 0 0 -1
4
4 9
1000 -22 333 -56 1 2 -77 -650 10
-7 166 -333 90 -565 12 788 -800 111
523

Код программы

Решение

Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.

Ссылки

Условие задачи e-olymp

Код решения ideone

e-olymp 145. Квадраты

Задача взята с сайта e-olymp

Задача

Заданы длины $n$ отрезков. Какое наибольшее количество квадратов можно из них составить? Сторона каждого квадрата должна состоять только из одного отрезка.

Входные данные

В первой строке находится количество отрезков $n \left(1 \leqslant n\leqslant 10^6\right)$. Во второй строке заданы $n$ натуральных чисел — длины отрезков, числовые значения которых не превышают $100$.

Выходные данные

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

Тесты

#   ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 9
2 2 4 2 3 2 1 2 4
1
2 11
2 2 4 2 2 4 2 2 1 2 2
2
3 5
8 9 8 9 11
0

Код программы

Решение

Пусть имеется $k$ отрезков одинаковой длины. Тогда из них можно составить $\frac{k}{4}$ квадрата. Длины отрезков изменяются от $1$  до $100$. Подсчитываем количество отрезков длины $i\left(1\leqslant i\leqslant 100\right)$ в массив $a\left[i\right]$. Тогда максимально возможное количество квадратов, которое можно составить из данных отрезков, равно $$\frac{a\left[1\right]+a\left[2\right]+\dots +a\left[100\right]}{4}.$$
Для этого совершим сортировку подсчетом. В ячейке a[i] подсчитываем количество отрезков длины i . В переменную res  подсчитываем количество квадратов, которое можно построить.

Ссылки

Условие задачи на e-olymp

Код программы на ideone

Сортировка подсчетом на Wikipedia

А291а

Задача: А291а

Условие:

Даны действительные числа [latex]a_{1},\ldots,a_{30}.[/latex] Получить [latex]\max (a_{1}+ a_{30},a_{2}+a_{29},\ldots,a_{15}+a_{n}).[/latex]

Тесты:

Входные данные Выходные данные
1 2 3 5 4 8
2 2 3 7 5 4 14
3 4.5 1.1 3 9.25 0.75 10.35
4 -4.5 -2 0 -7.1 5 0.5

Код программы:

Решение:

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

Ссылки:

Задачник по программированию С. Абрамова.

Код программы на ideone.com.

e-olymp 4003. Топологическая сортировка

Задача взята отсюда.

Условие

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

Входные данные

В первой строке содержатся два натуральных числа [latex]n[/latex] и [latex]m[/latex] ([latex]1 \leq n \leq 10^5[/latex], [latex]1 \leq m \leq 10^5[/latex]) — количество вершин и рёбер в графе соответственно. Далее в [latex]m[/latex] строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно.

Выходные данные

Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести [latex]-1[/latex].

Решение

Для решения использовался алгоритм топологической сортировки методом поиска в глубину (подробнее в комментариях к коду). Функция bool dfs() (поиск в глубину) также проверяет, цикличен ли граф, т.к. по условию он может как содержать, так и не содержать циклы. Результат сортировки заносим в вектор result, потом выводим его элементы по порядку.

Тесты

Входные данные Выходные данные
1 6 6
1 2
3 2
4 2
2 5
6 5
4 6
 4 6 3 1 2 5
2  3 3
1 2
2 3
3 1
 -1
3 4 4
1 4
4 3
3 2
4 2
 1 4 3 2

Код

Ссылки

Код на ideaone.

Засчитанное решение на e-olymp.

Наглядное объяснение топологической сортировки здесь.

e-olimp 1667. Конденсация графа

Задача e-olimp.com №1667. Ссылка на засчитанное решение.

Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите  компоненты  сильной связности заданного графа и топологически отсортируйте его конденсацию.

Входные данные

Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра — два целых числа из диапазона от [latex]1[/latex]  до [latex]N[/latex] — номера начала и конца ребра.

Выходные данные

В первой строке выведите число [latex]K[/latex] — количество компонент сильной связности в заданном графе. В следующей строке выведите [latex]N[/latex] чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Тесты:

6 7 

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19 

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

Иллюстрация к первому тесту:

1

Иллюстрация ко второму тесту:

1

Код программы:

Алгоритм решения

Прежде всего топологически сортируем граф [latex]G[/latex] (с помощью функции dfs_1), записывая результат в вектор order. В итоге первой вершиной этого вектора окажется некая вершина [latex]u[/latex], принадлежащая «корневой» компоненте сильной связности, то есть в которую не входит ни одно ребро в графе конденсаций.

Теперь нужно сделать такой обход из этой вершины, который посетил бы только эту компоненту сильной связности и не зашёл бы ни в какую другую. Для этого служит функция dfs_2, которая применяется к траспонированному графу [latex]G^{T}[/latex] (граф, полученный из [latex]G[/latex] изменением направления каждого ребра на противоположное). В этом графе будут те же компоненты сильной связности, что и в исходном графе. Пусть [latex]G^{*}[/latex] — это граф конденсации, получаемый из данного графа сжатием каждой компоненты сильной связности в одну вершину (очевидно, что он ацикличен). Тогда [latex]\left(G^{T} \right)^{*}[/latex] будет равен транспонированному графу конденсации исходного графа [latex]G^{*}[/latex]. Это значит, что теперь из рассматриваемой нами «корневой» компоненты уже не будут выходить рёбра в другие компоненты.

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

Таким образом, чтобы обойти всю «корневую» компоненту сильной связности, содержащую некоторую вершину [latex]u[/latex], достаточно запустить обход из этой вершины в графе[latex]G^{T}[/latex]. Этот обход посетит все вершины этой компоненты сильной связности и только их. Дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением времени выхода и запускать обход на транспонированном графе из неё.

Так после каждого запуска dfs_2 в векторе component окажутся все вершины, принадлежащие одной компоненте связности. Поэтому каждой из тих вершин присваиваем номер компоненты, после чего вектор component чистится и идёт новая итерация (номер компоненты при этом увеличивается на 1).

М16. Freshly Pressed Juice

Формулировка задачи

Известно, что каждый посетитель фруктового бара просит сделать наиболее дешевый коктейль из свежевыжатого сока. Объем стакана для сока V. Рассчитайте стоимость и сформируйте рецепт коктейля, который достанется n-тому посетителю. V и n читаются из входного потока. Во входном потоке имеется неизвестное количество строк – справочник в котором для каждого вида фруктов указано его название, текущая стоимость за килограмм, процент выхода сока и количество фруктов на складе.
а) Прочитать справочник в список (vector) соответствующих структур.
б) Сформировать рецепт и рассчитать стоимость наиболее дешёвого коктейля.

Тесты

[latex]V[/latex] [latex]n[/latex] [latex]Menu[/latex] [latex]Recipe[/latex] Комментарий
150 2 Apple 10 60 200

Cherry 20 70 50
Sorry, we are closed for today Объем фруктов на складе меньше 300.
80 8 Dragonfruit 123 50 10

Aplle 10 60 200

Cherry 40 80 100

Coconut 20 5 30

Pineapple 80 90 50

Raspberry 70 95 30

Blackberry 130 95 30

Strawberry 60 95 40

Grape 20 95 120

Orange 10 80 200

Melon 10 98 300

Banana 20 30 120
Apple 80 800 В самом деле, более выгодным будет использование только арбузов и апельсинов, израсходованных ранее.
80 14 (см. тест № 2) Banana 40.000000

Raspberry 30.000000

Pineapple 10.000000

3700
Корректно
110 1 (см. тест №2) Melon 110 1100 Корректно

Анализ задачи

  1. Параметры «количество», «удельная стоимость», «процент выхода сока» описывают сущность типа «фрукт». Следовательно, необходимо создать одноименную структуру, связав конкретное наименование в меню (списке) с его количественными характеристиками.
  2. Условие задачи можно переформулировать как поиск наиболее выгодного фрукта по соотношению (у.е./куб.ед.) — фрукта, из единицы массы которого можно дешевле всего получить кубическую единицу объема, [latex]\frac {price}{volume}[/latex]. Данные, необходимые для сортировки фруктов в порядке возрастания стоимости единицы объема сока, присуствуют в исходных данных. Подробнее: [latex]\frac {price}{volume} = \frac {amount*specificCost}{amount*percentage*\rho} = \frac {specificCost}{percentage*\rho}[/latex]. В условии не указано обратное, потому плотность сока принята равной [latex]\rho = 1[/latex](г/мл). Окончательно, [latex]worth = \frac {specificCost}{percentage}[/latex].

Алгоритм решения

    • Объявить структуру [latex]fruit[/latex] с переменными:
      • name
      • specific_cost
      • percentage
      • amount
    • Необходимо
      1. считывать информацию о фрукте;
      2. сортировать фрукты по некоторому параметру

      Следовательно, уместно определить методы [latex]get()[/latex] и [latex]worth()[/latex] соответственно.

  1. Дальнейшее решение распадается на несколько подзадач:
    1. Сортировка элементов вектора в порядке убывания стоимости единицы объема.
    2. Поиск фруктов, доступных в момент, когда [latex]n[/latex]-ый посетитель делает заказ.
    3. Составление коктейля наименьшей стоимости при заданном объёме порции.

    Был намечен следующий алгоритм действий:

    1. После сортировки определить, какая масса фруктов должна быть израсходована к моменту заказа, и последовательно проходить по вектору, уменьшая количество каждого фрукта, пока не дойдем до требуемого значения.
    2. Если оставшихся фруктов достаточно для приготовления коктейля, последовательно перерабатывать фрукты, пока на складе не закончится текущее наименование, а тогда перейти к следующему, и так пока не прийдем к заданному объему.
    3. На каждом шаге добавлять в рецепт количество использованных фруктов вместе с их названиями. В конце рецепта указать стоимость коктейля.

Программный код

Программа доступна для тестирования по ссылке: http://ideone.com/qj8ovB.

Подробности реализации

Из интереса и эксперимента ради решение было запрограммировано в двух вариантах: в процедурном, в духе классического языка C, и средствами стандарта C++11. Вторая версия получилась более лаконичной, но, при необходимости, может быть предъявлена и первая.

  1. После считывания списка переменная [latex]total amount[/latex] хранит в себе общее количество всех фруктов на складе.
  2. Метод [latex]get()[/latex] возвращает значение булевого типа, так как таким образом можно производить чтение до конца файла средствами [latex]cin[/latex], с автоматической проверкой.
  3. Для работы только с фруктами, доступными в момент совершения заказы [latex]n[/latex]-м посетителем, была создана переменная [latex]used[/latex], хранящая объем всех коктейлей, сделанных для предыдущих посетителей. В цикле [latex]any of()[/latex] на каждом шаге происходит уменьшение переменной [latex]used[/latex] на доступную массу фруктов данного типа. Для наглядности восприятия введена переменная [latex]new amount[/latex]. Если оставшееся на складе количество фруктов позволяет сделать ещё один коктейль, происходит вход во внутренний цикл. В противном случае, пользователя уведомляют о том, что выполнение заказа невозможно.
  4. Во внутреннем цикле, который выполняется, пока не наберется достаточный объем сока, на каждом шаге берут максимально возможное количество фрукта данного типа. Рецепт сохраняется в строку [latex]recipe[/latex].
  5. В лямбда-выражения параметры из тела программы передаются по ссылке. Возможность их изменения гарантируется ключевым словом [latex]mutable[/latex].