                         СТРУКТУРЫ ДАННЫХ.

                            Задача 1.
     Пусть при  записи  этих  N  пар встретилось всего K различных
символов, которые образуют множество X.
     Идея решения  задачи  состоит  в  последовательном присвоении
каждому символу s из Х номера,  который определяет количество Р(s)
элементов,  предшествующих  ему,  с учетом свойства транзитивности
(из (с,b) и (b,а) следует (с,а)). Это осуществляется следующим об-
разом:
     Первоначально предполагается,  что каждому символу  не  пред-
шествует ни один символ, т.е. Р(s)=0 для любого s.
     При просмотре очередной пары (x,y)  символу  y  присваивается
большее из значений P(x)+1, P(y).
     Очевидно, что при первом просмотре всех пар из входной после-
довательности определятся все упорядоченные цепочки длины 2,  т.е.
состоящие из 2 элементов. Поэтому номера некоторых элементов будут
как  минимум 1.  При каждом из следующих просмотров входной строки
возможно несколько вариантов.
     1. Не произошло изменения ни одного из номеров символов. Если
   при этом номера символов различны и лежат в пределах  от  0  до
   N-1,  то эта нумерация определяет полный порядок. Иначе порядок
   неполный.
     2. Номер некоторого символа превысил N-1. Это произошло пото-
   му,  что рост номеров неограничен,  т.е.  осуществляется цикли-
   чески. Следовательно порядок противоречив.
     Легко понять, что число просмотров не превысит N.

     Вариант 2. Рассмотрим следующий метод:
     Заведем массивы
                    A: array [1..N,0..N] of byte
и
                     Cnt: array[1..N] of byte;
сначала A[i,0]=0 и Cnt[i]=0 для любого i.
     Пусть среди 2*N символов,  образующих N пар,  есть ровно K раз-
личных. Перенумеруем их от 1 до K. Будем считать, что пары составле-
ны не из символов, а из соответствующих им номеров.
     В i-ю строчку матрицы A будем заносить те элементы, которые яв-
ляются вторыми элементами в парах с первым элементом i. В A[i,0] бу-
дет храниться текущее число этих элементов. Обработка пары (i,j) бу-
дет выглядеть следующим образом:
     A[i,0]:=A[i,0]+1;  { количество увеличилось на 1 }
     A[i,A[i,0]]:=j;      { вставляем j на первое свободное место }
     В Сnt[i]  будет храниться число пар,  у которых элемент i явля-
ется вторым в паре.
     Если все символы без повторений, использованные для записи пар,
можно выписать в цепочку в порядке предшествования, то у этой цепоч-
ки должен быть первый символ s, у которого нет предшествующего и кото-
рому соответствует Cnt[s]=0.
     Может быть несколько ситуаций:
     1. Такой элемент единственный -- следовательно,  это начало це-
почки. Отбрасываем s из цепочки и убираем все пары с первым элемен-
том s из множества пар, корректируя при этом массив Cnt:
     for i:=1 to A[0,s] do
       Сnt[A[s,i]]:=Cnt[A[s,i]]-1;
     после чего опять ищем элемент s, у которого нет предшествующего
и которому соответствует Cnt[s]=0.
     2. Таких элементов несколько,  следовательно, между ними нельзя
определить порядок предшествования -- система неполна.
     3. Таких элементов нет -- следовательно, система противоречива.

                             Задача 2.
     Для решения этой задачи используем  структуру  данных  'список'.
Каждый элемент списка указывает на следующий за ним элемент (другими
словами -- хранит информацию о расположении следующего элемента).
    a). Заведем массив A из N ячеек - по числу людей в круге. В каж-
дую из ячеек A[i] занесем номер стоящего следующим за i-ым человека.
Первоначально A[i]=i+1,  i=1,...,.N-1, A[N]=1. Начиная счет от теку-
щего человека (человека с номером IndTek, с самого сначала IndTek=1)
будем делать ход - отсчитывать M ячеек,  двигаясь по кругу в поисках
человека, который должен выйти из круга. С учетом определения масси-
ва A это будет выглядеть следующим образом:
    { IndTek -- это номер человека, с которого начинается счет }
     for i:=1 to M-1 do  { Отсчитываем M человек, начиная с IndTek }
       begin
         IndPred:=IndTek;   { в IndPred сохраняем номер текущего
                              человека в круге }
         IndTek:=A[IndTek]; { и вычисляем номер следующего за ним }
       end;
     После выполнения этого цикла в переменной  IndTek  будет  номер
человека, на котором остановился счет (т.е.  номер человека, который
покинул круг),  а в переменной IndPred -- номер предшествующего  ему
человека в круге.
     Удалим человека с номером IndTek.  Для этого мы просто  изменим
