                             РАЗНОЕ.

                            Задача 1.
     Чисто программистская задача.

                            Задача 2.
     Другими словами необходимо написать программу, выполняющую те
же действия, что и команда RENUM языка ВASIC.

                            Задача 4.
     Позиция (1,1)  проигрышная  для игрока,  который должен с нее
сделать свой очередной ход (фишка уже стоит в позиции  (1,1).  Все
соседние позиции - (1,2),  (2,2), (2,1) - выигрышные для делающего
текущий ход (они приводят  в  выигрышную  позицию  (1,1).  Позиции
(3,1),(1,3),(3,3) - также проигрышные (любой ход из них приводит в
выигрышную позицию, и игрок, делающий следующий ход, выигрывает).
     Анализируя позиции дальше,  получаем предположение, что пози-
ции с обеими нечетными координатами являются проигрышными для  на-
чинающего,  все  остальные  позиции  -  выигрышные  для него.  Это
действительно так: из проигрышной позиции с обеими нечетными коор-
динатами после любого допустимого хода мы попадаем в позицию,  где
хотя бы одна из координат четная (выигрышную).  Из позиции с  хотя
бы  одной четной координатой мы всегда можем опять попасть в пози-
цию с обеими нечетными  координатами  (проигрышную  для  делающего
очередной ход). Так как последняя позиция (1,1) имеет обе нечетные
координаты,  то человек, начинающий с позиции, где хотя бы одна из
координат  четная,  всегда сможет сделать так,  чтобы после любого
его хода фишка была в позиции с обеими нечетными координатами, а в
конце концов - в позиции (1,1).
     Итак, если i и j нечетные,  то первый игрок при наилучших
ходах второго всегда проигрывает, иначе - выигрывает.

                           Задача 5.
     Если N и M взаимно просты (т.е.  если НОД(N,M)=1),  то  Коли-
чество=N+M-1. Если же k=НОД(N,M)<>1, то диагональ большого прямоу-
гольника можно представить как объединение k кусочков,  каждый  из
которых является диагональю прямоугольника размера (N/k,M/k),  где
N/k и M/k взаимно просты. Получаем, что
              Количество=k*(N/k+M/k-1)=N+M-НОД(M,N).
Итак, всегда Количество=N+M-НОД(M,N).

                           Задача 6.
     Будем обозначать текущую ситуацию в игре парой (S,i), где S -
количество бананов,  оставшихся в куче,  перед текущим ходом  i-ой
обезьяны (i равно 1 или 2).
     Для того,  чтобы  (S,1)  была выигрышной для игрока 1,  среди
возможных ситуаций после его хода (S-a_1,2), ... ,(S-a_k,2) должна
быть хоть одна проигрышная для игрока 2 (в эту то ситуацию и  надо
будет перевести игру);  если все ситуации выигрышные для игрока 2,
то (S,1) - проигрышная для игрока 1 (как бы он не поступал, он все
равно проиграет).
     Пусть ситуация после хода игрока 1 стала (S',2). Опять же де-
лаем все допустимые ходы из этой позиции и смотрим является ли по-
лучившаяся ситуация (S",1) выигрышной,  проигрышной или такой, ко-
торую мы еще не можем оценить.  Если выполняется последняя альтер-
натива,  то из (S",1) мы опять делаем все возможные ходы, анализи-
руем, и т.д.
     Если мы в конце концов определили, для кого является выигрыш-
ной текущая позиция, то возвращаемся к предыдущему ходу и пытаемся
определить,  какая позиция для делающего ход и т. д., пока не вер-
немся к ситуации (L,1).

const l1=200;
      s=10;
var   a: array [0..l1,1..2] of byte; { в ячейке a[L,i] хранится
                                      информация, кто выигрывает
                                         в ситуации (L,i)}
      b: array [1..2,0..s] of byte;  { массив возможных ходов    }
                                     { первого и второго игроков }
                                     { в b[i,0] хранится число   }
                                     { возможных ходов игрока i  }
      l,i,j:integer;

  Function  f(ba:Integer;No: Byte): Byte;
   Var i,p,r: Byte;      { рекурсивная функция вычисления (L,i) }
   Begin                    { f=i, если в (ba,i) выигрывает i }
     if Ba<0             { после хода монет <0? }
     Then  f:= 3-No      { выигрыш игрока с номером 3-Nо }
     else if ba=0                { монет = 0? }
          then begin             { выигрыш No}
                  f:=No;
                  a[ba,no]:=no;
               end

          Else if a[ba,no]<>0      { в этой ситуации мы уже были }
               Then F := a[ba,no]  { в ней выигрывает a[ba,no] }
               Else
                    Begin { эту ситуацию мы еще не рассматривали }
                         r := 0;
                         { мы будем делать все возможные ходы }
                         For i := 1 to b[No,0] do
                            if ba-b[no,i]>=0 { если ход возможен }
                                             { то делаем его }
                            then r := r or F(Ba-B[No,i],3-No);
                         if r=0 then r:=no;
                         If (No and R)<>0 { есть выигрышный ход? }
                         Then p := No     { да, (ba,i)=No }
                         Else p := 3-No;  { нет, (ba,i)=3-No }
                         A[Ba,No]:=p; { запоминаем эту информацию }
                         f:=p;
                    End;
   end;

begin
     for i:=0 to l1 do
      for j:=1 to 2 do  A[i,j] := 0;
    write('s=');
    readln(b[1,0]);     { b[1,0] = количество ходов первого игрока }

    for i:=1 to b[1,0] do
    begin
     write('a',i,'=');  { сами ходы }
     Readln(b[1,i]);
    end;
     write('k=');
     Readln(b[2,0]);    { b[2,0] = количество ходов второго игрока }
     For j := 1 to b[2,0] do
     begin
       write('b',j,'=');
       Readln(b[2,j]);  { ввод ходов }
     end;
repeat                  { для данных ходов вводятся значения L }
     write('L=');       { число бананов }
     readln(l);


     if f(l,1)=1        { вызов рекурсивной функции-проверки }
     then writeln('1-я выиграла')
     else writeln('1-я проиграла');

     for i:=1 to b[1,0] do  { распечатка результатов возможных ходов }
     if (l-b[1,i])>=0       { из начальной позиции L }
     then writeln('b=',b[1,i],' winner=',a[l-b[1,i],2]);
      writeln;
until false;
end.

                            Задача 7.
     Идея решения аналогична изложенной в задаче про обезьян.

                            Задача 8.
     Если n=1,  и единственное слово начинается и заканчивается на
одну и ту же букву, то цепочка построена.
     Для того,  чтобы можно было переупорядочить слова A1, ..., An
из набора A в "цепочку",  необходимо,  чтобы совокупность букв, на
которые заканчиваются слова,  совпадала с совокупностью  букв,  на
которые эти слова начинаются (другими словами, чтобы каждой завер-
шающей букве слова соответствовала такая же начальная буква  како-
го-то слова).  То, что это не достаточное условие, показывает при-
мер: AB, BC, CA, DE, ED. "Цепочку" построить нельзя.
     Так как  цепочка  обязана  пройти через каждое слово,  то все
равно, с какого слова набора A начинать. Возьмем слово A1. Удаляем
его из множества A: A:=A\A1. Ищем в A какое-нибудь слово Ai, начи-
нающееся с последней буквы слова A1 (такое слово всегда  существу-
ет,  так как мы считаем, что необходимое условие, упомянутое выше,
выполняется).  Удаляем Ai из A: A:=A\Ai, ищем в A какое-нибудь Aj,
начинающееся  с  последней буквы Ai и т.д.  Продолжаем до тех пор,
пока либо все слова A1,  ... ,An не войдут в цепочку (тогда задача
решена), либо пока не окажется, что A не пусто, и в нем нет слова,
начинающегося на последнюю букву x последнего  слова  (кстати,  из
необходимого  условия следует,  что эта буква x совпадает с первой
буквой первого слова). Мы нашли какую-то подцепочку.
     Пример: A=(AB,BC,CA,BD,DC,CB).
     Подцепочка1: AB,BC,CA.
     Цепочка существует: AB,BD,DC,CB,BC,CA.
     Пусть мы  нашли подцепочку 1.  Берем опять какое-нибудь слово
из A в качестве начального для очередной подцепочки и опять повто-
ряем построение следующей подцепочки, и т.д.
     В конце концов пусть множество A стало пустым, и весь началь-
ный  набор слов A1,  ...  ,An распался на k подцепочек.  Начнем их
склеивать:
     Пусть в подцепочках i и j соответственно есть слова u и v та-
кие, что в u и v совпадают первые буквы. Пусть цепочка i имеет вид
i=BuC,  а j=EvD (тут B,C,D,E - некоторые последовательности слов).
Склеенная из i и j цепочка будет иметь вид
     EuCBvD.
(Проверьте, что такая склейка корректна!)
     Склеивая все подцепочки, получим искомую цепочку. Если на ка-
ком-то шаге окажется,  что склейка никаких двух подцепочек  невоз-
можна, то задача неразрешима.
     Пример 1.  Для приведенного в предыдущем примере набора  слов
будет 2 подцепочки:
     AB, BC, CA    и
     BD, DC, CB.
     У них совпадают первые буквы в словах BC и BD.  После склейки
получаем
     AB, BD, DC, CB, BC, CA.
     Пример 2.  A=(ACA, BB). Две подцепочки: ACA и BB. Слов с сов-
падающими первыми буквами в них нет, задача неразрешима.

     Вариант #2 решения задачи.
     Если при  составлении  цепочки оказалось,  что в наборе A нет
слова с первой буквой,  совпадающей с последней буквой  последнего
слова Aj цепочки, то Aj "отщепляем" от нее и пытаемся найти другое
подходящее слово.  Если это не удается,  то "отщепляем"  очередное
последнее слово цепочки и т.д.  Если на каком-то шаге A пусто,  то
задача решена,  иначе если на каком-то шаге цепочка стала  пустой,
то задача неразрешима.
     Пусть есть набор слов A=(A1, ... ,An). Каждому слову приписан
его уникальный  номер,  равный индексу.  Слова упорядочены по воз-
растанию индекса.
     Цепочка = A1
     A=A\A1; инд=1.
     Пока (A не пусто) и (цепочка не пустая) повторять
     нц
       Если в A есть подходящее слово с индексом > инд
       то приписываем к цепочке это слово,
          слово удаляем из A
          инд=1
       иначе "отщепляем" от цепочки последнее слово Aj
             инд=j
             Aj заносим в A
     кц
     Если A пусто, то цепочка найдена
     иначе задача не имеет решения.

     Этот метод называется "перебор с возвратом" ("backtracking").

                            Задача 9.
     Предположим, что левая фишка (будем называть ее Ф1) можем хо-
дить только вправо,  а правая фишка Ф2 - только влево, и ход пере-
давать нельзя. Решение задачи в первоначальной постановке сводится
к решению задачи при налагаемых выше ограничениях.
     Пусть первый  ход делает Ф1.  Ф1 выигрывает,  если количество
клеток между фишками d(Ф1,Ф2) (вначале оно равно m-2)  не  делится
нацело  на  k+1.  Действительно,  пусть  Ф1 делает такой ход,  что
d(Ф1,Ф2) кратно k+1.  Какой бы ход не сделала Ф2 (например,  на  L
клеток влево),  Ф1 следующим ходом смещается на k+1-L клеток впра-
во, и,  таким  образом,  после  хода  Ф1 расстояние d(Ф1,Ф2) снова
кратно k+1.  А так как 0 также делится на k+1 нацело,  то наступит
момент,  когда d(Ф1,Ф2)=0 и предыдущий ход был ходом Ф1,  т.е.  Ф2
проиграла.  Если (m-2) mod (k+1)=0,  то Ф1 при наилучших ходах  Ф2
проигрывает.
     Если разрешить фишкам ходить как  влево,  так  и  вправо,  то
всегда  выигрывает  та  фишка,  после хода которой d(Ф1,Ф2) кратно
k+1.

                            Задача 10.
     Последовательность строится так:  сначала  пишется  0,  затем
повторяется  следующее действие:  уже написанную часть приписывают
справа с заменой 0 на 1, 1 на 0, т.е.
                0 -> 01 -> 0110 -> 01101001 ->...
     Докажите, что предложенная  последовательность  удовлетворяет
условию задачи.
     Если не смогли этого сделать, то вот доказательство:
     Будем нумеровать цифры последовательности,  начиная  с  нуля.
Итак,  a(0)a(1)=01,  a(2)a(3)=10=a(1)a(0). Отметим, что последова-
тельность состоит из 'кирпичиков' 01 и 10 (любые a(2k)a(2k+1) есть
либо a(0)a(1), либо a(1)a(0)). Любой отрезок четной длины, начина-
ющийся с элемента с четным индексом a(2k) имеет  поровну  нулей  и
единиц.  Предположим, что в M есть три смежных одинаковых отрезка.
Если есть такие отрезки, то есть и отрезки минимальной длины. Мож-
но считать, что сначала идет начальный отрезок P, затем подряд три
смежных одинаковых отрезка S1,S2 и S3 минимальной длины, S1=S2=S3=
=S:
                       P S1 S2 S3.
     Будем обозначать длину отрезка A через IAI.
     Есть 4 возможных варианта:
     1) IPI=2k, ISI=2l.
     Будем писать 0* вместо 01 и 1* вместо 10. С помощью этих сим-
волов последовательность M записывается так же, как и раньше:
     M=0*1*1*0*1*0*0* ...
     Значит и  P,  и  S можно записать с помощью символов 0* и 1*;
начальный отрезок P будет состоять из k знаков 0* и 1*, а S - из l
знаков. Уберем звездочки у цифр - последовательность M от этого не
изменится.  А из P,S1,S2 и S3 мы получим новые отрезки P', S1',S2'
и  S3'  с  длинами вдвое меньшими.  Отрезки S1',S2' и S3' остаются
одинаковыми, а длина каждого из них станет l. Мы получили противо-
речие с утверждением о минимальности длины S.
     2) IPI=2k, ISI=2l+1.
     Отрезок S1 начинается элементом с четным индексом.  Длина от-
резка S1 S2 четная (она равна 4l+2),  и в нем одинаковое число ну-
лей и единиц.  Длина S1 нечетная, и, без нарушения общности, пред-
положим,  что нулей в S1 больше, чем единиц, тогда в S2 единиц бу-
дет больше чем нулей?! Противоречие с тем, что S1=S2.
     3) IPI=2k+1, ISI=2l+1.
     Отрезок S2  S3  имеет  четную  длину и начинается элементом с
четным индексом. Далее рассуждения аналогичны приведенным в пункте
2.
     4) IPI=2k+1, ISI=2l.
     Последний элемент  отрезка  P  имеет индекс a(2k) (вспомните,
что нумерация элементов начинается с нуля).  Пара   a(2k) a(2k+1)
есть либо 01,  либо 10,  и всегда a(2k)<>a(2k+1).  Первые элементы
S1,S2 и S3 будут, соответственно, a(2k+1), a(2k+2l+1), a(2k+4l+1).
Поэтому из совпадения S1=S2=S3 следует, что
     a(2k+1)=a(2k+2l+1)=a(2k+4l+1)<>a(2k)=a(2k+2l)=a(2k+4l).
     Следовательно, так как
       a(2k)a(2k+1)=a(2k+2l)a(2k+2l+1)=a(2k+4l)a(2k+4l+1),
то мы можем считать, что повторяющиеся отрезки S1 S2 S3 начинаются
в позиции a(2k),  IPI=2k,  ISI=2l,  а этот случай уже  разобран  в
пункте 1.

                            Задача 11.
     Рассмотрим сначала случай, когда a, b, c, xi - натуральные.
     1) Разбивка на слагаемые.
     Если a<c,  то задача неразрешима,  если a лежит на [c,d],  то
