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

Задачи из рубрикатора

Тег: Быстрая сортировка

Условие задачи  
ID 37256: Спасаемся от короновируса
Спасаемся от короновируса
Темы: Быстрая сортировка   

МЧС по Лицейской области решил обновить план спасения на случай проникновения короновирусной инфекции. Известно, что дома всех 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 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
Анти-QuickSort
Темы: Быстрая сортировка   

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

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

Примеры

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

ID 31880: Закраска прямой
Закраска прямой
Темы: Быстрая сортировка   

На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка (Li и Ri). Найти длину окрашенной части числовой прямой.
 

Входные данные: В первой строке находится число N, в следующих N строках - пары Li и Ri. Li и Ri - целые, -1 000 000 000 <= Li <= Ri <= 1 000 000 000, 1 <= N <= 15 000
Выходные данные: Вывести одно число - длину окрашенной части прямой.
 
Примеры
Входные данные Выходные данные
1
1
10 20
10
2 1
10 10
0
3 2
10 30
20 40
30

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 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 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 34879: K-квест
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