ссылку A[IndPred] у предшествующего ему человека так,  чтобы он ука-
зывал не на IndTek,  а на следующего за IndTek, т.е. на A[IndTek], и
новый отсчет M-того человека начнем со следующего за удаленным:
     A[IndPred]:=A[IndTek];
     IndTek:=A[IndTek];     { Новый номер начального человека }
     Все вышеописанные операции мы будем повторять до тех пор,  пока
в круге не останется одного единственного человека, т.е. до тех пор,
пока A[IndTek] не станет равным IndTek,  что означает, что следующим
за человеком с номером IndTek является он сам.
     Полностью весь фрагмент программы будет выглядеть так:
  { Инициализация массива A }
  for i:=1 to N-1 do
    A[i]:=i+1;
  A[N]:=1;
  { IndTek -- это номер человека, с которого начинается счет }
  IndTek:=1;
  while  A[IndTek] <> IndTek do
    begin
     for i:=1 to M-1 do  { Отсчитываем M человек, начиная с IndTek }
       begin
         IndPred:=IndTek;   { в IndPred сохраняем номер текущего
                              человека в круге }
         IndTek:=A[IndTek]; { и вычисляем номер следующего за ним }
       end;
     A[IndPred]:=A[IndTek];
     IndTek:=A[IndTek];     { Новый номер начального человека }
    end;
  writeln('Номер последнего оставшегося человека ',IndTek);

     Решения пункта b).
     Будем считать,  что человек с номером N+i -- это то  же  самое,
что и человек с номером i.
     Предположим, что как и в пункте a), что мы начали счет с перво-
го человека,  выбрасывали из круга M-того,  и последний оставшийся в
круге человек имеет номер K. Очевидно, что если бы мы начали счет со
второго человека,  то  последний  оставшийся в круге человек имел бы
номер K+1, ..., если с j-го, то K+j-1.
     Если номер оставшегося человека L,  то из равенства L=K+j-1 оп-
ределяем номер j первого человека (если j<=0,  то заменим j на  j+N,
считая  как и раньше,  что человек с номером N+j -- это то же самое,
что и человек с номером j).

                            Задача 3.
     Будем моделировать сложение полоски,  затем пронумеруем полу-
чившуюся колонку клеток числами от 1 до 2^n, после чего распечата-
ем числа,  приписанные первой, второй, ..., 2^n-ой клетке исходной
полоски.
     Сначала создаем двусвязный список,  состоящий из 2^k  элемен-
тов.  Поле next будет указывать на элемент находящийся под данным,
а поле last - на элемент находящийся над данным. Для верхнего эле-
мента last=0, а для нижнего next=n+1, где n-общее число элементов.
Вначале длина верхней полоски равняется n элементов, после первого
сгибания их она станет n/2,  после второго -- n/4,  и т.д. Пусть в
данный момент длина верхней полоски есть cn элементов.  Значит нам
необходимо cn/2 правых элементов опустить под cn/2 левых. Для это-
го запустим цикл,  который будет менять i от 1 до cn/2 и на каждом
шаге помещать (cn-i+1)-ю колонку элементов под i-ю, при этом поря-
док элементов в (cn-i+1)-ой колонке меняется  на  противоположный.
После каждого сгибания cn уменьшается вдвое. Так продолжаем до тех
пор пока cn>1.

     Программа (программы для задач 3 и 4 написаны В.Белым):

{$A-,B-,D-,E+,F-,I-,L-,N-,O-,R-,S-,V-}
{$M 65520,0,655360}

uses crt;
const
   maxk = 13; { Максимальное значение для k }
type
   input = record
              last,next,new : word;
           end;
var
   k,i,j,n,cn,half : word;
   m : array[1..1 shl maxk] of input;

Procedure concat(a,b : word);
var i,j,nj : word;
begin
   i:=a; while m[i].next<>n+1 do i:=m[i].next;
   j:=b; while m[j].next<>n+1 do j:=m[j].next;
   while j<>0 do
     begin
        nj:=m[j].last; m[i].next:=j; m[j].last:=i; i:=j; j:=nj;
     end;
   m[i].next:=n+1;
end;

begin
   Write('Enter k...');readln(k);
   n:=1 shl k; { Определение длины полоски }
   for i:=1 to n do{ Начальные значения }
    with m[i] do
     begin
        last:=0;
        next:=n+1;
        new:=0;
     end;
   cn:=n;
   while cn>1 do { Сгибание полоски }
     begin
        half:=cn div 2;
        for i:=1 to half do concat(i,cn-i+1);
        cn:=half;
     end;
   j:=1;
   for i:=1 to n do { Нумерация клеток }
     begin
        m[j].new:=i; j:=m[j].next;
     end;
   for i:=1 to n do write(m[i].new:5);
   writeln;
end.

     Попробуйте найти формулу и написать  программу,  которая  без
моделирования  складывания полоски по номеру клетки выдавала бы ее
номер.

                            Задача 4.
     Решение этой задачи аналогично решению предыдущей  задачи  со
сгибанием  полоски  с той лишь разницей,  что тут будет поочередно
производится два сгибания:  сначала правая половина под  левую,  а
затем нижнюю под верхнюю

{$A-,B-,D-,E+,F-,G-,I+,L-,N-,O-,R-,S-,V-,X-}
{$M 16384,0,655360}

uses crt;
const
   maxk = 6;
type
   input = record
              last1,last2,next1,next2,new : word;
           end;
var
   k,i,j,i1,i2,j1,j2,nj1,nj2,n,n1,cn,half : word;
   m : array[1..1 shl maxk,1..1 shl maxk] of input;

Procedure concat(a,b,c,d : word);
var i1,i2,j1,j2,nj1,nj2 : word;
begin
   i1:=a; i2:=b;
     while (m[i1,i2].next1<>n+1) and (m[i1,i2].next2<>n+1) do
       begin
          i1:=m[i1,i2].next1; i2:=m[i1,i2].next2;
       end;
   j1:=c; j2:=d;
     while (m[j1,j2].next1<>n+1) and (m[j1,j2].next2<>n+1) do
       begin
          j1:=m[j1,j2].next1; j2:=m[j1,j2].next2;
       end;
   while j1<>0 do
     begin
        nj2:=m[j1,j2].last2; nj1:=m[j1,j2].last1;
        m[i1,i2].next1:=j1; m[i1,i2].next2:=j2;
        m[j1,j2].last1:=i1; m[j1,j2].last2:=i2;
        i1:=j1; i2:=j2; j1:=nj1; j2:=nj2;
     end;
   m[i1,i2].next1:=n+1; m[i1,i2].next2:=n+1;
end;

begin
   Write('Введите k...');readln(k);
   n:=1 shl k; { Определение числа клеток в одной строке или столбце }
   n1:=n*n;    { Определение числа клеток в матрице                  }
   for i:=1 to n do
    for j:=1 to n do
    with m[i,j] do
     begin
        last1:=0; next1:=n+1;
        last2:=0; next2:=n+1;
        new:=0;
     end;
   cn:=n;
   while cn>1 do { сгибание матрицы }
     begin
        half:=cn div 2;
        for i:=1 to half do { сгиб по вертикали }
          for j:=1 to cn do concat(j,i,j,cn-i+1);
        for i:=1 to half do { сгиб по горизонтали }
          for j:=1 to half do concat(i,j,cn-i+1,j);
        cn:=half;
     end;
   j1:=1;j2:=1;
   for i:=1 to n1 do { Назначение клеткам новые номера }
     begin
        m[j1,j2].new:=i;
        nj1:=m[j1,j2].next1; nj2:=m[j1,j2].next2;
        j1:=nj1; j2:=nj2;
     end;
   for i:=1 to n do { Вывод результатов }
     begin
       for j:=1 to n do write(m[i,j].new:8);
       writeln;
     end;
end.

                            Задача 5.
     Идея решения основывается на использовании очереди. Вначале в
очередь помещается элемент,  определяющий исходное положение  шах-
матного  коня,  а соответствующая клетка поля помечается как посе-
щенная.
     На каждом из следующих шагов алгоритма (пока очередь не пуста
или не помечена конечная клетка) выполняются следующие действия.
  1. Из очереди извлекается очередной элемент,  который определяет
     некоторую позицию (x,y).
  2. Находятся клетки в пределах поля,  которые достижимы из (x,y)
     одним ходом шахматного коня, и которые еще не помечены.
  3. Элементы,  соответствующие  найденным  клеткам,  помещаются в
     очередь, а клетки помечаются как посещенные.
    При этом  вначале  все клетки должны быть непомечены,  а метку
желательно ставить такую, чтобы можно было восстановить путь между
полями.
    Для этого метку поля можно определить как позицию поля, из ко-
торой она была помечена.

                            Задача 6.
     Идея решения основывается на  использовании  стека.  Считывая
входную последовательность скобка за скобкой,  выполняются следую-
щие действия.
   1. Если очередная скобка - открывающая, то помещаем ее в стек.
   2. Если очередная скобка - закрывающая,  то анализируем скобку,
      стоящую в вершине стека. Возможно несколько ситуаций:
     а) открывающая скобка соответствует очередной  закрывающей.  В
      этом  случае  она выталкивается из стека,  а процесс с новой
      входной скобкой.
     б) открывающая  скобка не соответствует очередной закрывающей
      или стек пуст.  В этом случае невозможно получить правильное
      арифметическое выражение.
   Когда все скобки входной строки обработаны, возможны 2 ситуации.
    1. Стек пуст.  В этом случае можно получить правильное арифме-
       тическое выражение.
    2. Стек не пуст.  В этом случае невозможно получить правильное
       арифметическое выражение.

                            Задача 7.
     Необходимо организовать  стек  для  позиций элементов,которые