задача решена.
     Пусть a>d.  Минимальное число слагаемых  будет  тогда,  когда
каждое  из  слагаемых  будет  как  можно  больше.  Введем  функцию
ceil(x)=k+1, если k<x<=k+1, k - целое. Покажем, что в случае, если
разложение существует, то необходимо ceil(a/d) слагаемых.
     Пусть k=ceil(a/d).  Если мы возьмем k слагаемых по d, то пре-
вышение над a будет p=k*d-a. Каждое из k слагаемых мы можем умень-
шить не более чем на d-c.  Количество уменьшаемых слагаемых должно
быть n=ceil(p/(d-c)).  Если n>k, то разложения не существует (сла-
гаемых,  которые надо уменьшить,  больше,  чем у нас есть, другими
словами,  a div c = a div d,  и a mod c <> 0,  a mod d <> 0). Если
n<=k, то L, L=p div (d-c), слагаемых уменьшаем на (d-c), одно сла-
гаемое - на p mod (d-c), остальные остаются без изменений (равными
максимальному).
     Если a,  b, c, xi - целые, то алгоритм практически не изменя-
ется.
     2) Разбивка на сомножители.
     Метод решения этой задачи аналогичен использованному при  ре-
шении  задачи о нахождении максимальной по длине возрастающей под-
последовательности введенной  последовательности  (см.  задачу  20
главы "Рекуррентные соотношения и динамическое программирование").
     Опять будем рассматривать только случай a>d.
     Обозначим через L упорядоченное по возрастанию множество  де-
