для тех кто в ещё может! :-)

← →
gn © (2004-04-01 22:36) [0]

Сортировки и последовательности
Задача 1.
Предположим, что имеется некоторый кусок ленты, разделенный на кадры. Кадры занумерованы с двух сторон. Полоска ленты склеена в лист Мебиуса. Необходимо составить алгоритм упорядочения этой последовательности, предположив, что соседние кадры можно переставлять, (естественно, в упорядоченной последовательности будет один "скачок" от минимального элемента к максимальному). Следует учесть, что при перестановки кадров переставляются числа с обеих сторон кадров. Пример:
Есть 2 кадра
А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-мерных параллелепипедов (ai1 , ..., ain), i=1,...,M.
Паpаллелепипед может располагаться в пространстве любым из способов, при которых его ребра параллельны осям координат. Найти максимальную последовательность вкладываемых друг в друге паpаллелепипедов.
Задача 15.
Пусть A - множество из N натуральных чисел. Ваша программа должна определить, существует ли по крайней мере одно подмножество B множества A, имеющие cледующее свойство (*) для любых X,Y,Z из B, X<>Y<>Z<>X,
X+Y+Z <=е {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"=(а",в") называются сравнимыми, если а<=а" и в<=в" или а>=а" и в>= в", в противном случае не сравнимым

gn
cn 1101

← →
gn © (2004-04-01 22:56) [1]

чёт народ припател это задачи за 8 клас школы
Если мы будем переставлять кадр A с соседним с ним справа, пока A не пройдет всю ленту Мебиуса и не вернется на свое место, то окажется, что стороны кадра поменяются - то, что раньше было A1 станет B1, и наоборот.
Разрежем ленту. Из замечания выше следует, что мы можем полагать, что на одной стороне ленты в каждом кадре написано минимальное из чисел, находящихся на сторонах кадра. Упорядочиваем элементы этой стороны ленты по неубыванию, Если и на другой стороне элементы выстроились по неубыванию, и при этом последний элемент первой стороны не превышает первого элемента второй стороны, то поставленная задача решена, иначе упорядочение невозможно.
Решение задачи 2.
Основная стратегия решения заключается в том, что каждый следующий камень кладется в кучу с меньшим текущим весом. При этом в первую кучу надо положить камень максимального веса. Покажем, что этого достаточно, чтобы гарантировать правильное решение задачи. По окончании распределения камней по кучам возможны 2 ситуации:
1. Все камни попали во вторую кучу, а ее вес остался меньше половины веса первой кучи. Понятно, что в этом случае камни требуемым образом разбить нельзя, следовательно решения не существует.
2. Случай 1. не верен. Тогда возможны следующие ситуации.
а) Все камни попали во вторую кучу. В этом случае ясно, что веса куч отличаются не более чем на половину первой кучи, если вес первой кучи больше, или не более чем вес последнего камня, положенного во вторую кучу. В любом из этих случаев требуемое условие выполняется.
б) В первую кучу попали и другие камни. Тогда ясно, что веса куч отличаются не более чем на вес самого тяжелого камня, кроме первого. Следовательно и в этом случае условие задачи выполняется.
Решение задачи 3.
На начальном этапе в первую кучу кладется самый тяжелый камень, а во вторую - два следующих по весу камня. Для оставшихся камней реализуется описанная для задачи 2 стратегия.
Задачи 4, 5.
Алгоритм состоит в следующем. На каждом шаге находится человек Х, имеющий наибольшее число Р нереализованных знакомств. Затем находится Р людей, с которыми человек Х собирается реализовать знакомства. Нетрудно понять, что это должны быть люди опять же с наибольшим числом нереализованных знакомств, так как такая стратегия обеспечивает на каждом шаге максимально возможное количество людей с нереализованными еще знакомствами. Человек Х реализует по одному знакомству с каждым из Р выбранных людей и из дальнейшего процесса исключается. При этом число нереализованных знакомств у каждого из Р людей уменьшается на 1. Процесс продолжается до тех пор, пока все знакомства не будут реализованы, или найдется такой человек Х, которому не хватит людей для реализации его нереализованных знакомств. В последнем случае задача не имеет решения. Для поиска человека Х и Р людей для реализации знакомств достаточно каждый раз упорядочивать значения нереализованных знакомств в порядке невозрастания, сохраняя при этом информацию о "имени" (исходном номере) человека.
Решение задачи 6.
Мы можем отсортировать оба массива - и A, и B (например, по неубыванию), далее, если первые элементы массивов A и B совпадают, то ищем и в A, и в B минимальные элементы, большие данного, и повторяем сравнения; если же элементы не совпадают, либо один из массивов уже закончился, а другой еще нет, то массивы не похожие.
{A и B уже отсортированы}
i:=1; j:=1; {смотрим массивы A и B, начиная с первых элементов}
while (i<=10) and (j<=15) and (A[i]=B[j]) do
begin
element:=A[i];
while (i<=10) and (A[i]=element) do
i:=i+1; {поиск несовпадающего элемента}
while (j<=15) and (B[j]=element) do
j:=j+1; {поиск несовпадающего элемента}
end;
if (i=11) and (j=16) {просмотрели все элементы A и B}
then writeln("Массивы похожи")
else writeln("Массивы непохожи");
Решение задачи 7.