претендуют быть большими.  Для каждого текущего элемента  выталки-
вать из стека все позиции,  на которых стоят элементы меньше теку-
щего и заменить их текущим.  Затем позицию текущего  элемента  по-
местить в стек.После просмотра всех элементов в стеке будут стоять
позиции элементов,которые надо заменить на ноль.

                             Задача 8.
     Идея решения  основывается  на использовании очередей.  Но если
реализация движения от остановки к остановке по одному маршруту ана-
логична технике,  используемой в задаче 6,  то возможность изменения
маршрутов несколько усложняет структуру элемента в очереди.
     Для этого  для  каждой  остановки введем тройку чисел (О,М,За),
где О - номер остановки, М - номер маршрута, За - величина задержки.
При выборе очередного элемента из очереди возможны 2 ситуации.
   1. Продолжается движение по тому же маршруту.  В  этом  случае  в
      очередь заносятся тройки типа (О',М,За),  где О' - номер оста-
      новки, соседней О, в маршруте М, а За=0.
   2. Изменяется  маршрут.  В этом случае в очередь заносятся тройки
      типа (О,М',За), где М' - номер измененного маршрута, За=3 (за-
      держка на пересадку).
     При этом новые тройки порождаются только тройками с  задержкой,
равной 0. В случае тройки с ненулевой задержкой она вновь помещается
в очередь с уменьшенным на 1 значением задержки.

                            Задача 9.
     Будем хранить  в  массиве A[1..N,1..2] координаты тех клеток,
где король уже был.  Возьмем N достаточно большим, N=500. A[i,1] -
иксовая,  A[i,2] - игрековая координата клетки. Пусть в переменной
DLN хранится количество уже сделанных  ходов  (т.о.  в  массиве  A
после хода номер i будут заняты клетки с первой по i-ую).
     Результаты очередного  хода  заносим в массив A на первое
свободное место (т.е.  на место с индексом DLN+1), увеличиваем
количество сделанных ходов DLN:=DLN+1,  и проверяем, совпадает
ли хоть одна из позиций,  на которых король уже был, с текущей
позицией:
     for i:=1 to DLN-1 do
       if (A[i,1]=A[DLN,1]) and
          (A[i,2]=A[DLN,2])       { проверка совпадения }
     then begin
            writeln('совпадение на ходах ',DLN,' и ',i);
            halt;                 { останов }
          end;
     Давайте посмотрим,  как можно вводить ходы короля.  Он из
клетки k может пойти на 8 соседних позиций.
     1  2  3     Будем вводить направление перемещения короля
     8  К  4     цифрой от 1 до 8.
     7  6  5
     Заведем массив XOD=array[1..8,1..2]=((-1,1),(0,1),(1,1),
(1,0),(1,-1),(0,-1),(-1,-1),(-1,0));
     В массив заносятся смещения по x- и y-координатам,  соот-
ветствующие направлениям от 1 до 8.  Координаты короля после  сде-
ланного хода вычисляются по формулам
             x:=x+XOD[i,1];           y:=y+XOD[i,2];

                            Задача 10.
     Монеты лежат на N+M позициях.  Пронумеруем эти позиции по по-
рядку по контуру от 1 до N+M.
     Заведем массив A из N+M ячеек. Первоначально все ячейки нуле-
вые. Начиная счет от первой ячейки, будем делать ход - отсчитывать
S ячеек (считаем,  что за N+M-ым элементом следует непосредственно
1-ый элемент массива) и заменять в этой ячейке число  i  на  число
1-i (т.е. 0 на 1, а 1 на 0). После k-того хода остановимся.
     Рассмотрим возникшую ситуацию. После каждого хода переворачи-
вается  одна монета,  при этом разность количества монет,  лежащих
гербами вверх и количества монет, лежащих гербами вниз либо увели-
чивается,  либо уменьшается на 2.  Например, если переворачивается
монета, лежащая гербом вверх, то при этом увеличивается на 1 коли-
чество  монет гербом вниз и уменьшается на 1 количество монет гер-
бом вверх.
     Предположим, что  после  k ходов в массиве A стало p единиц -
т.е.  p монет, по сравнению с начальным положением, будут перевер-
нуты после k-ого хода.
     В случае,  если L>=N,  то (L-N) монет, которые лежали гербами
вниз, должны после k-ого хода быть перевернуты гербами вверх. (Ес-
ли p<(L-N), то это, очевидно, невозможно сделать). Среди оставших-
ся p-(L-N) перевернутых монет должна быть половина гербами вверх и
половина - вниз, чтобы при перевороте суммарное число монет герба-
ми вверх и вниз не изменилось. Следовательно, число p-(L-N) должно
быть четным,  иначе условию  задачи  удовлетворить  нельзя.  Пусть
p-(L-N) = 2v. Должно быть, очевидно, v<=N, v+(L-N)<=M.
     Итак, в случае L>=N,  если не выполняется хотя бы одно из не-
равенств
       p-(L-N)=2v>=0,
       v<=N,
       v+(L-N)<=M,
то преобразование начальной конфигурации в конечную невозможно.
     Иначе на (L-N) мест,  помеченных в массиве A единицами,  выс-
тавляем  монеты гербами вниз.  На оставшиеся 2v=p-(L-N) помеченных
единицами позиций кладем v монет гербами вниз и v гербами вверх  в
произвольном порядке. На остальные позиции кладем оставшиеся моне-
ты опять же в произвольном порядке, чтобы в общей сложности было N
монет гербами вверх и M - гербами вниз.
     Но мы еще не учли тот факт,  что счет начинается с первой мо-
неты гербом вверх:
     а) Если в массиве A первый элемент нулевой, то в случае, если
среди  (N+M)-p монет есть хоть одна гербом вверх (что эквивалентно
выполнению условия N-v>0),  то ее и кладем в первую позицию.  Если
все (N+M)-p монеты - гербом вниз (т.е. N-v=0), то размещение монет
невозможно.
     б) Если  же  A[1]=1,  то среди p монет должна быть по крайней