лителей числа A, лежащих на отрезке [c,d], количество делителей не
превышает 2*SQRT(A) (если a=f*g,  то f<=SQRT(a), g>=SQRT(a), всего
разных  f - не более SQRT(a),  столько же и разных g).  Пусть L1 -
минимальный элемент из L, a L2- максимальный. В массив S[1..k] за-
несем  по  возрастанию  все делители числа a (включая и само число
a=S[k]), начиная с минимального элемента из L. Из утверждения выше
следует, что k<=2*SQRT(A)+1.
     Будем искать минимальную по длине последовательность  элемен-
тов  массива S,  ведущую из множества L в число a=S[k] такую,  что
каждый последующий элемент последовательности при делении на  пре-
дыдущий дает частное,  принадлежащее множеству L,  и нулевой оста-
ток.
     Заведем массивы B[1..k] и C[1..k].  В B[i] будем заносить ин-
декс  последующего  элемента  в  подпоследовательности минимальной
длины,  ведущей из S[i] в S[k] (B[i]=0,  если в a из S[i]  попасть
невозможно),  в  C[i] будет храниться число элементов в этой мини-
мальной последовательности (отметим,  что мы рассматриваем  только
такие последовательности, у которых частное от деления последующе-
го члена последовательности на предыдущий принадлежит множеству L,
а остаток от деления нулевой).
     Сначала во  все  элементы  C,  кроме последнего,  занесем ка-
кое-нибудь большое число,  например 2*A.  Если C[i]=2*A,  то будем
считать,  что последовательности элементов, идущей от S[i] к S[k],
пока не обнаружено.
     После заполнения матриц A и B мы  находим  минимальную  длину
цепочки, ведущей из множества L в число a.
     for i:=1 to k-1 do C[k]:=2*A;  { последовательности нет }
     C[k]:=1;      { последовательность из одного элемента A }
     B[k]:=0;      { предыдущего элемента нет }
       for i:=k-1 downto 1 do
         for j:=i+1 downto k do
           if (S[j] div S[i] >=L1) and   { частное S[j]/S[i] }
              (S[j] div S[i] <=L2) and   { принадлежит L, и  }
              (S[j] mod S[i] =0)         { остаток нулевой }
           then if C[i]>C[j]+1    { если длина обнаруженной }
                then begin   { сейчас подпоследовательности, }
                        { идущей от S[i] к S[k], меньше, чем }
                  C[i]:=C[j]+1;   { ранее найденная, то кор- }
                  B[i]:=j         { ректируем длину и индекс }
                end;              { следующего элемента }
       i:=1; min:=2*A; j:=0;
       while S[i]<=L2 do
       begin
         if C[i]< min
         then begin
           min:=C[i];    { корректируем минимум }
           j:=i;         { сохраняем индекс первого элемента }
         end;
         i:=i+1
       end;
       if j=0
       then writeln('Разложения не существует')
       else begin
              writeln('Разложение:');
              write(A[j]);
              for i:=1 to min-1 do
              begin
                P:=j;
                j:=B[j];
                write(A[j]/A[p]) { распечатка сомножителя }
              end
       end
     В случае, если a, c, d, xi - целые, в массив S помещаем в по-
рядке возрастания модуля все делители числа A, начиная с минималь-
ного элемента в L. Далее - аналогично.

                            Задача 12.
     См. решение задачи о том,  является ли введенное слово перио-
дическим повторением какого-то другого слова (Задача 24).

                            Задача 13.
     Решается аналогично  задаче 23 (глава "Рекуррентные соотноше-
ния и динамическое программирование").

                            Задача 14.
     Если последовательности B и C совпадают,  то вычеркнутых букв
определить нельзя.
     Если B и C различаются ровно в одной позиции (т.е.  в A  были
вычеркнуты соседние буквы), то определить вычеркнутые буквы можно,
а  последовательность  A  -  нет  (пример:  A='ABCDB',   B='ACDB',
C='ABDB').
     Чуть-чуть упростим задачу.  Уберем из начала и конца последо-
вательностей  B  и C все совпадающие элементы.  Получим последова-
тельности B' и C'.  Пример B='albce', C='alcde', B'='bc', C'='cd',
т.к. первые два и последний символ у B и C совпадают. Если мы смо-
жем восстановить слово, из которого получается B' и C', то мы смо-
жем восстановить и A.
     Пусть B'=b1b2b3 ... bk
           C'=c1c2c3 ... ck.
     Если b1=c2=b3=c4= ... и              (*)
          c1=b2=c3=b4= ...,
     то определить последовательность A нельзя,  выброшенные буквы
- это b1 и c1.
     Пример: B='abab',  C='baba'.  В качестве A  можно  взять  как
'babab', так и 'ababa').
     Если же (*) не выполняется, то можно найти и A, и вычеркнутые
буквы.  Мы  находим  такие  элементы в B' и C',  что c(i)=b(i+1) и
b(i)<>c(i+1) (или c(i)<>b(i+1), а b(i)=c(i+1)), и получаем началь-
ную строчку A=b(1) ... b(i)b(i+1)c(i+1)b(i+2)
... b(k) (или A=c(1) ... c(i)c(i+1)b(i+1)c(i+2) ... c(k)).
     Пример: B'='bc'
             C'='cd'
     Слово из которого получается и B' и C' - 'bcd'.

                            Задача 16.
     Эту же последовательность можно записать и так:
                2, 4, 8, 16, 32, 64, 128, ...
     Очередной член последовательности - 28.

                            Задача 17.
     Члены последовательности есть запись числа 6 в двоичной, тро-