← →
gn © (2004-04-01 22:57) [2]

Каждому слову приписываем его номер в словаре. Сначала сортируем буквы в каждом слове по (например) неубыванию. Получаем какой-то "ключ", который совпадает у всех слов-анаграмм (например, слова "лом" и "мол" преобразуются в одни и те же ключи "лмо").
Далее мы сортируем ключи слов (совместно с приписанными номерами) по неубыванию. Все одинаковые ключи будут размещаться в отсортированной последовательности слов друг за другом. Мы просматриваем полученную последовательность, ищем совпадающие ключи и по приписанным им номерам находим в словаре соответствующие слова-анаграммы.
Решение задачи 8.
Для каждой буквы заведем отдельный "черпак", в который будем "складывать" букву. Это можно сделать, используя массив А из 255 элементов. При этом номер "черпака", соответствующего некоторой букве, определяется кодом буквы (известно, что любая буква кодируется некоторым двоичным числом, содержащим 8 цифр - называемых битами; в Паскале по букве определить ее код можно с помощью функции ord). При просмотре множеств подсчитаем, сколько раз встречалась каждая буква. Это делается следующим образом. При встрече буквы содержимое соответствующего ей элемента массива увеличиваем на 1. При этом начальное содержимое элементов массива - 0. После просмотра букв всех множеств элементы А определяют количество соответствующих букв, а значит и количество множеств, которым принадлежит соответствующая буква (ведь в одном множестве все элементы различны!). Используя аналогичным образом массив В из 255 элементов (больше не нужно, так как искомое число к по условию не превышает числа букв) подсчитаем количество единиц, двоек и т.д. в массиве А. Максимальное значение индекса к, для которого к=В[к] и будет решением поставленной задачи.
Решение задачи 9.
Будем моделировать закрашивание этих N отрезков.
Достаточно отсортировать отрезки в порядке неубывания координат левых концов. После этого осуществляется простой просмотр упорядоченных отрезков с анализом следующих возможных ситуаций:
1. Если текущий отрезок пересекается с закрашиваемым отрезком (его левая координата не больше правого конца закрашиваемого отрезка), то новым правым концом закрашиваемого сейчас отрезка становится более правый из концов закрашиваемого и текущего отрезков.
2. Если текущий отрезок не пересекается с закрашиваемым отрезком, то закраска предыдущего отрезка закончена, его длина суммируется с длиной уже закрашенной части, а закрашиваемым отрезком становится текущий отрезок.
Процесс продолжается до тех пор, пока не будут просмотрены все отрезки. После этого длина последнего закрашенного отрезка суммируется с длиной ранее закрашенной части.
Решение задачи 10.
Основная идея состоит в неиспользовании операции умножения двух чисел. Легко понять, что если числа натуральные, то одна из пар должна содержать максимальное и минимальное числа. Рассуждая таким образом для оставшихся чисел, приходим к простому алгоритму. Упорядочиваем числа в порядке неубывания. Тогда пары составляют первое и последнее, второе и предпоследнее и т.д. Ситуация немного изменяется, если числа целые. В этом случае возможны три варианта:
1. Произведение равно 0. В этом случае существует хотя бы N нулевых элементов. Поэтому пары будут организованы из одного ненулевого элемента и одного нулевого или из двух нулевых элементов.
2. Произведение положительно. В этом случае перемножаются положительные с положительными, а отрицательные с отрицательными, по правилу как и в случае с натуральными числами.
3. Произведение отрицательно. В этом случае перемножается минимальное положительное число с минимальным отрицательным и т.д.
Для определения ситуаций достаточно подсчитать количество нулевых, положительных и отрицательных элементов.
Если есть нулевые элементы, то возможен только вариант 1. Если количество положительных не равно количеству отрицательных, то возможен только вариант 2. В других случаях возможна ситуация 2 и 3.
Для определения знака произведения рассмотрим четверку чисел: максимальный положительный (пусть a), минимальный положительный (b), минимальный отрицательный(c), максимальный отрицательный (d). Понятно, что решением могут быть только пары (a,b),(c,d) или (a,d),(b,c). Если a не равно -c, то в паре с элементом a должен быть меньший по модулю из элементов c, d, если a>-c и наоборот. В случае, если a=-c и b=-d, эта четверка не дает никакой информации о знаке произведения, поэтому можно перейти к следующей четверке чисел и т.д. пока не будет установлен знак произведения. Если же просмотрены все числа, а знак не установлен, то он может быть как плюс, так и минус.
Решение задачи 11.
Чтобы сумма произведений пар была максимальна (минимальна) необходимо упорядочить наборы A и B одинаковым (различным) образом и пары будут составлять элементы стоящие на одинаковых позициях в упорядоченных наборах. Это следует из того факта, что если а<b и c<d,то а*с+в*d>=a*d+b*c.
Решение задачи 12.
Будем представлять посещение музея посетителем в виде отрезка [время_прихода_посетителя, время_ухода_посетителя]. Надо найти множество точек, принадлежащих максимальному числу отрезков (они и будут составлять тот промежуток (промежутки) времени, в течение которого в музее одновременно находилось максимальное число посетителей.
Рассмотрим какой-нибудь такой промежуток. Его концами, очевидно, являются концевые точки каких-то двух отрезков. В решении задачи 8 (Дихотомия и поиск) в переменной С храниться количество отрезков, пересекающихся в текущей концевой точке. Сначала мы найдем Cmax - максимальную величину переменной C, затем определим, каким промежуткам соответствует максимальное количество посетителей в музее:
{смысл массива A см. в задаче 8 (Дихотомия и поиск)}
{находим Cmax}
i:=1; Cmax:=0;
пока (i<=2*N) и
повторять
если A[2,i]>0
то C:=C+1;
Cmax:=max(Cmax, C);
конец_то
иначе C:=C-1;
конец_иначе
i:=i+1;
конец_пока
если Сmax=0,
то посетителей не было вообще. Стоп.
{ищем и печатаем промежутки с максимальным числом посетителей}
i:=1;
пока (i<=2*N) и
повторять
если A[2,i]>0
то C:=C+1;
если С=Смах {это начало искомого промежутка?}

← →
gn © (2004-04-01 22:59) [3]

то печатаем координату начала промежутка A[1,i] конец_то
конец_то
иначе
если С=Смах {промежуток закончился}
то печатаем координату конца промежутка A[1,i]
конец_то
C:=C-1;
конец_иначе
i:=i+1;
конец_пока
Решение задачи 13.
Предположим, что среди пяти чисел нет одинаковых (случай совпадающих чисел рассматривается аналогично). В дальнейшем будем обозначать операцию сравнения значком ":". Например, 5:3 означает, что мы сравниваем пятое и третье числа. Запись 5<3 означает, что пятое число меньше третьего.
Сначала выполним следующие операции 1:2,3:4. При необходимости перенумеровывая числа, получаем, что 1<2, 3<4. Далее делаем 1:3. Опять же при необходимости перенумеровывая числа, получаем 1<3.
Выполняем 3:5. Случаи:
a) 3>5. Подводя итог четырех проделанных операций сравнения имеем:
1<2
1<3<4
5<3
б) 3<5.
Сравниваем 4 и 5.
Пусть 4<5. Тогда
1<2
1<3<4<5.
Выполняем 2:4. В зависимости от результата делаем либо 2:3, либо 2:5.
Оставшиеся варианты рассматриваем аналогично.
Решение задачи 14.
Зафиксируем какой-нибудь порядок перечисления ребер параллелепипеда.
Очевидно, что параллелепипеды можно повернуть так, чтобы размеры ребер параллелепипеда шли в неубывающем порядке. Опять же понятно, что параллелепипед с большим объемом нельзя вложить в параллелепипед с меньшим объемом, вложение параллелепипеда B в C возможно только тогда, когда для двух параллелепипедов B(b(1), ..., b(n)) и C(c(1), ..., c(n)) выполняются неравенства b(k)<=c(k), k=1, ..., n. Запишем это так:
(b(1), ..., b(n))<=(c(1), ..., c(n)).
Алгоритм:
1. Сортируем размеры граней каждого параллелепипеда в неубывающем порядке.
2. Сортируем последовательность параллелепипедов по неубыванию объема.
3. Применяем алгоритм задачи 20 (Глава "Рекуррентные соотношения и динамическое программирование") для поиска максимальной по длине возрастающей подпоследовательности.
Решение задачи 15.
Без потери общности предположим, что элементы массива A упорядочены в возрастающем порядке (в множестве нет дублирующихся элементов, поэтому массив A упорядочен именно в возрастающем, а не только в неубывающем порядке). Если это не так, то добавляем в программу подпpогpамму сортировки.
Если свойство (*) выполняется для подмножества B, то оно выполняется и для трех наибольших по величине элементов B. Обратно, из выполнимости (*) для трех максимальных элементов B следует выполнимость (*) и для B. Мы будем включать в B в порядке их возрастания элементы из A и проверять для трех максимальных выполнение (*).
Программа на Pascal будет выглядеть следующим образом:
const m=20; {максимальный размер массива A}
var A:array[1..m] of word; {описание массива A}
n,s,s3,k,:word;
{s -- сумма от 1-ого до i-ого элементов массива A
s3 - сумма a(i+1)+a(i+2)+a(i+3)
n - размерность массива A
k - индекс такого элемента массива A, что для a(1), ... ,a(k)
выполняется свойство (*)}
begin
readln(n);
for i:=1 to n do readln(a[i]);
k:=0;
for i:=1 to n-3 do
begin
s:=s+a[i];
s3:=a[i+1]+a[i+2]+a[i+3];
if s3<=s then k:=i+3;
end;
if k=0 then writeln("Решения нет")
else for i:=1 to k do write(a[i]);
end.
Решение задачи 16.
а) Пусть в переменной MaxEndingHere хранится сумма элементов максимального подвектора, заканчивающегося в позиции i-1. Для того, чтобы MaxEdingHere начала хранить сумму элементов максимального подвектора, оканчивающегося в позиции i, необходимо выполнить следующую операцию присваивания:
MaxEndingHere:=max(MaxEndingHere+A[i],A[i]);
а для того, чтобы найти максимальную сумму MaxSoFar элементов подвектора, встретившегося до позиции i, надо выполнить операцию
MaxSoFar:=Max(MaxSoFar, MaxEndingHere).
Программа:
MaxSoFar:=A[1];
MaxEndingHere:=A[1];
for i:=2 to K do begin
MaxEndingHere:=max(MaxEndingHere+A[i],A[i]);
MaxSoFar:=max(MaxSoFar, MaxEndingHere);
end.
b) Для поиска минимальной суммы мы можем сначала умножить все элементы массива A на -1, а затем искать, как и в пункте а, максимальную сумму.
c) Заведем массив C[0..k] такой, что C[i]=A[1]+ ... +A[i], C[0]=0. Заметим, что
S(M,N)=C[N]-C[M-1].
Сумма S(M,N) элементов вектора A[M]+ ... +A[N] равна нулю, если C[M-1]=C[N]. Исходя из этого соображения возьмем массив C, отсортируем его, затем найдем минимальную по модулю разность двух соседних элементов отсортированного массива (т.е. найдем два наименее отличающихся элемента массива C). Эта разность как раз и