мере одна,  которую необходимо положить гербом вверх, иначе, опять
же, размещение невозможно.
     Случай N-L>0 разбирается аналогично.

                            Задача 11.
     Как и в задаче 10 заполняем сначала массив A нулями, перену-
меровываем по  порядку  N+M позиций от 1 до N+M.  Начиная с первой
позиции (серая мышка) делаем ход - отсчитываем S  нулевых  позиций
по порядку (считаем,  что позиция, где сидела съеденная мышка, по-
мечается единицей,  несъеденная мышка - нулем;  за N+M-ой позицией
располагается  первая)  и выставляем в соответствующую позицию 1 -
мышка съедена. Далее отсчет начинаем со следующей за съеденной мы-
ши. (Для более быстрого поиска S-той мышки среди оставшихся в кру-
ге можно использовать список, описанный в задаче 2).
     Делаем P=(N+M)-(K+L) ходов.
     По условию  задачи  в первой позиции сидит серая мышка.  Есть
A[1]=1 (первая мышь была съедена),  то в оставшихся P-1  единичной
позиции в произвольном порядке расставляем N-K-1 серых и M-L белых
мышей.  В оставшихся незанятыми позициях рассаживаем  опять  же  в
произвольном порядке оставшихся мышей.
     Если A[1]=0,  и K=0,  то начальной расстановки не  существует
(все серые мыши съедены, а должна остаться еще одна в первой пози-
ции);  если же K<>0, то в единичных позициях рассаживаем N-K серых
и  M-L  белых мышей,  а в оставшихся позициях - в первую позицию -
серую мышь,  а во все остальные - белых и серых в произвольном по-
рядке.

                             Задача 12.
     Идея решения  состоит  в последовательном определении множества
клеток,  принадлежащих тому же куску,  что и некоторая фиксированная
клетка.
     Начиная с некоторой непомеченной  клетки  (начальной),  которая
помечается,  помечаются все клетки, имеющие с ней общую сторону. За-
тем, используя вновь помеченные клетки, помечается множество клеток,
имеющих  с ними общую сторону и т.д.,  пока на некоторой итерации не
будет помечено ни одной новой клетки.  Множество клеток,  помеченных
таким образом,  и составляет единый кусок листа максимального разме-
ра.
     Для подсчета общего количества кусков необходимо подсчитать ко-
личество клеток,  выбранных в качестве  начальных.  Новая  начальная
клетка  выбирается из множества клеток,  не помеченных на предыдущих
итерациях.  Для хранения вновь помеченных клеток можно  использовать
очередь или стек, а пометку клеток можно проводить в матрице размера
N*M.

                            Задача 13.
     Проще всего взять и промоделировать раскладку карточек: берем
стопку  из  n черных и белых карточек и начинаем расклад как гово-
рится в задаче - первая на стол, вторая под низ, третья на стол, и
т.д. при этом первой выложенной карточке приписывается белый цвет,
а каждой последующей - цвет,  не совпадающий с  цветом  предыдущей
карточки. Повторяет так, пока не найдем раскраску всех n карточек.
     Для этой задачи возьмем такую структуру данных как список.  У
списка есть начало и конец, и каждый элемент его указывает на сле-
дующий за ним элемент.  Будем считать ,  что у последнего элемента
списка  указатель  на  следующий  за  ним  равен  0.  Список можно
представлять массивом.  Например,  если в списке  4  элемента,  то
массив будет выглядеть так:
                       1   2   3   4
                     ┌───┬───┬───┬───┐
                  A  │ 2 │ 3 │ 4 │ 0 │
                     └───┴───┴───┴───┘
     т.е. за первым элементом находится A[1]=2  элемент,  ...,  за
4-ым - A[4]=0 (т.к. 4-ый элемент списка последний).
     Пусть у нас есть указатель на начальный элемент списка  и  на
последний (BEG и FIN соответственно). В списке n элементов.
     Рассмотрим процедуру удаления элемента из начала списка  (это
соответствует переносу карточки на стол):
     BEG:=A[BEG]; {теперь новый первый  элемент  списка  -  второй
элемент старого списка}
     Рассмотрим операторы перестановки элемента из начала списка в
конец  (это  соответствует  перемещению карточки сверху стопки под
низ ее):
     A[FIN]:=BEG; {следующей за последним элементом
                     - бывший первый}
     FIN:=BEG;    {меняем ссылку на последний элемент}
     BEG:=A[BEG]  {новый первый элемент}
     A[FIN]:=0    {корректировка ссылки у последнего элемента}
     Фрагмент программы будет выглядеть так:
       for i:=1 to N-1 do A[i]:=i+1;
         A[N]:=0;    {установка ссылок в списке}
       BEG:=1;   FIN:=N;
       COLOR:=1;     {белый цвет = 1, черный = 0}
       while A[BEG]<>0 do {пока первый элемент не является}
                          {одновременно и последним}
       begin
            BEFORE:=BEG;  {сохраняем индекс начала списка}
            BEG:=A[BEG];  {удаляем первый элемент из списка}
            A[BEFORE]:=COLOR; {раскрашиваем удаленный элемент}
                              {в нужный цвет}
            COLOR:=1-COLOR;    {меняем цвет}
            A[FIN]:=BEG;       {переставляем элемент из}
            FIN:=BEG;          {начала списка в конец}
            BEG:=A[BEG];
            A[FIN]:=0
       end;
       A[BEG]:=COLOR;        {раскрашиваем последний элемент}
                              {списка}
       for i:=1 to N do        {распечатка цветов}
         if A[i]=0
         then writeln('элемент',i,' - черный')
         else writeln('элемент',i,' - белый');

                            Задача 14.
     Для реализации данного алгоритма  нам  понадобится  структура
данных "очередь".  Очередь в программировании, как и очередь в ма-
газине,  имеет начало и конец.  Если приходит новый элемент, то он
становится в конец очереди,  если необходимо взять элемент из оче-
реди, то он берется из ее начала. Очередь будем представлять в ви-
де массива.  Пусть  у нас есть индекс первого - BEG и последнего -
FIN элементов очереди (если очередь пуста,  то BEG=FIN+1;  сначала
же BEG=1, FIN=0).
     Очередь опишем так: var Queue=array[1..MaxQ] of element;
     Тут MaxQ - максимальное число элементов в очереди,  element -
какой-то тип данных.  В задаче ниже в качестве element можно взять
такой
        type element = record
                x: byte;
                y: byte;
             end;
     где element - это запись,  состоящая из x-овой и y-овой коор-
динаты элемента матрицы A=array[0..M+1,0..N+1] of integer. Индексы
матрицы принимают такое значение из-за того,  что мы будем  окайм-
лять  матрицу нулевыми элементами (так будет проще проверять выли-
вание за край фигуры).
     С очередью можно проводить операции:
           вставка  в  очередь InQueue,
           удаление из очереди OutQueue.

     Procedure InQueue (x : element);
     begin
       FIN:=FIN+1;      { на первое свободное место}
       Queue[FIN]:=x;   { ставим элемент x }
     end;

     Procedure OutQueue (var x : element);
     begin
       x:=Queue[BEG];   { берем первый элемент }
       BEG:=BEG+1;      { и изменяем указатель }
                        { на следующий за ним }
     end;

     Находим максимальный элемент D в матрице A. Пока все элементы
в матрице A не станут равны D,  повторяем следующую последователь-
ность действий:
     а) Находим в матрице минимальный ненулевой элемент z (если их
несколько,  то берем любой из них),  и заносим его в очередь (оче-
редь сначала пустая). Если этот минимальный ненулевой элемент z=D,
то СТОП.
     Сначала считаем,  что p=D - это минимальный граничный элемент
области, заполненной элементами со значением z.
     б) Для  каждого еще не просмотренного элемента очереди (пусть
в матрице этот элемент находится в позиции (i,j)) повторяем следу-
ющее:
     Для каждого соседа (сверху, снизу, справа, слева) данного