ичной, четверичной,  пятеричной, шестеричной, ... системах счисле-
ния. Все остальные члены последовательности равны 6.

                            Задача 18.
     Если мы знаем расстояние R от некоторой точки С до  точки  А,
то  точка  A  будет лежать где-то на окружности O(R,C) радиуса R с
центром в точка C.
     Возьмем на оси абсцисс две точки - V и W. Узнаем
     1. Расстояние R1 - от точки V до точки A.
     1. Расстояние R2 - от точки W до точки A.
     1. Расстояние R3 - от точки V до точки B.
     1. Расстояние R4 - от точки W до точки B.
     Точка A - это одна  из  двух  точек  пересечения  окружностей
O(R1,V)  и  O(R2,W).  Точка B - это одна из двух точек пересечения
окружностей O(R3,V) и O(R4,W).  Обозначим точки пересечения окруж-
ностей соответственно  через  A1,  A2  и B1,  B2.  Эти точки можно
рассматривать как вершины  равнобедренное  трапеции  с  основания-
ми-отрезками [A1, A2] и [B1, B2]. (Трапеция равнобедренная так как
точки A1 и B1 симметричны относительно оси абсцисс точкам A2 и  B2
соответственно). Отрезок  [A,B], фигурирующиий в задаче, - один из
следующих четырех:  [A1,B1], [A1,B2], [A2,B1], [A2, B2] - т.е. это
либо боковая сторона трапеции, либо ее диагональ. А так как в рав-
нобедренной трапеции срединные перпендикуляры к боковым сторонам и
срединные перпендикуляры к ее диагоналям пересекаются в одной точ-
ке (докажите это!), то для нахождения этой искомой точки достаточ-
но четырех вопросов.

                            Задача 19.
     Определим вначале  ситуации,  когда  можно  можно  определить
фальшивую монету за одно взвешивание. Это возможно сделать, если:
     есть две  неизвестные  монеты и одна стандартная (заведомо не
фальшивая);
     есть три  неизвестные  монеты и известен вес фальшивой монеты
(т.е. информация о том, больше или меньше ее вес).
                             Алгоритм:
     Разобьем 13 монет на 3 части: 4,4 и 5 монет.
     1. вес монет в первых частях равны. Тогда это стандартные мо-
неты. Будем обозначать их через с а возможные фальшивые монеты че-
рез ф.
      2-е взвешивание
         ссс и  ффф (остались неопределенными только фф из третьей
         части).
     Если веса  равны,  то  фальшивая среди оставшихся двух.  Если
нет, то среди взвешенных трех, но ее вес известен.
     2. Веса  монет  в  первых  частях  не равны.  Тогда монеты из
третьей части - стандартные монеты.  Определим  взвешенные  монеты
как  т (тяжелые) или л (легкие) в зависимости от результатов взве-
шивания.
      2-е взвешивание
         ссст и тттл
Если веса равны,  то фальшивая среди оставшихся трех легких.  Если
нет, то возможны следующие ситуации.
     2.1. ссст легче тттл. Понятно, что фальшивая монета находится
среди трех тяжелых монет.
     2.2. ссст тяжелее тттл.  Понятно,  что фальшивая монета нахо-
дится среди двух монет: тяжелой монеты слева или легкой справа.
     Поэтому фальшивую  монету можно определить за одно оставшееся
взвешивание.

                          Задача 20.
{                     Задача "Быки  и  коровы"
      Пользователь загадывает число из 4 цифр,  каждая из которых от
1 до 6,  причем все цифры различны.  Разработать  алгоритм,  который
угадывает  число по следующим правилам:  выводится число и пользова-
тель сообщает,  сколько в нем "быков" и "коров",  т.е.  сколько цифр
стоят  на своих местах и сколько цифр содержатся в обоих числах,  но
совпадают лишь по значению.  Например,  пусть загадано  число  1264,
спрошено 1256. В этом случае 2 быка (1,2) и одна корова (6)
     б) Правила игры те же, но загадывается 6-значное число с цифра-
ми от 1 до 9, причем среди цифр допускаются одинаковые.

     Примечание : Спрошенное число должно удовлетворять правилам для
загадываемого; компьютеру на ход дается 1 минута .

     Итак, 1-ое что приходит в голову играть по следующему  правилу:
называть первое попавшееся число, которое может быть задуманно, т.е.
при сопоставлении любого ранее спрошенного числа с новым должно  по-
лучится такое-же количество 'быков' и 'коров'. Число будем представ-
лять в виде массива цифр. }
 const  MaxSgn = 6; {  Максимальное значение в числе }
          Sgn = 4; { Количество цифр в числе }
type S = 1..MaxSgn;
     Numb = array[1..Sgn] of S;
function cows(n1,n2:Numb):byte;
 { Сравнивает два числа и возвращает результат сравнения в виде
   <количество быков>*10+<количество коров> }
var i1,i2 : 1..Sgn;
    a : byte;
begin
 { Необходимо сравнивать все цифры первого числа со всеми цифрами второго }
 a:=0;
 for i1:=1 to Sgn do
  for i2:=1 to Sgn do
   if n1[i1]=n2[i2] then
     if i1=i2 then a:=a+10 { Встретился 'Бык' }
     else inc(a);
 cows:=a;
end;
type Step = Record  { Информация об одном вопросе - ответе }
       n : Numb;  { Спрошенное число }
       answer : byte;  { Ответ }
     end;
     Game = array[1..32] of step;
     { Информация о всех вопросах - ответах }
var Nstep : byte; { Номер текущего шага }
    Info : Game;
    Curnumb : Numb;
    i,j : integer;
    b : boolean;
BEGIN
 clrscr;
 for i:=1 to Sgn do Curnumb[i]:=i;
 Nstep:=0;
 while true do
  { Пока не будут перебраны все числа или не найденно решение }
  begin
   { Спросить текущее число }
   for i:=1 to Sgn do write(Curnumb[i]);
   write(' ? ');
   inc(Nstep);
   Info[Nstep].n:=Curnumb;
   readln(Info[Nstep].Answer);
   { Пользователь должен ввести число, первая цифра
     которого 'Быки', вторая - 'Коровы' }

   if (Info[Nstep].Answer div 10+Info[Nstep].Answer mod 10)>Sgn then
    begin writeln('Плохая игра !'); exit; end;
   { 'Быков' и 'Коров' вместе не может быть больше, чем цифр }
   if Info[Nstep].Answer=10*Sgn then exit;
   { Далее идет генерация нового числа }
   repeat
    i:=Sgn;
    { Увеличение числа на 1-цу }
    while (i>=1) and (Curnumb[i]=MaxSgn) do
      begin
       Curnumb[i]:=1;
       dec(i);
      end;
    if i<1 then
      begin { Все числа перебраны, а ответ не найден }
       writeln('Вы неправильно отвечали !'); exit; end;
    inc(Curnumb[i]);
    b:=true;
    { Проверка на встречающиеся одинаковые цифры }
    for i:=1 to Sgn do
     for j:=i+1 to Sgn do
      b:=b and (Curnumb[i]<>Curnumb[j]);
    for i:=1 to Nstep do b:=b and (cows(Curnumb,Info[i].n)=Info[i].Answer);
    until b;
  end; { while }
END. { program }

     Итак, наша  программа  работает  следующим  образом:  мы  путем
последовательного увеличения на 1 генерируем все возможные 6-значные
числа,  отбираем среди них те, в которых все цифры различные, и, на-
конец,  те  из них,  которые удовлетворяют хранящимся в массиве Info
ответам, задается пользователю в качестве вопроса. Возникает ряд ре-
зонных вопросов: сколько всего интересующих нас 4-значных цифр и ка-
кая их часть не содержит повторений.
     За сколько  шагов  может угадать ответ самый быстрый алгоритм и
