--->
9 задач
<---
Источники
Отсортируйте данный массив, используя сортировку слиянием.
Первая строка входных данных содержит количество элементов в массиве N, N ≤ 105. Далее идет N целых чисел, не превосходящих по абсолютной величине 109.
Выведите эти числа в порядке неубывания.
2 3 1
1 3
Назовем два массива похожими, если они состоят из одних и тех же элементов (без учета кратности). По двум данным массивам выясните, похожие они или нет.
В первой строке содержится число N (1 ≤ N ≤ 100000) – размер первого массива. Во второй строке идет N целых чисел, не превосходящих по модулю 109 – элементы массива. Далее аналогично задается второй массив.
Программа должна вывести слово YES, если массивы похожи, и слово NO в противном случае.
3 1 7 9 4 9 7 7 1
YES
Как известно, красить забор Тому Сойеру помогали многочисленные друзья. Каждый друг покрасил неcколько подряд идущих досок, при этом какие-то доски могли быть покрашены несколько раз, а какие-то доски могли остаться непокрашенными. Определите общее количество покрашенных досок.
В первой строке содержится натуральное число N ≤ 105 – количество друзей Тома Сойера. Далее идет N пар целых неотрицательных чисел – номер (от начала забора) доски, с которой друг начал красить забор и номер доски, на которой он закончил покраску. Каждый друг покрасил непрерывный участок забора, включая две заданные доски. Номера досок – целые числа от 1 до 109.
Программа должна вывести единственное число – суммарное количество покрашенных досок.
3 1 2 3 4 2 3
4
Вася коллекционирует спичечные этикетки. Для этого у него есть N альбомов вместимостью K1, K2, ..., KN этикеток. Вася хочет, чтобы в случае утери одного любого альбома каждая этикетка осталась у него хотя бы в одном экземпляре. Для этого он покупает каждую этикетку в двух экземплярах, и наклеивает их в два разных альбома. Какое максимальное количество различных этикеток при этом может оказаться в его коллекции?
В первой строке содержится число N – количество альбомов. Во второй строке идет N чисел K1, K2, ..., KN, задающих вместимости альбомов. N – натуральное число из диапазона от 2 до 1000. Вместимость каждого альбома задается натуральным числом, суммарная вместимость всех альбомов не превышает 100000 этикеток.
Выведите сначала число E – максимальное количество различных этикеток, которое может собрать Вася с соблюдением выдвинутого условия. Затем выведите E пар чисел – каждая пара чисел задает номера двух альбомов, куда будет вклеена очередная этикетка.
4 1 2 1 1
2
Ассоциация Тапкодер организует Всемирное парное соревнование сильнейших программистов. К участию в соревновании допущены первые 2k зарегистрировавшихся участников, которым присвоены номера от 1 до 2k.
Соревнование будет проходить по олимпийской системе. В первом туре первый участник встречается со вторым, третий с четвертым и так далее. В каждой паре победителем становится участник, первым решивший предложенную задачу, при этом ничьих не бывает. Все победители очередного тура и только они являются участниками следующего тура. В каждом туре пары составляются из участников в порядке возрастания присвоенных им номеров. Соревнование продолжается до тех пор, пока не останется один победитель.
Организаторам стало известно, что некоторые пары участников заранее договорились о результате встречи между собой, если такая встреча состоится. Для всех остальных встреч, кроме n договорных, возможен любой исход.
Некоторые m участников соревнования представили свои резюме в ассоциацию Тапкодер с целью поступления на работу. Организаторов интересует, до какого тура может дойти каждый из претендентов при наиболее благоприятном для него стечении обстоятельств. При этом для каждого участника в отдельности считается, что все недоговорные встречи, в том числе те, в которых он не участвует, закончатся так, как ему выгодно, а все состоявшиеся договорные встречи закончатся в соответствии с имеющимися договоренностями.
Требуется написать программу, которая для каждого из претендентов определяет максимальный номер тура, в котором он может участвовать.
В первой строке заданы три целых числа k (1 ≤ k ≤ 60), n (0 ≤ n ≤ 100 000) и m (1 ≤ m ≤ 100 000). В следующих n строках описаны n пар участников, которые договорились между собой о том, что первый из двух участников пары выиграет встречу, если она состоится. Гарантируется, что каждая пара участников присутствует во входных данных не более одного раза, при этом, если задана пара x y, то пары y x быть не может, кроме того, x ≠ y. В последней строке перечислены номера участников, желающих работать в Тапкодере, в порядке возрастания их номеров. Все номера претендентов на работу различны.
Выходные данные должны содержать m целых чисел — максимальные номера туров, до которых могут дойти соответствующие претенденты на работу. Туры нумеруются от 1 до k.
Комментарии к примерам тестов.
1. У каждого из участников есть возможность выйти в финал, так как договорных матчей нет.
2. Если четвертый участник выиграет у третьего, то договорная встреча первого и третьего не состоится, что благоприятно для первого.
3. Первому участнику благоприятно во втором туре играть с третьим, а не с четвертым, в свою очередь, четвертый может выиграть у третьего и также выйти в финал.
Тесты к этой задаче состоят из четырех групп, баллы начисляются только при прохождении всех тестов группы и всех тестов предыдущих групп.
0. Тесты 1–10. k <= 5. Эта группа оценивается в 30 баллов.
1. Тесты 11–14. k <= 20. Эта группа оценивается в 20 баллов.
2. Тесты 15–18. k <= 30. Эта группа оценивается в 20 баллов.
3. Тесты 19–23. Дополнительные ограничения отсутствуют. Эта группа оценивается в 30 баллов.
2 0 3 1 3 4
2 2 2
3 1 1 3 1 1
3
3 3 4 1 2 1 3 4 1 1 2 3 4
3 1 2 3