Темы --> Информатика --> Алгоритмы --> Алгоритмы сортировки --> Квадратичные сортировки
    Сортировка "пузырьком"(11 задач)
    Сортировка выбором (максимума)(5 задач)
    Сортировка вставками(4 задач)
---> 3 задач <---
Источники --> Командные олимпиады --> Московская командная олимпиада
    8 класс(18 задач)
    9-11 классы(228 задач)
Страница: 1 Отображать по:
#37
\"Сортировка\" с конфеткой
  

Дан массив из N различных натуральных чисел от 1 до N. Сортировка массива по возрастанию "пузырьком" работает следующим образом. Сначала сравниваются первый и второй элемент, и, если первый больше второго, то они меняются местами. Затем та же процедура производится со вторым и третьим элементом, …, с предпоследним и последним. Затем эта процедура снова повторяется с первым и вторым, со вторым и третьим, …, с предпоследним и последним элементами. И так (N – 1) раз.

Сортировка «с конфеткой» выполняется по тем же правилам, но дополнительно задан список пар чисел, которые не меняются друг с другом ни при каких условиях (в таком случае сортирующий получает конфетку за то, что пропускает соответствующий обмен). Например, наличие в списке пары (4,1) обозначает, что если в какой-то момент рядом окажутся числа 4 и 1 или 1 и 4, и по алгоритму сортировки их нужно будет поменять местами, то обмена не произойдет, а сортирующий получит конфетку.

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

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

Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

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

Требуется вывести массив после сортировки.

Примеры
Входные данные
4
1 4 2 3
2
4 3
1 2
Выходные данные
1 2 4 3
#39
Обувной магазин
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Примеры
Входные данные
60
2
60 63
Выходные данные
2
Входные данные
26 
5
30 35 40 41 42
Выходные данные
3
#3585
Народный IPO
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Компания «Рога и копыта» решила провести народный IPO (первоначальное публичное предложение акций компании на продажу широкому кругу лиц). Как обычно у Остапа Бендера не обошлось без аферы.

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

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

Тем не менее, изменяя порядок удовлетворения заявок покупателей можно влиять на количество вырученных денег. Помогите Остапу Бендеру наиболее выгодно продать «Рога и копыта». Акций у компании так много, что Остап может продать любой процент акций, в том числе дробный.

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

В первой строке задано количество людей, подавших заявки N (1 ≤ N ≤ 1000). Далее следуют N строк по два числа в каждой: натуральное число, не превосходящее 100 — часть компании в процентах, которую хочет купить очередной человек и натуральное число не превоходящее 109 — количество денег, которое он заплатит за 1 процент от общего количества акций компании.

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

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

Примечание

В первом тесте выгоднее сначала удовлетворить заявку второго человека, в результате чего будет продано 25% акций компании. Первому человеку будет продано 25% от оставшейся части (т.е. 18,75% от общего числа акций). Суммарная выручка в таком случае составит 25 × 10 + 18, 75 × 5 = 343, 75 рублей.

Примеры
Входные данные
2
25 5
25 10
Выходные данные
2 1
Входные данные
3
10 30
20 15
30 10
Выходные данные
1 2 3
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест