Исп Сорт

Использование сортировки.


Во всех задачах, в условиях которых упомянуты массивы, если это не оговорено особо, размер вспомогательной памяти не должен зависеть от их длин, а число действий пропорционально их длинам. В задачах 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], найти первый общий элемент

  1. если он заведомо есть
  2. если этого заранее неизвестно.

4. (cлияние)
Объединить массивы x[1..n] и y[1..p] в z[1..n+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 точек на плоскости.

  1. Построить n-1-звенную несамопересекающуюся ломаную, проходящую через все эти точки. Число действий порядка n log n.
  2. То же, но ломаная n-звенная замкнутая.

11*.
Построить (при тех же ограничениях) выпуклую оболочку для n точек на плоскости.