насколько хороша наша стратегия?
     Давайте попытаемся  ответить на них.  Итак сколько всего чисел?
     Пусть k цифр и m позиций.  В первой позиции может стоять  любая
из  k  цифр,  что  нам дает k вариантов.  Во второй-также любая из k
цифр, т.е. k^2. И так далее m раз, т.е. всего k^m вариантов. Обобщим
эту идею.
     Определение: размещение с n повторением из k элементов по m на-
зывается m-элементный массив натуральных чисел, каждое из которых не
превосходит k.
     Утверждение: Число  размещений  с  повторениями из k по m равно
k^m. Доказательство проводим по индукции:
     Базис индукции: При m=1 у нас ровно k вариантов.
     Индуктивный переход:  Пусть утверждение верно при m=n-1.  Дока-
жем,  что  оно  верно при m=n.  Зафиксируем число 1.  Справа к этому
числу припишем k^(n=1) размещений из k по n-1. Аналогично поступим с
1,2,3...k. Получим k^(n-1)*k=k^n вариантов.
     Таким образом,  число 4-значных чисел с цифрами от 1 до 6 равно
6^4=1296. Теперь посмотрим, сколько из них не содержит повторяющихся
цифр.
     Определения: размещением  из k элементов по m называется m-эле-
ментный массив каждая компонента которого не превосходит k  и  среди
них не встречаются одинаковые. Очевидно, что множество размещений не
пусто лишь при m<=k.
     Число размещений из k по m принято обозначать A.
     Утверждение A=k*(k-1)*...(k-m+1)=k!/(k-m+1)!
     Доказательство проводим по индукции:
     Базис индукции: При m=1 у нас ровно k вариантов.
     Индуктивный переход: Пусть утверждение верно при m=n-1. Выберем
любое из k!/(k-n+1)! размещений из k по n-1. Чисел, которые в нем не
участвуют-(k-n+1). Приписывая их поочередно справа к выбранному раз-
мещению мы получим (k-n+1) вариантов. Перебирая все размещения:
   (k!/(k-n+1)!)*(k-n+1)=k!/(k-n)!
     Таким образом,число 4-значных чисел с цифрами от  1  до  6  без
повторений равно A46=6*5*4*3=360,  т.е.  в 3 раза меньше,  чем число
вариантов,  которые мы перебирали. Итак мы нашли один способ для оп-
тимизации нашей программы: генерировать не все числа, а лишь те, ко-
торые не содержат повторяющихся цифр. Возьмем это на заметку, а сей-
час попробуем оценить максимальное число шагов, за которое отгадыва-
ет лучший игрок. Вариантов ответа у нас:
     Пусть угадано  4  цифры.  Среди  них  могут быть 2,1,0 "быков".
Пусть угаданы 3 цифры.  Среди них могут быть 3,2,1,0 "быков".  И так
далее: получаем 3+4+2+1=10 вариантов.
     Таким образом за  каждый  вопрос  количество  допустимых  чисел
уменьшается,  если мы рассматриваем худший случай, не более чем в 10
раз.  Число шагов,  за которое угадывает лучший игрок,  не менее чем
[log10 360]+1=3
     Ну а теперь попытаемся повысить эффективность работы программы.
Как уже было отмечено выше,  нам достаточно перебрать не 1096 комби-
наций,  а всего лишь 360.  Это не отразится на быстроте  угадывания,
т.е. числе шагов, так как не изменим стратегии "первый попавшийся из
подходящих", но уменьшит время обдумывания хода.
     Генерировать числа будем следующим образом:  для начала выберем
множество цифр,которое в него входит,  ну а затем будем переставлять
элементы этого множества между собой. Множество цифр удобно, для на-
ших целей,  представить в виде массива длины  4,  элементы  которого
расположены в порядке возрастания. Будем генерировать эти массивы в
лексикографическом порядке, т.е. сначала  сравниваются  первые  циф-
ры,если они равны -- вторые, и так далее. То есть:
     1   2   3   4
     1   2   3   5
     1   2   3   6
     1   2   4   5
     1   2   4   6
     1   2   5   6
     1   3   4   5
       .   .   .
       .   .   .

Значит, мы должны увеличить самую правую цифру,  какую это возможно,
и уменьшить затем те цифры,  какие стоят за ней.  Заметив, что номер
цифры,  которую нужно увеличивать,  уменьшается на 1,  а как  только
последний  элемент массива можно будет увеличить, скачкообразно ста-
новится равной длине массива, приходим к следующему алгоритму:
    {n-число цифр}
    {A-массив который содержит текущие комбинации}
   Var
      p:integer;
        {номер элемента ,который увеличивается в данный момент }
   Var
      i:integer;

     for i:=1 to n do
       a[i]:=i;{ Начальное значение }

     p:=n;{ увеличивается крайняя правая цифра }

     while p>=1 do
      begin
         {Write(A)}-{Последовательность готова};
         for i:=k  downto p do
           A[i]:=A[p]+i-p+1;
         if a[k]=n then dec(p);
                   else p:=k;
      end;

Для генерирования всевозможных перестановок множества служит следую-
щая идея:  Пусть у нас сформированы всевозможные перестановки  длины
N-1  .Вставляя  оставшийся элемент в каждую перестановку во все воз-
можные позиции, мы получим все комбинации длины n. Например, число 1
в перестановку 2 3 можно вставить следующими 3-мя способами:
     1  2  3
     2  1  3
     2  3  1
Следует отметить,  что  получающиеся  перестановки обладают приятным
свойством: каждая перестановка получается из предыдущей путем обмена
двух соседних элементов.  Применяя эту идею рекурсивно,  мы получим,
например, следующую последовательность перестановок:
     1  2  3
     2  1  3
     2  3  1
     3  2  1
     3  1  2
     1  3  2
Для применения  этого  алгоритма в рекурсивной форме нам понадобится
хранить всевозможные перестановки.  Давайте попытаемся привести этот
алгоритм  к  нерекурсивной  форме.  Для i-го элемента нам необходимо
знать:

    Куда он сейчас движется - вправо или влево.

    Знать номер возможного из n-i+1 мест в перестановке  длины  n-i,
    которое он сейчас занимает.

Мы приходим к следующему алгоритму:
  { B - массив элементов перестановки }
  { Direc - массив направлений, i-й элемент равен TRUE, если тело i движется
    вправо }
  { Posit - массив положения i-го элемента в перестановке n-i элементов }

    for i:=1 to n do
      begin
        B[i]:=i;
        Posit[i]:=1;
        Direc[i]:=TRUE;
      end;
    Posit[n]:=0;
     Давайте попытаемся привести этот алгоритм к нерекурсивной  фор-
ме. Для i-го элемента нам необходимо знать:
     Куда он сейчас движется-вправо или влево.
     Номер возможного из n-i+1 мест в перестановке длине n-i,  кото-
рое он сейчас занимает.
  Мы проходим к следующему алгоритму:
  {В-массив элементов перестановки}
  {Direc-массив направлений. i-й элемент равен true,
   если число i движений вправо }
  {Posit- массив положения i-го элемента в перестановке
   n-i элементов}
For i:=1 to n do
 begin
  b[i]:=i;
  posit[i]:=1;
  direc[i]:=true;
 end;
posit[n]:=0;
i:=1;
while i<n do
 begin
  direct[i]:=not direct[i];
  posit[i]:=1;
  if direct[i] then inc(x);
  inc(i)
 end;
