Быстрая сортировка


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 31926. Классификация снежинок
Темы: Быстрая сортировка   

Стелла изучает снежинки, измеряя длину их шести лучей, и собрала уже много данных. Теперь Стелла собирается определить, сколько различных видов снежинок ей удалось обнаружить. Она считает снежинки одинаковыми, если снежинки можно совместить после поворота и/или переворачивания.
Напишите программу, которая поможет Стелле провести классификацию снежинок.
Первая строка ввода содержит одно целое число N (2 ≤ N ≤ 100000). Далее следует N строк, содержащих по 6 целых чисел a1 a2 a3 a4 a5 a6 от 1 до 109, разделенных пробелами – длины лучей снежинок в порядке обхода по часовой стрелке.
Вывести одно целое число – количество различных снежинок, обнаруженных Стеллой.

Ввод Вывод
5
1 2 3 4 5 6
3 4 5 6 1 2
3 2 1 4 5 6
6 5 4 3 2 1
2 3 6 5 4 1
2
Примечание
Совпадают снежинки 1 и 2 и 4 после поворота или после переворачивания и снежинки 3 и 5 после переворачивания и поворота.

ID 34879. K-квест
Темы: Бинарный поиск    Быстрая сортировка   

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

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

Комнаты, в которых находятся персонажи, соединены односторонними магическими порталами, поэтому игроку придется встречать персонажей в определенной последовательности: после персонажа номер i он попадает к персонажу номер i + 1, затем к персонажу номер i + 2, и т.д. В комнате последнего персонажа с номером N портала к другому персонажу нет.

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

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

Входные данные
В первой строке входных данных записаны два числа: количество персонажей N и необходимый уровень кармы K (|K| ≤ 109, K ≠ 0). Во второй строке через пробел записаны N целых чисел a1, a2, ..., aN — величины, на которые меняется карма героя после общения с персонажами с номерами 1, 2, ..., N соответственно.

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

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

 

ID 22008. Большая сортировка
Темы: Быстрая сортировка   

Дано число N (\(1<=N<=100000\)), а затем N натуральных чисел из диапазона от 1 до 100.
Выведите N чисел в неубывающем порядке.

Входные данные
В первой строке задается число N - количество элементов массива (\(1<=N<=100000\)).
Далее идет N строк, по одному числу в строке - элементы массива.

Выходные данные 
Выведите на экран отсортированный массив в одну строку.
 
Примеры
Входные данные Выходные данные
1
5
3
1
2
4
2
1 2 2 3 4

ID 31880. Покраска забора
Темы: Быстрая сортировка   

Однажды, в наказание за шалости и обман, тетя Полли заставила Тома красить забор длиной L ярдов. Все вы прекрасно помните, что Том продавал (за различные ништячки) свою работу другим мальчишкам, которые хотели побелить забор.
К тому моменту, когда у Тома закончилась известка, забор успели покрасить N мальчишек. И так как за мальчишками Том не особо следил, то каждый красил ту часть забора, которая ему больше нравилась. 
Каждый i-й мальчишка начинал красить забор с вертикальной дощечки с координатой Lefti и красил до дощечки с координатой Righti (длину дощечки считать равной 1). 
Определите длину забора, которую необходимо будет докрасить Тому самостоятельно. 

 

Входные данные
В первой строке находится число L - длина забора тети Полли. Во второй строке находится число N, в следующих N строках - пары Lefti и Righti. Все числа - целые
Ограничения:
\(0 <= L <= 2 \cdot 10^9\);
 \(-10^9 <= Left_i <= Right_i <= 10^9\);
\(1 <= N <= 15 000\).

Выходные данные
Вывести одно число - длину забора, которую необходимо докрасить Тому.
 
 
Примеры
Входные данные Выходные данные
1
20
1
10 20
10
2 10
1
10 10
10
3 100
2
10 30
20 40
70

ID 37257. Такси
Темы: Быстрая сортировка   

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

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


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

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

Примеры
Входные данные Выходные данные
1 3
10 20 30
50 20 30
1 3 2
2 5
10 20 1 30 30
3 3 3 2 3
5 1 3 2 4

ID 37256. Спасаем роботов
Темы: Быстрая сортировка   

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

Входные данные 
В первой строке вводится число n - количество роботов(\(1 <= n <= 100000\)). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до места работы i-го робота. В третьей строке входных данных задается число m - количество ремонтных мастерских (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-й ремонтной мастерской. Все расстояния положительны и не превышают 109.  Робот и мастерская могут располагаться в одной точке.

Выходные данные
Выведите n чисел - для каждого робота выведите номер ближайшей к нему ремонтной мастерской. Ремонтные мастерские пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.

 
Примеры
Входные данные Выходные данные
1 4
1 2 6 10
2
7 3
2 2 1 1

ID 37258. Бомбоубежища
Темы: Быстрая сортировка   

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

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

Входные данные: В первой строке вводится число n - количество селений (1 <= n <= 100000). Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения. В третьей строке входных данных задается число m - количество бомбоубежищ (1 <= m <= 100000). Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища. Все расстояния положительны и не превышают 109. Селение и убежище могут располагаться в одной точке.

Выходные данные: Выведите n чисел - для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входных данных.

Примеры
Входные данные Выходные данные
1 4
1 2 6 10
2
7 3
2 2 1 1

ID 31879. Анти-QuickSort (на доработке)
Темы: Быстрая сортировка   

Дано число N (1<=N<=1000), а затем N натуральных чисел из диапазона от 1 до 100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что "опорным" будет элемент посередине. 

Входные данные: в первой строке задаётся число N
Во второй строке идут N чисел - элементы массива
Выходные данные: выведите требуемую перестановку элементов исходного массива

Примеры

Входные данные Выходные данные
1 5
3 10 1 20 7
3 20 7 1 10

ID 37691. Анти-QuickSort
Темы: Быстрая сортировка   

Дано число N (\(1<=N<=1000\)), а затем N натуральных чисел из диапазона от 1 до 100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что "опорным" будет элемент посередине. 

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

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

Примеры
Входные данные Выходные данные
1 5 1 4 5 3 2
 
Пояснение
Худшее время работы достигается когда массив разбивается так, что одна часть содержит n−1 элементов, а вторая — 1. Этого можно добиться если на каждом этапе разбиения в середине будет максимальный элемент.
1) 1 4 5 3 2
2) 1 4 2 3 5
3) 1 3 2 4 5
4) 1 2 3 4 5
5) 1 2 3 4 5

 

ID 38920. Эльфы и олени
Темы: Эвристические методы    Бинарный поиск по ответу    Быстрая сортировка    Жадный алгоритм   

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью ai, а каждый эльф – темпераментом bi. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо bj < ai < bk, либо bk < ai < bj.

Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.

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

Входные данные
В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1 ≤ m, n ≤ 100 000).

Вторая строка содержит m целых чисел ai – строптивость оленей ( 0 ≤ ai ≤ 109). В третьей строке записаны n целых чисел bi – темперамент эльфов ( 0 ≤ bi ≤ 109).

Выходные данные
В первой строке  выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: di, ei, 1, ei, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.

Примеры
Входные данные Выходные данные
1 4 6
2 3 4 5
1 3 2 2 5 2
2
1 1 2
3 4 5

ID 38991. Реклама 2
Темы: Пересечение множеств    Быстрая сортировка   

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

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

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

Входные данные
Во входном файле записано сначала число N — количество покупателей, посетивших супермаркет за день(1<N<3000). Затем идет N пар натуральных чисел Ai, Bi, задающих соответственно время прихода и время ухода покупателей из супермаркета (0<Ai<Bi<106).

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

Если решений несколько, выведите любое из них.
 

Примеры
Входные данные Выходные данные
1 5
1 10
10 12
1 10
1 10
23 24
5
5 10 12 23 24