будет наиболее близким к нулю значением суммы S(M,N).
d) Как и в предыдущем пункте сформируем массив C, затем его отсортируем. Нам надо найти в этом массиве два элемента C[i] и C[j], значение разности которых наиболее близко к P. Пусть массив C упорядочен по неубыванию, и i и j - индексы текущих просматриваемых элементов массива C.
i:=1; j:=1;
MinSoFar:=abs(C[2]-C[1]-P); {Текущее значение минимальной разности}
while (i<=k) and (j<=k) do begin
if C[j]-C[i]>P
then i:=i+1; {увеличиваем вычитаемое}
else j:=j+1; {увеличиваем уменьшаемое}
if i<>j {если это не один и тот же элемент массива C}
then MinSoFar:=min(MinSoFar, abs(C[j]-C[i]-P));
end;
Решение задачи 17.
Заметим, что если мы знаем сумму S[i]=X[i]+ ... +X[i+M], то мы можем вычислить S[i+1] по следующей очевидной формуле
S[i+1]=S[i]+X[i+M+1]-X[i],
и нет необходимости во вложенном цикле для вычисления S[i+1].
Решение задачи 18.
Можно в массив C записать сначала элементы массива A, затем массива B, затем применить любой алгоритм сортировки. Но в этом случае мы не используем того, что A и B уже отсортированы. Будем просматривать элементы массивов A и B начиная с A[1] и B[1]. Если, например, A[1]>B[1], то C[1]:=B[1], и на следующем шаге сравниваем уже A[1] и B[2], занося меньший элемент пары в ячейку C[2] и т.д.
Запись алгоритма на языке Паскаль:
{Ввод массивов A и B}
Ai:=1; Bi:=1; Ci:=1; {текущие индексы в массивах A,B,C}
while Ci<=N+M do begin
if A[Ai]>B[Bi]
then begin
C[Ci]:=B[Bi];
Bi:=Bi+1
end
else begin
C[Ci]:=A[Ai]; Ai:=Ai+1;
end
Ci:=Ci+1;
{Проверка окончания одного из массивов}
if Ai>N then for i:=Bi to M do
begin
C[Ci]:=B[Bi];
Bi:=Bi+1;
Ci:=Ci+1;
end;
if Bi>N then for i:=Ai to N do
begin
C[Ci]:=A[Ai];
Ai:=Ai+1;
Ci:=Ci+1;
end;
end; {while}
Решение задачи 19.
Пусть A - это k первых элементов массива X, а B - последних N-K. Нам необходимо из вектора AB получить вектор BA. Пусть у нас есть подпрограмма REVERRSE(I,j), которая реверсирует (меняет порядок элементов на обратный) часть массива x с индексами от i до j. Начав с массива AB реверсируем часть A, получаем (Ar)B; реверсируrем B, получаем (Ar)(Br); реверсируем весь массив, получаем((Ar)(Br))r =BA.
Продемонстрируем описанный алгоритм на примере. Пусть X есть последовательность 1,2,3,4,5, k=3:
REVERSE(1,K); {3,2,1,4,5}
REVERSE(K+1,N); {3,2,1,5,4}
REVERSE(1,K); {4,5,1,2,3}
Решение задачи 20.
Пусть числа a[1], ..., a[n] расположены в порядке неубывания (если это не так, то просто отсортируем массив). Будем выписывать искомые векторы v[1], ..., следующим образом:
Пусть k - номер формируемого сейчас вектора.
Положим сначала индекс i первого элемента формируемого сейчас вектора v[k] равным 1, а индекс второго элемента j=N.
k:=0;
пока (i<j) повторять {пока есть возможные элементы для пар}
k:=k+1;
v[k]:=(a[i],a[j]);
полагаем i:=i+1; j:=j-1; {переходим к следующим элементам}
если v[k]=(a[i],a[j])
то пусть количество оставшихся в массиве A элементов справа
от а[i-1], равных a[i-1], есть u, т.е. a[i]=a[i+1]=...=a[i+u],
а количество оставшихся в массиве A элементов слева от а[j+1],
равных a[j+1], есть v, т.е.
a[j]=a[j-1]=...=a[j-v].
если u>=v
то, так как мы стремимся получить максимальное число пар,
то мы отбросим все оставшиеся элементы со значением a[j]
и положим j:=j-v-1
иначе по аналогичной причине отбросим все оставшиеся элементы
со значением a[i], т.е. положим i:=i+u+1;
gn
cn 1101

Запарился читать... конечно, это как бы неуважение к автору, прошу извинить, а короче нельзя? И для чего всё это?

для тех кто в ещё может! :-) Найти похожие ветки