                 СОРТИРОВКИ И ПОСЛЕДОВАТЕЛЬНОСТИ.

                            Задача 1.
     Предположим, что  имеется некоторый кусок ленты,  разделенный
на кадры.Кадры занумерованы с двух сторон. Полоска ленты склеена в
лист  Мебиуса.  Необходимо  составить  алгоритм  упорядочения этой
последовательности,  предположив,  что соседние  кадры  можно  пе-
реставлять, (естественно, в упорядоченной последовательности будет
один "скачок" от минимального элемента к  максимальному).  Следует
учесть,что  при  перестановки  кадров переставляются числа с обеих
сторон кадров.Пример:

 Есть 2 кадра ┌──A─┬──B─┐, А1, В1 - одна сторона кадров,
              └────┴────┘  А2, В2 - другая.

     Пусть А1=1, А2=2, В1=7, В2=3. Тогда после перестановки содер-
жащего А <-> В будет А1=7, А2=3, В1=1, В2=2).
     Всегда ли такое упорядочение возможно?

                            Задача 2.
     Имеется N камней веса А1,А2,...,АN.
     Необходимо разбить  их  на  две кучи таким образом,чтобы веса
куч отличались не более чем в 2 раза.  Если этого сделать  нельзя,
то указать это.

                            Задача 3.
     Условие задачи 2,  только веса куч отличаются не более,  чем  в
1,5 раза.

                            Задача 4.
     Имеется N человек и целые числа А1, ..., AN; человека i необ-
ходимо познакомить с Аi людьми. Можно ли это сделать?

                            Задача 5.
     Условие задачи 4. Кого с кем знакомить, чтобы это сделать?

                            Задача 6.
     Даны две  целочисленных таблицы А [1:10] и В[1:15].  Разрабо-
тать алгоритм и написать программу, которая проверяет, являются ли
эти таблицы похожими. Две таблицы называются похожими, если совпа-
дают множества чисел, встречающихся в этих таблицах.

                            Задача 7.
     Задается словарь.  Найти в нем все анаграммы (слова,  состав-
ленные из одних и тех же букв).

                            Задача 8.
     Задано семейство  множеств  букв. Найти такое k, для которого
можно построить множество,  состоящее из k букв,  причем каждая из
них принадлежит ровно k множествам заданного семейства.

                            Задача 9.
     На прямой окрасили N отрезков.Известны координата L[I] левого
конца  отрезка  и  координата  R[I] правого конца I-го отрезка для
I=1, ..., N. Найти сумму длин всех окрашенных частей прямой.
     Примечание. Число N столь велико,  что на выполнение N*N даже
простейших операций не хватит времени.
     МОДИФИКАЦИЯ. На  окружности окрасили N дуг.  Известны угловая
координата L[I] начала и R[I] конца I-ой дуги (от начала  к  концу
двигались,  закрашивая дугу,  против часовой стрелки).  Какая доля
окружности окрашена?

                            Задача 10.
     Имеется 2*N чисел.  Известно что их можно разбить на пары та-
ким образом,что произведения чисел в парах равны.  Сделать разбие-
ние, если числа
     а) натуральные;
     б) целые.

                            Задача 11.
     Имеются числа А1,А2,...,АN и B1,B2,...,BN.  Составить из  них
N пар  (Аi,  Bj) таким образом,  чтобы сумма произведений пар была
максимальна (минимальна). Каждое Ai и Bj в парах встречаются ровно
по одному разу.

                            Задача 12.
     В музее регистрируется в течение дня время  прихода  и  ухода
каждого посетителя. Таким образом за день получены N пар значений,
где первое значение в паре показывает время прихода  посетителя  и
второе значения - время его ухода. Найти промежуток времени, в те-
чение которого в музее одновременно находилось максимальное  число
посетителей.

                            Задача 13.
     Упорядочить по невозрастанию 5 чисел за 7 операций сравнения.

                            Задача 14.
     Задаются число  n>1  -  размерность  пространства и pазмеpы М
n-мерных параллелепипедов (a  , ..., a  ), i=1,...,M.
                            i1        in
     Паpаллелепипед может располагаться в  пространстве  любым  из
способов, при которых его ребра параллельны осям координат. Найти
максимальную последовательность вкладываемых друг в друге паpалле-
лепипедов.

                            Задача 15.
     Пусть A  -  множество из N натуральных чисел.  Ваша программа
должна определить, существует ли по крайней мере одно подмножество
B  множества A,  имеющие cледующее свойство (*) для любых X,Y,Z из
B, X<>Y<>Z<>X,

       X+Y+Z <= SUM {t: t из B\{X,Y,Z}},

тут B\{X,Y,Z} означает 'множество B без элементов X,Y и Z'.
     В случае положительного  ответа  программа  должна  найти
подмножество  B,  удовлетворяющее  условию  (*) и состоящее из
максимально возможного числа элементов.

                            Задача 16.
     Дано положительное целое число К и К целых чисел А(1),...,
А(К). Вычислить
     а) наибольшее,
     b) наименьшее,
     c) наиболее близкое к нулю,
     d) наиболее близкое к заданному числу Р
возможное значение суммы
        S(М,N)=А(М)+А(М+1)+...+А(N-1)+А(N),
где 1<=М<=N<=К.
     Примечание.Число К  столь велико,  что числа А(1),А(2),  ...,
А(К) занимают примерно одну пятую памяти,  отводимой для  хранения
данных,  а  на выполнение К**2 даже простейших операций не хватает
времени.

                            Задача 17.
     Даны целые M и N и вектор действительных чисел X[1..N]. Найти
целое число i (1<=i<=N-M), для которого сумма x[i]+...+x[i+M] бли-
же всего к нулю.

                            Задача 18.
     Есть два отсортированных в порядке неубывания массива  A[1,N]
и B[1,M].  Получить отсортированный по неубыванию массив C[1,N+M],
состоящий из элементов массивов A и B ("слить" вместе массивы A  и
B).
     
                            Задача 19.
     Дан массив  X[1..N].  Необходимо циклически сдвинуть его на k
элементов вправо (т.е.  элемент X[i] после сдвига должен стоять на
месте X[i+k];  тут мы считаем что за X[N] следует X[1]).  Разреша-
ется использовать только несколько дополнительных слов памяти (До-
полнительного массива заводить нельзя!).

                            Задача 20.
     Построить максимальное множество,  состоящее  из  попарно  не
сравнимых векторов v. Векторы v определяются парами чисел, выбира-
емые из данной последовательности чисел а1, ...аn , n>=1. Два век-
тора  v=(а,в)  и  v'=(а',в')  называются сравнимыми,  если а<=а' и
в<=в' или а>=а' и в>= в', в противном случае не сравнимыми.