элемента (i,j) проводим проверку-просмотр:
     ЕСЛИ (сосед <> z)
     ТО P=min{P,сосед}
     ИНАЧЕ ЕСЛИ сосед еще не просмотрен
           ТО   координата соседа - в очередь (в очереди появился
                еще один непросмотренный элемент)
т.е. мы ищем минимальный окаймляющий элемент области,  заполненной
элементами со значением z.
     Фрагмент программы поиска:
 var Delta = array [1..4,1..2] of integer =
             ((0,1),(1,0),(-1,0),(0,-1));
{ Delta -  возможные смещения соседних клеток от текущей клетки }
     Current, neighbor : element;
     z      : integer;
                               ....
   { Будем обозначать то, что элемент в матрице уже просмотрен }
   {                  умножением его на -1                     }
   {   минимальный ненулевой элемент матрицы имеет значение z  }

   while BEG<>FIN+1 do begin
     OutQueue(Current);
     for i:=1 to 4 do begin
       neighbor.x:=Current.x+Delta[i,1],
       neighbor.y:=Current.y+Delta[i,2],
       if A[neighbor.x,neighbor.y]=z
       then InQueue(neighbor)
       else p:=min(A[neighbor.x,neighbor.y],p);
     end;
   end;

     Если в очереди нет больше непросмотренных элементов, то, если
p<z (случай, когда данная область имеет "слив" за границы матрицы)
в матрице во все просмотренные элементы из очереди заносим  значе-
ние D (делаем их равными накопленному значению, чтобы больше их не
рассматривать).
     Если же  p>z,  то  высчитываем,  сколько  воды  поместится  в
"бассейн" с глубиной дна z и с высотой ограждающего бордюра p:
   Объем = (p-z)* количество просмотренных элементов в очереди.
     Добавляем полученный объем к ранее  найденному  объему  воды,
заполняющему матрицу до высоты x.
     Заполняем в матрице элементы,  соответствующие  просмотренным
элементам из очереди,  значением p ("Доливаем" воды в "бассейн" до
уровня p).
     Переход на пункт а).
     Суммарный полученный объем воды и является искомым.
     Окаймление матрицы, упомянутое выше, может выглядеть сле-
дующим образом:  матрица [1..N,  1..M] окаймляется нулями так:
вводятся дополнительные  нулевые 0-ая и (N+1)-ая строки и 0-ой
и (M+1)-ый столбцы
     var A: array[0..N+1,0..M+1] of byte;
                          { ввод и окаймление нулями}
     for i:=1 to N do begin
       A[i,0]:=0; A[i,M+1]:=0;
       for j:=1 to M do read(A[i,j]);
     end;
     for j:=0 to M+1 do begin
       A[0,j]:=0; A[N+1,j]:=0;
     end;

                             Задача 15.
     Легко заметить, что для существования решения необходимо прово-
дить  людей  от самого левого входа к самому левому выходу,от самого
правого - к правому и т.д.  Поэтому приведем решение только для слу-
чая б).
     Основная стратегия человека,  вошедшего  в  самый  левый  вход,
состоит в прохождении лабиринта,  используя наиболее левые свободные
места лабиринта,  т.е.  он должен двигаться, держась правой рукой за
"стенку" лабиринта. Этот процесс можно формализовать следующим обра-
зом.  Находясь в очередной позиции лабиринта,  он должен помнить,  с
какой стороны он пришел сюда (слева,  справа, сверху, снизу), и, ру-
ководствуясь этой информацией, вобрать следующее наиболее предпочти-
тельное  направление  в новую позицию (куда он может пойти и где еще
не был).  При этом удобно использовать стек, в верхушке которого на-
ходятся координаты текущей позиции и направление,  по которому в нее
пришли.  При этом все посещенные клетки метятся. Легко заметить, что
если в позицию попали сверху,  то наилучшим направлением будет нале-
во,  затем вниз,  направо, и наконец назад (вверх). Аналогично можно
определить наилучшие направления для других случаев.
     Эта стратегия повторяется каждым из людей, при этом позиции,по-
меченные предыдущими людьми, считаются запрещенными для следующих.

                            Задача 16.
     Для упрощения вычислений рассмотрите преобразование выра-
жения в обратную польскую запись,  т.е.  в такую  бесскобочную
форму, в которой операнды записываются в том же порядке, что и
в исходном выражении,  а  каждый  знак  операции  следует  не-
посредственно за операндами,  над которыми эта операция прово-
дится.
     Пример: Выражение  '(3+5*2)/3-1' преобразуется в '3 5 2 *
