Сортировка слиянием

8 задач
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Хаос в библиотеке#82079
В библиотеке произошёл полтергейст! Книги на полке перепутались.  Библиотекарь хочет узнать, насколько сильно книги перепутаны.

Мера хаоса - это количество ИНВЕРСИЙ. Инверсия - это пара книг (i, j), где i < j, но книга i должна стоять ПОСЛЕ книги j (то есть номер книги i больше номера книги j).

Каждая книга имеет уникальный номер от 1 до N. Идеальный порядок: 1, 2, 3, ..., N.

Помогите библиотекарю подсчитать количество инверсий!

ВХОДНЫЕ ДАННЫЕ:
Первая строка: число N (1 ≤ N ≤ 100000) - количество книг.
Вторая строка: перестановка чисел от 1 до N - текущий порядок книг на полке.

ВЫХОДНЫЕ ДАННЫЕ:
Одно число - количество инверсий.
 
Использование сортировкиСортировка слиянием
✓ 2✗ 6—Войти и решать
Коллекционирование этикеток#55366
Вася коллекционирует спичечные этикетки. Для этого у него есть N альбомов вместимостью K1, K2, ..., KN этикеток. Вася хочет, чтобы в случае утери одного любого альбома каждая этикетка осталась у него хотя бы в одном экземпляре. Для этого он покупает каждую этикетку в двух экземплярах, и наклеивает их в два разных альбома. Какое максимальное количество различных этикеток при этом может оказаться в его коллекции?

Входные данные
В первой строке  содержится  число N  – количество альбомов.  Во второй строке идет N чисел K1, K2, ..., KN, задающих вместимости альбомов. N  – натуральное число из диапазона от 2 до 1000. Вместимость каждого альбома задается натуральным числом, суммарная вместимость всех альбомов не превышает 100000 этикеток.

Выходные данные
Выведите сначала число E  – максимальное количество различных этикеток, которое может собрать Вася с соблюдением выдвинутого условия. Затем выведите E пар чисел  – каждая пара чисел задает номера двух альбомов, куда будет вклеена очередная этикетка.
Сортировка слиянием
✓ 1✗ 0—Войти и решать
Забор#55365
Как известно, красить забор Тому Сойеру помогали многочисленные друзья. Каждый друг покрасил неcколько подряд идущих досок, при этом какие-то доски могли быть покрашены несколько раз, а какие-то доски могли остаться непокрашенными. Определите общее количество покрашенных досок.

Входные данные
В первой строке содержится натуральное число N ≤ 105  – количество друзей Тома Сойера. Далее идет N пар целых неотрицательных чисел  – номер (от начала забора) доски, с которой друг начал красить забор и номер доски, на которой он закончил покраску. Каждый друг покрасил непрерывный участок забора, включая две заданные доски. Номера досок  – целые числа от 1 до 109.

Выходные данные
Программа должна вывести единственное число  – суммарное количество покрашенных досок.
Сортировка слиянием
✓ 1✗ 0—Войти и решать
Два массива#45674

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i2, у профессора Селезнева i-й член последовательности равен i3. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз. 

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности. 


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

В единственной строке входного файла дано натуральное число i (1 <= i <= 107).


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

Выведите i-е число новой последовательности. 

 
Примеры
№ Входные данные Выходные данные
1 1 1
2 2 4
3 4 9
Вывод формулыРазбор случаевСортировка слиянием
✓ 6✗ 18900средняяВойти и решать
Два массива - 2#45460
Алиса со своим отцом профессором Селезневым записывают на листочке числа. Алиса записала n чисел, профессор Селезнев - m чисел. Алиса и профессор будут рады, если они записали одни и те же числа (без учета кратности). Помогите им определить это, так как им необходимо срочно улетать в очередное космическое путешествие. 
 
Входные данные
В первой строке содержится число n  (1 <= n <= 100000) - количество чисел, записанных Алисой. Во второй строке идет n целых чисел, не превосходящих по модулю 109 – числа Алисы. Третья строка содержит целое число m - количество чисел, записанных профессором Селезневым (1 <= m <= 100000) . В четвертой строке идет m целых чисел, не превосходящих по модулю 109 – числа профессора Селезнева.
 
Выходные данные
Выведите YES, если профессор и Алиса записали одни и те же числа, и слово NO в противном случае.
 
 
Примеры
№ Входные данные Выходные данные
1 3
2 0 7
4
2 0 0 7		 YES
Одномерные массивыСортировка слиянием
✓ 144✗ 959800средняяВойти и решать
Два массива (lite)#45459

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i2, у профессора Селезнева i-й член последовательности равен i3. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз. 

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности. 


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

В единственной строке входного файла дано натуральное число i (1 <= i <= 107).


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

Выведите i-е число новой последовательности. 

 
Примеры
№ Входные данные Выходные данные
1 1 1
2 2 4
3 4 9
Сортировка слиянием
✓ 245✗ 754700средняяВойти и решать
Сортировка слиянием#45458

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


Входные данные
Первая строка входных данных содержит количество элементов в массиве N, N <= 105. Далее идет N целых чисел, не превосходящих по абсолютной величине 109.


Выходные данные
Выведите эти числа в порядке неубывания.
 
Примеры
№ Входные данные Выходные данные
1 2
3 1		 1 3
Сортировка слиянием
✓ 337✗ 674600лёгкаяВойти и решать
Сливаемся!#23375
Слияние двух упорядоченных последовательностей чисел в одну упорядоченную  основная идея сортировки слиянием. Эта сортировка работает быстро, а слияние двух упорядоченных после-
довательностей легко выполняется в том числе и человеком вручную.

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

Входные данные
В первой входного файла строке содержится число N  количество элементов в каждой из исходных последовательностей. Во второй и третьей строках записано по N чисел и знаков вопроса 
содержимое первой и второй последовательности соответственно. В четвертой строке записано 2хN чисел -  результат слияния.
Выходные данные
Вывод должен содержать 2 строки по N чисел в каждой: какой-нибудь из вариантов восстановления исходных последовательностей, которые при слиянии дадут тот же результат. Если
в исходных данных в последовательности стояло число, то в выходных данных на том же месте должно стоять то же число.

Ввод Вывод
2
? 4
3 ?
1 3 4 5		 1 4
3 5

Разбор случаевСортировка слиянием
—Войти и решать
Поделиться
Класснуть