| **Во всех задачах, в условиях которых упомянуты массивы, если это не оговорено особо, размер вспомогательной памяти не должен зависеть от их длин, а число действий пропорционально их длинам. В задачах 1 – 7 массивы предполагаются отсортироваными. В задачах 8 – 12 Число действий должно быть порядка n log n. |
1.
Найти для массива x[1..n] число различных элементов (Число действий Cn)
2.
Найти для массивов x[1..n] и y[1..p] их пересечение, т.е. общие элементы с учетом кратности (Число действий Cn+p)
3.
Для массивов x[1..n], y[1..p] и z[1..q], найти первый общий элемент
4. (cлияние)
Объединить массивы x[1..n] и y[1..p] в z[1..n+p].
5.
Найти для массивов x[1..n] и y[1..p] число различных элементов (Число действий Cn+p)
6.
Сумму вида x[i] + y[j] наиболее близкую к заданному числу a. (Число действий Cn+p; исходные массивы запрещено менять.)
7. (двоичный поиск)
В x[1..n] найти число заданное a. Число действий порядка log n
8.
Для массива x[1..n] найти наименьшее натуральное a, непредставимое в виде суммы каких-либо его элементов. Число действий порядка n log n.
9.
Дано n отрезков на прямой. Найти максимальное K (по всем точкам прямой) такое, что точка покрыта K слоями отрезков. Число действий порядка n log n
10.
Дано n точек на плоскости.
11*.
Построить (при тех же ограничениях) выпуклую оболочку для n точек на плоскости.
12.
Во входном файле записано n больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется написать программу, которая из данных букв по указанным правилам составит палиндром наибольшей длины, а если таких палиндромов несколько, то первый в алфавитном порядке. Число действий порядка n log n.