+ 3 / 1 -' (сначала будет выполняться операция * над  предыду-
щими двумя операндами 5 и 2,  результат 10 помещается на место
чисел 5 и 2.  Затем - операция + над предыдущими двумя операн-
дами 3 и 10,  результат 13 помещается на место 3 и 10,  и т.д.
Выражение в ходе вычисления будет принимать вид:
     3 5 2 * + 3 / 1 -
     3 10 + 3 / 1 -
     13 3 / 1 -
     4 1 -
     3.
     Алгоритм вычисления скобочного арифметического выражения.
Преобразуем сначала выражение в обратную польскую запись. Каж-
дой операции и открывающей скобке припишем приоритет:
                    приоритет
     ┌─────────────┬──────────┐
     │  (          │  0       │
     │  +,-        │  1       │
     │  *,/        │  2       │
     │ пустой стек │  0       │
     └─────────────┴──────────┘
     Шаг 1. Если во входной строке нет литер, то перейти к ша-
гу 6;  иначе прочитать следующий элемент (скобку, операцию или
операнд) и обозначить его через x.
     Шаг 2.  Если  x  -  операнд,  то перенести его в выходную
строку, поместить вслед за ним разделитель и вернуться у  шагу
1.
     Шаг 3.  Если x - открывающая скобка,  то поместить  ее  в
стек и вернуться к шагу 1. Если x - закрывающая скобка, то пе-
рейти к шагу 4; иначе перейти к шагу 5.
     Шаг 4. Если элемент, находящийся на вершине стека, не яв-
ляется открывающей скобкой, то перенести его из стека в выход-
ную строку,  поместить  за ним разделитель,  а затем повторить
шаг 4.  Если на вершине стека  находится  открывающая  скобка,
удалить ее из стека и вернуться к шагу 1.
     Шаг 5. Если приоритет элемента на вершине стека не меньше
приоритета x,  то  перенести  этот элемент из стека в выходную
строку, поместить за ним разделитель, а затем повторить шаг 5.
Иначе поместить x на вершину стека и вернуться к шагу 1.
     Шаг 6.  Освободить стек, удаляя каждый раз по одному эле-
менту и помещая его в выходную строку с последующим разделите-
лем. Закончить работу.
     Пример:
     Этот алгоритм переводит выражение '(3+5*2)/3-1' в
'3 5 2 * + 3 / 1 -'.
     Если в ходе построения обратной польской записи не  пере-
носить знак  операции  в  выходную строку (где он бы стоял не-
посредственно за теми операндами,  над которыми должна  выпол-
няться эта операция), а взять из выходной строки два последних
операнда, выполнить над ними операцию,  и результат  поместить
снова в  выходную  строку,  то  у  нас после шага 6 в выходной
строке окажется искомый результат.
     Рассмотрим вычисления на примере выражения (3+5*2)/3-1
   Очередной элемент      После обработки элемента
    входной строки       ──────────────────────────────────
                          стек      выходная строка
        (                  (             пустая
        3                  (                3
        +                  ( +              3
        5                  ( +              3 5
        *                  ( + *            3 5
        2                  ( + *            3 5 2
        )                  пуст     Вместо переноса знака * в
                                    выходную строку, мы выпол-
                                    няем умножение над двумя
последними элементами выходной строки,  при этом 5 и 2 из  нее
извлекаются, а  результат умножения 10 - помещается в выходную
строку. Она принимает вид: 3  10.
     Далее мы  должны  были бы перенести знак + из стека в вы-
ходную строку, но вместо этого опять же выполняем сложение над
двумя последними  элементами  и  результат помещаем в выходную
строку, так что она становится следующей:
                                            13
        /                  /                13
        3                  /                13 3
        -                  -        Выполняем деление 13 на 3,
                                   Результат в выходную строку
                                            4
        1                  -                4 1
   входная строка         пуст     В выходную строку помещаем
      пустая                       результат 4-1=3. Это и есть
                                   значение выражения.
     Естественно в  место  выходной  строки  использовать стек
чисел. Операции проводятся над двумя верхними элементами  сте-
ка. Результат снова помещается в стек.

                            Задача 17.
     Так как могут быть потребованы подписи лишь  непосредственных
подчиненных,  то  для  любого разумного способа получения лицензии
подпись всех подписавших чиновников, кроме первого, используются в
одном  и только одном наборе.  Таким образом,  мы можем определить
стоимость подписи любого чиновника как минимум по  соответствующим
ему набором сумм стоимостей подчиненных и взятии для набора. Таким
образом,  мы получаем простой и эффективный  рекурсивный  алгоритм
определения стоимостей чиновников.
     Но у  этой  задачи есть маленький подводный камень, а именно,
должно быть заведено глобальное множество уже пройденных  чиновни-
ков, что исключает повторную обработку этих чиновников.  Сложность
алгоритма - линейна по суммарному числу элементов в наборе.