if i<n then
 begin
  if pirof[i] then k:=c[i]+x
              else k:=n-i+1-c[i]+x;
              b[k]<->b[k+1];
              inc(posit[i])
 end
end;
  И, наконец, новый вариант программы игры
Const MaxSgn=6;
         Sgn=4;
Type s=1..MaxSgn; {цифра}
     Numb=array[1..Sgn] of s;
function cows(n1,n2:Numb):byte;
 { Сравнивает два числа и возвращает результат сравнения в виде
   <количество быков>*10+<количество коров> }
var i1,i2 : 1..Sgn;
    a : byte;
begin
 { Необходимо сравнивать все цифры первого числа со всеми цифрами
   второго }
 a:=0;
 for i1:=1 to Sgn do
  for i2:=1 to Sgn do
   if n1[i1]=n2[i2] then
     if i1=i2 then a:=a+10 { Встретился 'Бык' }
     else inc(a);
 cows:=a;
end;
type Step = Record  { Информация об одном вопросе - ответе }
       n : Numb;  { Спрошенное число }
       answer : byte;  { Ответ }
     end;
     Game = array[1..32] of step;
     { Информация о всех вопросах - ответах }
var NStep:byte;
    Info:game;
Procedure testnumber;
{процедура проверяет, удовлетворяет ли входное число ранним ответам,
 и,  если да, то задает его в качестве вопроса. В случае, если число
 угадано, заканчивает игру}
Var i:byte;
begin
 for i:=1 to nstep do
  if cows(n,info[i].n)<>info[i].answer then Exit;
 inc(Nstep);
 info[nstep].n:=n;
 for i:=1 to sgn do write(n[i]);
 write('   ?   ');
 readln(info[nstep].answer);
 if info[nstep].answer=sgn*10 then
                              halt;
                              {игра окончена}
 end; {test number}
Var tset{текущее n-элементное подмножество}
    ,tn:number;
    i,j,k,l:byte;
    direc:array[1..sgn] of boolean;
    posin:array[1..sgn] of byte;
begin
{инициализация}
nstep:=0;
for i:=1 to sgn do tset[i]:=i;
i:=sgn;
while i>=1 do
begin
 tn:=tset;
 for j:=1 to sgn do begin
 posit[i]:=1;
 direct[i]:=true;
 end;
