| Условие задачи | | Прогресс |
|
Темы:
Сортировка слиянием
Отсортируйте данный массив, используя сортировку слиянием.
Входные данные
Первая строка входных данных содержит количество элементов в массиве N, N <= 105. Далее идет N целых чисел, не превосходящих по абсолютной величине 109.
Выходные данные
Выведите эти числа в порядке неубывания.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
2
3 1 |
1 3 |
| |
![]()
|
|
Темы:
Сортировка слиянием
Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i2, у профессора Селезнева i-й член последовательности равен i3. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз.
Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности.
Входные данные
В единственной строке входного файла дано натуральное число i (1 <= i <= 107).
Выходные данные
Выведите i-е число новой последовательности.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 |
1 |
| 2 |
2 |
4 |
| 3 |
4 |
9 |
| |
![]()
|
|
Темы:
Сортировка слиянием
Одномерные массивы
Алиса со своим отцом профессором Селезневым записывают на листочке числа. Алиса записала n чисел, профессор Селезнев - m чисел. Алиса и профессор будут рады, если они записали одни и те же числа (без учета кратности). Помогите им определить это, так как им необходимо срочно улетать в очередное космическое путешествие.
Входные данные
В первой строке содержится число n (1 <= n <= 100000) - количество чисел, записанных Алисой. Во второй строке идет n целых чисел, не превосходящих по модулю 10 9 – числа Алисы. Третья строка содержит целое число m - количество чисел, записанных профессором Селезневым (1 <= m <= 100000) . В четвертой строке идет m целых чисел, не превосходящих по модулю 10 9 – числа профессора Селезнева.
Выходные данные
Выведите YES, если профессор и Алиса записали одни и те же числа, и слово NO в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3
2 0 7
4
2 0 0 7 |
YES |
| |
![]()
|
|
Темы:
Сортировка слиянием
Вывод формулы
Разбор случаев
Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i2, у профессора Селезнева i-й член последовательности равен i3. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз.
Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности.
Входные данные
В единственной строке входного файла дано натуральное число i (1 <= i <= 107).
Выходные данные
Выведите i-е число новой последовательности.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1 |
1 |
| 2 |
2 |
4 |
| 3 |
4 |
9 |
| |
![]()
|
|
Темы:
Сортировка слиянием
Как известно, красить забор Тому Сойеру помогали многочисленные друзья. Каждый друг покрасил неcколько подряд идущих досок, при этом какие-то доски могли быть покрашены несколько раз, а какие-то доски могли остаться непокрашенными. Определите общее количество покрашенных досок.
Входные данные
В первой строке содержится натуральное число N ≤ 105 – количество друзей Тома Сойера. Далее идет N пар целых неотрицательных чисел – номер (от начала забора) доски, с которой друг начал красить забор и номер доски, на которой он закончил покраску. Каждый друг покрасил непрерывный участок забора, включая две заданные доски. Номера досок – целые числа от 1 до 109.
Выходные данные
Программа должна вывести единственное число – суммарное количество покрашенных досок.
| |
![]()
|
|
Темы:
Сортировка слиянием
Вася коллекционирует спичечные этикетки. Для этого у него есть N альбомов вместимостью K1, K2, ..., KN этикеток. Вася хочет, чтобы в случае утери одного любого альбома каждая этикетка осталась у него хотя бы в одном экземпляре. Для этого он покупает каждую этикетку в двух экземплярах, и наклеивает их в два разных альбома. Какое максимальное количество различных этикеток при этом может оказаться в его коллекции?
Входные данные
В первой строке содержится число N – количество альбомов. Во второй строке идет N чисел K1, K2, ..., KN, задающих вместимости альбомов. N – натуральное число из диапазона от 2 до 1000. Вместимость каждого альбома задается натуральным числом, суммарная вместимость всех альбомов не превышает 100000 этикеток.
Выходные данные
Выведите сначала число E – максимальное количество различных этикеток, которое может собрать Вася с соблюдением выдвинутого условия. Затем выведите E пар чисел – каждая пара чисел задает номера двух альбомов, куда будет вклеена очередная этикетка.
| |
![]()
|