posit[sgn]:=0;
j:=1;
testnumber(tn);
while j<sgn do
 begin
  j:=1;
  k:=0;
  while posit[j]=sgn-j+1 do
   begin
    posit[j]:=1;
    direct[j]:=not direct[j];
    if direct[j] then inc(x);
    inc(j);
   end;
  if j<sgn then
   begin
   if direct[j] then l:=posit[j]+n;
                else l:=sgn-j+1+posit[j]+k;
   inc[posit[j];
  end;
 end;
writeln('Плохая игра');
end.

                            Задача 21.
     Тесты должны проверять не только работу программы на коррект-
ных данных, но и на некорректных. Например:
     a    b    c
     0    0    0        Это все не треугольники!
    -1    1   0.5
     1    1    3
     0    1    2
     Какие еще тесты можно предложить?

                    Задача 22 (Прохоров В.В.).
     Обозначим условия через F(x,y):
     Пусть x=2, y=4. Тогда F(2,4)=True, а F(6,-2)=False.
     Пусть x=6, y=-2.Тогда F(6,-2)=True,а F(4,8)=False.
т.е. F(6,-2) должна равняться и True и False одновременно!  Следо-
вательно такого < условия выполнения итерации > не существует. За-
дача алгоритмически не разрешима. Но если мы разрешим использовать
в условии обращение к функции F(x,y),  которая  возвращает  всегда
логическое  значение  False,  и изменяет аргументы x и y требуемым
образом, то тело цикла не будет выполняться, и в этом случае зада-
чу можно решить.

                         Задача 23.
     Метод 1.  Во всех узлах (трубках) схемы  мы  должны  получить
состояние Gi'.  Первоначально установим G1,  G2 и G3 в G1',  G2' и
G3',  выбрасывая,  по необходимости,  шарики через входы A,  B и С
соответственно.  Для того, чтобы G1,G2 и G3 оставались в состоянии
G1', G2' и G3' необходимо, чтобы через каждый из входов забрасыва-
лось лишь четное число шариков.
     Если проследить за шариками,  заброшенными в игровой автомат,
то мы можем заметить, что результат хода, например, ABC аналогичен
результату хода BCA,  т.е.  от порядка заброски шариков ничего  не
зависит!
     Рассмотрим узлы,состояние которых может меняться при забрасы-
вании шариков через вход A, т.к. при выбранной методике забрасыва-
ния только четного числа
               A

               *
               |  \
               |    \
               |      \
               |        \
               |          \
               |            \
               |              \
               |                \
               |                  \
               |                    \   G4
               |                     /*
               |                   /    \
               |                 /        \
               |               /            \
               |             /                \
               |           /                    \
               |         /                        \
               |       /                            \
               |     /                                \
               |   /                                    \
          G6   | /                                        \  G7
               *                                            *


шариков через входы всегда G1=G1',  то состояний G6  G4  G7  может
быть лишь 2^3=8,  от 000 до 111. Если мы будем забрасывать через A
пары шариков,  то при забросе серии максимум из 8 пар шариков  ка-
кое-то состояние G6 G4 G7 должно обязательно повториться на протя-
жении серии,  а далее состояния будут  циклически  повторяться,  и
случай с забрасыванием более 8 пар шариков сводится к случаю с ко-
личеством пар, не превосходящим 8.
     Аналогично, для  забрасывания шариков через B мы получаем се-
рию из не более чем 2^5=32 пар шариков,  на протяжении которой бу-
дут установлены все возможные состояния G4 G5 G6 G7 G8, а для вхо-
да C серия, как и для A, будет иметь длину не более 8 пар.
     Перебирая все  возможные  комбинации A2x B2y C2z забрасывания
шариков (тут A2x обозначает серию из 2X забрасываний шариков через
вход A,  0<= x,y <=8,  0<=z<=32 ) получаем либо комбинацию-решение
задачи, либо определяем отсутствие решения.
     Метод 2.  Можно рассматривать эту задачу как задачу на графе.
Вершины графа будут обозначать Y-трубки,  а дуги - соединения этих
трубок. Итак, у нас есть граф с 8 вершинами, каждой из которых мо-
жет быть приписана одна из пометок 0 или  1.  Всего  есть  2^8=256
всевозможных состояний игрального автомата. Каждое состояние можно
представить в виде 8-и битного числа. Создадим новый граф П на 256
вершинах следующим образом:
    1) Пометим вершины номерами от 0 до 255.  Каждая вершина графа
П соответствует одному из возможных состояний системы Y-трубок.
    2) Для каждого состояния системы i - от 0 до 255 повторять
        1. В состоянии i забросить шарик через вход А. Система пе-
        рейдет в состояние iA. В графе П соединить ориентированной
        дугой вершины i и iA. Пометить эту дугу символом А.
        2. В состоянии i забросить шарик через вход B. Система пе-
        рейдет в состояние iB. В графе П соединить ориентированной
        дугой вершины i и iB. Пометить эту дугу символом B.
        3. В состоянии i забросить шарик через вход C. Система пе-
        рейдет в состояние iC. В графе П соединить ориентированной
        дугой вершины i и iC. Пометить эту дугу символом C.
    3) Из вершины графа П,  соответствующей начальному  состоянию,
найти кратчайший путь (по количеству дуг) в вершину, соответствую-
щую конечному состоянию.  Пометки дуг на этом пути являются поряд-
ком заброса через входы шариков. Если пути не существует, то зада-
ча решения не имеет.
     Алгоритм поиска кратчайших путей см.  в главе "Задачи на гра-
фах".

                             Задача 24.
     Для решения данной задачи введем так называемую функцию отка-
зов F(j),  принимающей целочисленные значения [ Ахо А. и др. Пост-
роение и анализ  вычислительных  алгоритмов.,  М.,  1979,  с.386].
Функция F задается так: F(j) -- наибольшее число s<j, для которого
A1 A2 ... As -- суффикс цепочки A1, A2, ..., Aj, т.е.
        A  A  ... A  = A      A      ... A
         1  2      s    j-s+1  j-s+2      j

  Если такого s=>1 нет, то F(j)=0.

                         (m)
   Определим функцию    F   (j) следующим образом:

           (1)
       1) F   (j)=F(j)

           (m)       (m-1)
       2) F   (j)=F(F     (j)) для m>1.

   Будем вычислять  функцию  F итеративно.  По определению F(1)=0.
Допустим, что вычислены F(1), F(2), ... , F(j). Пусть F(j)=i. Что-
бы вычислить F(j+1) исследуем A    и A    . Если A    = A    , то
                               j+1     i+1        j+1    i+1
F(j+1)=F(i)+1 ,

   поскольку   A  A ... A  A   = A      A      ... A  A   .
                1   2    i  i+1   j-i+1  j-i+2      j  j+1

   Если A   <> A   , то тогда надо найти наибольшее значение i, для
         j+1    i+1
которого
              A  ... A  = A      ... A   и A    = A   ,
               1      i    j-i+1      j     i+1    j+1
если такое i существует.  Если такого  i  нет,  то  очевидно,  что
F(j)=0. Пусть i , i , ... -- наибольшее, второе по величине и т.д.
               1   2
значения i, для которых
                 A  A  ... A  = A      ... A .
                  1  2      i    j-i+1      j

     С помощью простой индукции убедимся, что

                      (2)                       (k)
   i =F(j), i =F(i )=F   (j),  ..., i =F(i   )=F   (j), ....
    1        2    1                  k    k-1


Итак, в случае A   <> A    находим наименьшее m, для которого либо
                j+1    i+1
          (m)
      1) F   (j)=u  и  A    = A   , и полагаем тогда F(j+1)=u+1,
                        j+1    u+1
либо
          (m)
      2) F   (j)=0  и  A    <> A , и тогда F(j+1) полагаем равным 0.
                        j+1     1

     Алгоритм вычисления F следующий:

         begin
            F[1]:=0;
            for j:=2 to n do
               begin
                  i:=F[j-1];
                  while ( A[j]<>A[j+1] ) and ( i>0 ) do
                     i:=F[i];
                  if ( A[j]<>A[i+1] ) and ( i=0 )
                  then F[j]:=0
                  else F[j]:=i+1;
               end;
           end.

   Этот алгоритм  вычисляет  F за O(n) шагов.  Чтобы доказать это,
покажем, что сложность оператора while при работе программы ( про-
порциональная числу уменьшений значения i оператором i:=F[i] ) ли-
нейно зависит от N.
   Единственный способ  увеличить i в этом фрагменте программы --
это выполнить оператор F[j]:=i+1  в  третьей  от  конца  программы
строке.  Этот оператор может выполняться не более N-1 раза, следо-
вательно,  и уменьшение i в операторе while может произойти не бо-
лее N раз.  Остальная часть алгоритма имеет сложность O(n), и поэ-
тому и весь алгоритм имеет сложность O(n).
    Итак, мы вычислили F(n)=U, это означает, что
              A  A  ... A   = A     ... A                      (*)
               1  2       U    N-U+1     N
    Для того, чтобы последовательность
              A  ... A
               1      N
была периодической необходимо и  достаточно,  чтобы  длина  общей
части двух строк в (*)
                         A      ... A
                          N-U+1      U
была кратна длине периода (в качестве периода последовательности
тут выступает строка A  ... A   ).
                      1      N-U

    Действительно, если A  ... A   = A      ... A      , то по
                         1      N-U    N-U+1     2(N-U)

свойству (*) и  A      ... A       = A         ... A        и т.д.
                 N-U+1      2(N-U)    2(N-U)+1      3(N-U)

   Для окончательного решения задачи

      1) найдем длину l перекрывающейся части строк в (*)
            l=U-(N-U+1)+1 =2*U-n;
в случае l<=0 последовательность A ... A  непериодическая. Стоп.
                                  1     N
      2) Если l>0 , то проверим, делится  ли нацело l на длину пе-
риода (т.е. на N-U)
     l mod (N-U) = (2U-N) mod (N-U) = - ((N-U)-U) mod (N-U) =
                         =U mod (N-U) = R
   Если R=0, то последовательность периодическая с периодом
                           A ... A   ,
                            1     N-U
иначе -- нет.


                          Задача 25.
     Назовем скобочное выражение элементарным, если оно представи-
мо в виде (S),  где S - правильное скобочное выражение.  Очевидно,
что каждое непустое скобочное выражение можно единственным образом
представить в виде
                               ES,
где
     E - элементарное скобочное выражение;
     S - скобочное выражение (возможно, пустое).
     Обозначим через S(n) число правильных скобочных  выражений  с
2n  скобками.  Тогда  число  элементарных скобочных выражений с 2n
скобками есть S(n-1). Таким образом
            n
      S(n)=SUM(S(i-1)*S(n-i)).
           i=1
     Замечая, что S(0)=1,  - одно пустое скобочное  выражение,
мы приходим к алгоритму сложности O(n^2).

     ДРУГОЕ РЕШЕНИЕ этой задачи:
     Будем изображать знаком / открывающую скобку, а \ - закрываю-
щую.  Правильное скобочное выражение (ПСВ) при n=1 будет выглядеть
так:
                                /\
                               0  1
     Если мы возьмем картинку
                               / \
                             / \ / \
                            0   1   2

то все ПСВ с n=2 будут такими:

                       / \ / \    и     /\
                       0   1   2       /  \
                                       0   2
- то есть каждому ПСВ соответствует свой единственный и неповтори-
мый путь  между вершинами 0 и 2.  Аналогично, все ПСВ с  n=3 будут
описываться путями в графе
                               / \
                             / \ / \
                           / \ / \ / \
                          0   1   2   3

и т.д. Подсчитаем число ПСВ (число путей) при n=3.
      C ->    1           В вершину A мы можем попасть единствен-
            /   \         ным способом - из точки 0, равно в B,C и
    B ->   1     3  <- D  точку 1 можно попасть, соответственно,
          / \   / \       только из точек A, B, A. В  E можно
  A ->   1    2    5      попасть как из 1, так и из  B, поэтому
        / \ / ^ \ / \     пометка E есть сумма пометок этих узлов,
       1   1  E  2   5    т.е. 2. В D можно попасть либо из C
       0   1     2   3    (пометка 1), либо из E (пометка 2), и,
                          следовательно, пометка D=3 и т.д.
     Аналогично находим количество ПСВ для любого n.

                          Задача 26.
     Так как нам известна длина s шифрованного текста,  то нам не-
обходимо  разложить  s на всевозможные пары множителей ( например,
для s=6 эти пары будут 1*6,  2*3, 3*2, 6*1 ), переписать шифрован-
ный  текст  в  таблицу  T  соответствующего  множителям размера по
столбцам и посмотреть,  есть ли в полученном тексте ( если его чи-
тать по строкам ), хоть одно слово из набора.
     Необходимо проверить все возможные наборы множителей, так как
текст  может дешифроваться неоднозначно.  Также надо предусмотреть
обработку случая, когда текст не дешифруется вообще.
     Если s слишком большое, то матрица размера [1..s, 1..s] может
не поместиться в память машины.  В этом случае можно  промоделиро-
вать доступ  к тексту длины s как к массиву T[1..n,  1..m],  nm=s;
при этом обращение к элементу Т[i,j] эквивалентно обращению к эле-
мету (i-1)*n+j кодированного текста(представьте себе, что мы весь
текст разбили на куски длины m - строки матрицы  Т,  j-ый  элемент
i-ой строки  массива T будет соответствовать букве (i-1)*n+j коди-
рованного текста.

                          Задача 27.
    Один из возможных алгоритмов решения задачи такой:
    1. Предположим,  что существует текст, дешифровка которого не-
однозначна,  следовательно,  существует и текст минимальной длины,
для которого возможны по меньшей мере две разбивки
             b[1] b[2]...b[k] = c[1] c[2]...c[m]
на слова множества A.  Представляя текст в виде  отрезка  DE,  эти
разбивки мы можем изобразить следующим образом

         b[1]   b[2]               ...                  b[k]
    D  ├─────┼────────┼──────────────────────────────┼───────┤  E


          c[1]    c[2]  c[3]        ...                  c[m]
    D  ├─────────┼────┼─────┼──────────────────────────┼─────┤  E


     Из того, что текст минимальной длины, следует, что концы слов
в разных разбивках не могут лежать на одной вертикали (кроме конца
текста),  т.к.  b[1]  <>  c[1],  то одно из кодовых слов (например
b[1]) должно входить в другое в качестве префикса и представляться
в  виде  c[1] = b[1] p[1] ,  где p[1] - это оставшаяся часть слова
(суффикс).  Далее, либо p[1] входит в b[2] (b[2] =p[1] p[2]), либо
b[2] входит в p[1] (p[1] = b[2] p[1] ) в качестве префикса.  Опре-
деляем новый суффикс p[2]. Продолжая выделять префиксы и суффиксы,
получаем,  что  на  каком-то шаге p[j] совпадет с одним из кодовых
слов.
    Эти рассуждения являются основой следующего алгоритма :
    На нулевом шаге возьмем все пары (a[i], a[j]),  i <> j, таких
кодовых слов,  что одно из них есть префикс другого,  и найдем все
суффиксы p[0,k].
    На j-ом шаге для всех пар (p[j-1,k],  a[i]),  где одно из слов
является префиксом другого,  опять находим все суффиксы,  и те  из
них,  которые не появлялись на предыдущих шагах алгоритма, обозна-
чим p[j,k].
    Эти шаги повторяем либо до тех пор, пока какой-либо суффикс не
совпадет с одним из кодовых слов (и тогда существует  неоднозначно
декодируемый  текст),  либо  пока на очередном шаге не появится ни
одного нового суффикса  (и  тогда  для  любого  текста  существует
единственная дешифровка).
    Т.к. количество кодовых слов ограничено,  то и суффиксов также
конечное  число,  и  на каком-то шаге алгоритм обязательно остано-
вится.
    Этот алгоритм принадлежит в первоначальном варианте A.  Сарди-
насу и Дж. Паттерсону (см. Кибернетический сборник, вып.3 стр. 93-
102 ).
    2. Если существует текст,  который,  используя A,  дешифруется
неоднозначно,  то начинаем выбрасывать из A слова и их комбинации,
пытаясь получить множество A' с максимальным  числом  слов  такое,
что все тексты, составленные из слов A' дешифруются однозначно.
    Сначала из A удаляем i-ое слово ,  i = 1, 2, ... , n, и делаем
проверку по пункту 1. Если удалением одного слова из A мы не полу-
чаем искомого множества A',  то тогда генерируем все сочетания  по
n-2 слова из множества A,  и для каждого полученного множества де-
лаем проверку по пункту 1, и т.д.
    Воспользуемся следующим  алгоритмом  генерации  сочетаний по i
слов из множества A:
    В массиве  B  будут  находиться индексы используемых на данном
шаге элементов из A (общее их число i).  В качестве начальной кон-
фигурацией возьмем следующую: B[j]=j, j=1,...,n.
    Ищем B[j] с максимальным индексом j такое,что B[j]<n+j-i, уве-
личиваем  это  B[j]  на  1,  а для всех k>j полагаем B[k]=B[k-1]+1
(B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с
максимальным номером j,  чтобы при заполнении возрастающими значе-
ниями элементов массива B[k],  k>j, последний элемент B[i] не пре-
восходил бы n). Если такого B[j] не существует, то генерация соче-
таний для данного i закончена.
    Начинаем генерацию  с  i=n-1  и проводим ее с уменьшением i до
тех пор,  пока либо i не станет  равно  1  (тогда  A'  состоит  из
единственного  слова),  либо пока проверка по пункту 1 не даст од-
нозначности декодировки.
    3. Этот пункт реализуется следующим рекурсивным алгоритмом по-
иска с возвращением (все слова массива A упорядочены по  номерам):
    а) Если строка пустая,  то одна из возможных дешифровок найде-
на, иначе при разборе текста мы проверяем a[i] (при изменении i от
1 до n) на вхождение в начало дешифруемой в данный момент строки.
    б) Если какое-то a[i] входит в строку как префикс,  то запоми-
наем номер i этого слова,  затем выделяем слово  из  строки,  а  с
остатком текста производим операцию разбора по пункту а).
    Если ни одно из а[i] не входит в качестве префикса в дешифруе-
мую сейчас строку,  то осуществляем возврат на пункт а), предвари-
тельно  добавляя в начало строки последнее удаленное оттуда слово,
и пытаемся выделить из текста слово с большим номером  в  A.  Если
возврат осуществить невозможно (т. к. мы находимся в начале исход-
ной строки),  то алгоритм заканчивает свою работу.  Все  возможные
дешифровки найдены.
    Задача 1. Докажите следующую теорему (Марков А. А.):
    Для однозначности декодировки текста достаточно выполнения од-
ного из двух следующих условий:
    1) не  существует  ни  одной  пары  кодовых  слов (a[i], a[j]),
i<>j, такой, что одно из этих слов есть префикс другого.
    2) не  существует  ни  одной  пары  кодовых  слов (a[i], a[j]),
i<>j, такой, что одно из них есть суффикс другого.
    Задача 2.  Приведите пример такого множества кодовых слов, что
для него не выполняется ни условие 1,  ни условие 2 из предыдущего
пункта, а декодировка любого текста, составленного при помощи это-
их слов - однозначная.

                            Задача 28.
     Обратите внимание на то,  что от посылки сигнала на интерфейс
до приема сигнала должно пройти некоторое время. В программе необ-
ходимо учесть возникновение этой паузы.

                            Задача 29.
     Чтобы суммы меток ребер при вершинах  были  равны,  необходимо,
чтобы  эта  сумма равнялась 2*(1+2+...+12)/8,  так как каждому ребру
смежны 2 вершины (т.е. оно подсчитывается дважды), а количество вер-
шин - 8. Но число 2*(1+2+...+12)/8=2*12*13/(2*8) - не целое. Поэтому
нумерации не существует.

                            Задача 31.
     Полное описание  решения  этой  задачи  можно найти в журнале
"Информатика и образование" N 5-6 за 1992 г.

                            Задача 32.
    Сформируем массив A из всех цен покупок и продаж. Очевидно, что
искомая единая цена для каждого из пунктов  есть  один из элементов
данного массива.
    1. Просматриваем элементы массива, и для каждой из текущих цен
вычисляем сумму сделок. Находим максимальную из сумм сделок.
    2. Просматриваем элементы массива, и для каждой из текущих цен
вычисляем общее  число  участников  торгов.  Находим  максимальное
число участников и соответствующую этому числу максимальную цену.

