                             PАЗНОЕ.

                            Задача 1.
     Пусть программа на языке BASIC состоит из последовательностей
операторов.  Каждая последовательность состоит из ненулевого числа
операторов.  Операторы отделяются друг от друга символом двоеточие
(:),  который для других целей в программе не используется. После-
довательность может располагаться на нескольких строках,  при этом
разбивка оператора на 2 строки не допускается; если последователь-
ность  продолжается  на  следующей строке,  в конце текущей строки
стоит двоеточие.  Последовательности операторов в тексте программы
имеют уникальные номера.  Таким образом,  структура последователь-
ности операторов следующая:
     - каждая новая последовательность начинается с новой строки;
     - в начале последовательности,  до ее номера,  состоящего  не
более чем из 8-ми десятичных цифр, могут присутствовать пробелы;
     - после номера последовательности также могут  присутствовать
пробелы;
     - оператор всегда начинается не с цифры;
     - оператор нельзя разрывать на несколько строк, если оператор
не последний,  за ним (возможно через  пробелы)  следует
двоеточие.
     Переходы в программе  осуществляются  посредством  операторов
goto  или  gosub  (эти  ключевые  слова  могут быть записаны как с
использованием заглавных, так и прописных букв, например GoSUb).
    Вид операторов
           goto номер последовательности
           gosub номер последовательности
(между ключевыми  словами  и  номером   последовательности   могут
присутствовать пробелы).
     Написать программу,  которая читает из файла имя  файла  (имя
файла вводится с клавиатуры),  текст BASIC программы и перенумеро-
вывает последовательности операторов так, чтобы
      - в  выходном  файле  порядок последовательностей совпадал с
порядком последовательностей исходного файла,  отсортированного по
возрастанию номеров последовательностей;
      - первая последовательность выходного файла имела номер f, а
каждая  следующая последовательность имела номер на d больше,  чем
предыдущая (f и d - натуральные числа, вводимые с клавиатуры).
     Текст программы  состоит  не  более  чем из 100 строк,  длина
строки не превышает 80 символов.
     Преобразованную BASIC-программу выводить в файл
                          имя_файла.OUT.
     Входные данные корректны.

                            Задача 2.
    Пусть грамматика языка описывается следующим образом :

 <выражение>::=<операнд> <on> <операнд> | <операнд>
 <on>::=+|-|*
 <операнд>::=<переменная> | <целое без знака>
 <переменная>::= A | B | C | D | ... | Z
 <целое без знака>::= 1 | 2 | 3 | 4 | ... | 9 | 0
 <оператор>::=<IF-оператор> | <WHILE-оператор> | <присвоить>
 <присвоить>::=<переменная>:=<выражение>
 <IF-оператор>::= IF <условие> THEN <оператор> ELSE <оператор>
 <WHILE-оператор>::= WHILE <условие> DO BEGIN <оператор> END
 <условие>=<выражение> > <выражение>
 <программа P>=<оператор> | <программа P><оператор>

     Значок | обозначает 'или'.
     Задается текст программы P. Каждый оператор программы Р начи-
нается с новой строки.  Оператор может быть записан  в  нескольких
строках.  Ввод  программы осуществляется из файла.  Имя файла вво-
дится с клавиатуры. В программе все переменные и ключевые слова за-
писываются заглавными буквами латинского алфавита.  Текст вводимой
программы Р синтаксически правильный.
   Написать программу,  оптимизирующую введенный текст программы Р
по следующим правилам :
   1. Если в операторе IF условие всегда истинно (ложно) (например
      2>1 (1>2)),  то в текст преобразованной программы включается
      только оператор, стоящий за THEN ( за ELSE, если он есть).
   2. Если в операторе WHILE условие всегда ложно,  то WHILE- опе-
      ратор из текста программы исключается.
   3. Если в операторах IF,  WHILE в  <условие>  или  в  операторе
      присваивания в правой части стоит выражение,  численное зна-
      чение операндов которого известно,  то это значение вычисля-
      ется  и записывается вместо <выражения> в условие или вместо
      правой части оператора присваивания соответственно.
   4. Если в  двух  операторах присваивания (обозначим их А и В) в
      программе Р в левой части оператора стоит одна переменная, и
      эта  переменная не используется ни в правой части операторов
      присваивания, ни в условиях IF- или WHILE-операторов, встре-
      чающихся  в  тексте программы между операторами А и В,  то в
      программе Р остается только оператор В.
   5. Если  внутри  тела  цикла  оператора  WHILE  стоит  оператор
      присваивания, и переменная из левой части этого оператора не
      встречается в <условии>, то этот оператор выносится из цикла
      и ставится перед ним.
   6. Если  в  ветках THEN и ELSE оператора IF стоит один и тот же
      оператор присваивания (переменные в левых частях  этих  двух
      операторов  совпадают,  а  значения правых частей одинаковы,
      например,
        IF A>B THEN L:=A+B ELSE L:=B+A),
      то этот оператор присваивания записывается вместо IF-операто-
      ра.
     Вывод программы оптимизатора направляется  в  файл  с  именем
код.OUT.
                               
                            Задача 3.
              'PROLAN/M' (В.В.Прохоров, Свердловск)
     Представим, что  электронный концерн NePhiggah выпустил новый
микропроцессор с компактной  системой  команд.  Операционный  блок
этого  микропроцессора  "признает"  данные  только  одного  типа -
текстовые строки - и "умеет"  исполнять  единственную  операцию  -
контекстную  замену (поиск в строке заданной подстроки и замену ее
на другую  заданную).  Микропроцессор  соединяется  с  двумя  уст-
ройствами  памяти:  одним  -  для  запоминания  программы  (набора
подстановок для контекстных замен) и другим,  R ("почти  неограни-
ченной емкости") - для размещения (в виде текстовой строки) исход-
ных данных, результатов промежуточных преобразований и "ответа".
     Для программирования микропроцессора используется язык, кото-
рый будем условно называть 'PROLAN/M'.  Предваряя  его  формальное
описание, приведем пример программы:

         (aa,b) (ba,a) (bc,a) (c,start) (d,) (b,finish) (,)

. Если эту программу исполнить для строки   abcabcd
, то результатом будет строка               finish
(при этом в  процессе  работы  программы  в  R  последовательно
будут находиться значения
          abcabcd  aaabcd  babcd  abcd  aad  bd  b  finish).

     Ну а формально синтаксис программы на 'PROLAN/M' таков
("::=" означает "есть по определению", а "|" - "или"):

 <'PROLAN/M'-program> ::=  <substitut. sequence>(,)
 <substitut. sequence> ::= <substitution> |
                           <substitut. sequence><substitution>
 <substitution> ::=        (<left part>,<right part>)
 <left-hand part> ::=      <string>
 <right-hand part> ::=     <string> | <empty>
 <string> ::=              <string symbol> |
                           <string><string symbol>
 <empty> ::=
 <string symbol> ::=       <any ASCII character except ',', ')'>

     Исполнение же  микропроцессором  <'PROLAN/M'-program> для за-
данной в R исходной строки проводится так.  Среди <substitution> в
<substit.  sequence> <'PROLAN/M'-program> отыскивается первая, для
которой ее <left part> является некоторой подстрокой строки  R.  В
случае успеха поиска соответствующая подстрока R (при неединствен-
ности  -  самая  левая)  заменяется  на  <right   part>   той   же
<substitution>.  После чего процедура повторяется с самого начала,
но уже для изменившейся R. Процесс повторяется так до тех пор, по-
ка  не  случится,  что ни одна <left part> <'PROLAN/M'-program> не
является подстрокой текущей R.  Тогда процесс исполнения программы
завершается; сложившаяся к этому моменту строка R и есть результат
исполнения  этой  программы   для   выбранной   исходной   строки.
______________________________________________________________________

     Требуется:

     1. Написать программу на PROLAN/M (ее текст должен храниться в
файле  'SUM.PRM'), которая для исходной строки вида
                <natural number1>+<natural number2>=?
, где  <natural  number1>,  <natural  number2>  -  записи  натуральных
десятичных чисел, вырабатывала бы в качестве результата строку вида
        <natural number1>+<natural number2>=<natural number3>
, где  результирующая  строка  содержала  бы   арифметически   верное
выражение. Например, для исходной строки       1990+123=?
Ваша программа должна выдать                   1990+123=2113                     .

     2. Раэработать  программу  для   отладки  программ  на  PROLAN/M,
которая бы
     (a)  запрашивала  имя  текстового  файла,  в   котором   хранится
программа  на  PROLAN/M;
     (b) запрашивала исходную для преобразования строку R;
     (c) производила бы преобразование исходной строки в  соответствии
с программой  из  указанного  файла;
     (d) выдавала  реэультат  на  экран дисплея;
     (e) желатательна  воэможность  эапуска  программы  на  PROLAN/M с
трассировкой исполнения.

     Качество Вашей программы  п.1  будет  оцениваться  жюри  с  одной
стороны по количеству <substitution> в ее <substitution  sequence>,  с
другой - по скорости выполнения ею тестов  жюри.  Так  что  Вы  можете
предложить два варианта программы, каждый из которых хорош  по  своему
критерию.
     Тестирование  программы  п.2  будет  проводиться   в   специально
разработанной жюри для проверки PROLAN/M-системе программирования.
     Качество Вашей программы п.2 будет оцениваться в  зависимости  от
прохождения теста жюри и того, все ли подпункты п.2 будут реализованы.

     
                            Задача 4.
     На шашечной доске размера n x n ее верхний правый угол  имеет
 номер (1,1). В позиции (i,j) стоит фишка, которая может двигаться
 по правилу,показанному на рисунке (допустимые ходы обозначены  х,
 шашка - О). Фишка не может дважды ставиться на одно и то же поле.
 Играют двое, по очереди двигая фишку. Выигрывает поставивший фиш-
 ку в позицию (1,1).
     Для введённых i,j определить,  может ли выиграть первый игрок
 при наилучших ходах второго.
     Написать программу, где первый игрок- компьютер.
 n                                1
┌───┬───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │   │ 1
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │ x │ x │ x │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │ O │ x │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │ x │   │   │   │   │
├───┼───┼───┼───┼───┼───┼───┼───┼───┤
│   │   │   │   │   │   │   │   │   │  n
└───┴───┴───┴───┴───┴───┴───┴───┴───┘

                            Задача 5.
     Прямоугольник, стороны которого выражены целыми числами  M  и
N, разделен на квадраты размером 1x1. Составить программу, которая
находит число квадратов, пересекаемых диагональю прямоугольника.
     Если дан прямоугольник 4x8, то диагональ пересекает 8 квадра-
тов. Если  же  дан прямоугольник 3x11,  то в этом случае диагональ
пересекает 13 квадратов.

                            Задача 6.
     Есть две  обезьяны и куча из L бананов.  Обезьяны по очереди,
начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может
при каждом очередном ходе взять из кучи либо a_1,  либо a_2,  либо
...  a_S бананов (а_1 <a_2 <...<a_S ), а 2-ая при каждом очередном
ходе --либо b_1, либо b_2, либо ... b_K бананов (b_1 <b_2 <...<b_K
).  Нумерация индексов при a и b не имеет никакого отношения к но-
мерам ходов обезьян
     Выигрывает та обезьяна,  которая на своем ходе не может взять
банан(ы) (либо потому, что их не осталось, либо потому что бананов
осталось  меньше  чем a_1 (при ходе первой обезьяны) либо b_1 (при
ходе второй обезьяны)).
     Определить может  ли  выиграть  первая обезьяна при наилучших
ходах соперницы,  которая также стремится  выиграть.  Все  входные
данные - натуральные числа.

                            Задача 7.
     Вводится целое число K>=1.  Бумажная полоса разбита на N кле-
ток (K <= N <= 40).Играют двое,  по очереди выбирая и зачеркивая K
пустых смежных клетки.Выигрывает сделавший последний ход.

    1    2                            N
  ┌────┬────┬────┬────┬         ────┬────┐
  │    │    │    │    │  . . .      │    │
  └────┴────┴────┴────┴         ────┴────┘

      1)Ввести N и определить, имеет ли игрок 1 выигрышную страте-
        гию ( т.е.  может ли игрок 1 выиграть при наилучших после-
        дующих ходах игрока 2).  Сообщение вида 'У игрока  1  (не)
        существует выигрышная стратегия'.

      2)Для N  определить,имеет  ли игрок 1,сделав заданный первый
       ход,выигрышную стратегию.

      3)Провести игру для N и первого хода игрока  1.  За  второго
        игрока  играет программа.Ходы первого вводятся с клавиату-
        ры.  Цель второго игрока -победа.  Ход  задается  индекcoм
        ячейки L (1<=L<=N-K+1).При этом вычеркиваются клетки с ин-
        дексами от L до L+K-1.После каждого хода выводится текущая
        позиция в виде

     1  2  3  ...  N

        *  *

     Сверху печатается номер позиции.Зачеркнутые клетки помечаются
символом '*'.  В конце игры выдать сообщение 'Победа игрока 1(2)'.
При  вводе  N и K выдать подсказывающие сообщения 'N>'и 'K>',  при
вводе хода - 'Ход игрока 1>'.Предусмотреть  контроль  корректности
входных данных.

                            Задача 8.
     Пусть слово - это последовательность от 1 до 8  символов,  не
включающая пробелов.
     Вводится n слов A1,...,An.Можно ли  их  переупорядочить  так,
чтобы получилась "цепочка",  т.е.  для каждого слова Aj его первая
буква должна совпадать с последней  буквой  предыдущего  слова,  а
последняя  буква в Aj - с первой буквой последующего слова;  соот-
ветственно последняя буква последнего  слова  должна  совпадать  с
первой буквой первого слова.  В цепочку входят все n слов без пов-
торений.
     Дать ответ в виде  "Можно"\"Нельзя".
     Если такое упорядочение возможно, то вывести какую-нибудь це-
почку слов. Слова при выводе разделяются пробелами.

                            Задача 9.
     На линейке  из m клеток в разных концах стоят две фишки,кото-
рые ходят по очереди. Каждая из фишек может ходить влево или впра-
во не более чем на К клеток (m<=80;К<=m-2).  При этом нельзя пере-
шагивать через фишку и нельзя оставаться на месте.  Фишка проигры-
вает, если она не может сделать ход. Написать программу, реализую-
щую выигрышную стратегию для одной из фишек.  При этом разрешается
передача хода в самом начале игры.  Предусмотреть контроль входных
данных.

                            Задача 10.
     Составить программу, которая по введенному N выдает последова-
тельность длины N, состоящую из цифр 0 и 1 такую, что ни один фраг-
мент этой подпоследовательности не повторяется подряд трижды.

                            Задача 11.
     Ввести три числа а,b,с.
     1). Представить a в виде суммы минимального числа целых  сла-
гаемых x[i], каждое из которых лежит на отрезке [b,c].
     2). Можно ли представить число а таким образом, чтобы
                                           k
           а = х[1] * x[2] * ... * x[k] =  П x[i], i>=1,
                                          i=1
где b<=x[i]<=c,  х[i], а, в, с - целые. Лучшим считается алгоритм
находящий такое представление с наименьшим числом множителей. Пре-
дусмотреть вариант, когда такого представления не существует.

                            Задача 12.
     Даны три слова X,Y,Z.  Определить,  существует ли слово V та-
кое,  что X,Y,Z являются повторениями слова V.  Если V существует,
то напечатать его.  Слова имеют длину не более 1000 символов. Сим-
вол "пробел" является разделителем слов.

                            Задача 13.
     Даны два положительных целых числа А,В. Напечатать слово "ДА"
или  "НЕТ" в соответствии с тем,  можно ли получить десятичную за-
пись числа А путем вычеркивания одной или более цифр числа В.

                            Задача 14.
     Пусть А  - последовательность букв.  После вычеркивания одной
буквы из А (в одной позиции )получили последовательность В.  После
вычеркивания другой буквы из А (в одной позиции) получили последо-
вательность С.
     Можно ли по последовательностям B и С
     1) Определить вычеркнутые буквы.
     2) Определить последовательность A.
     Примечание: В и C могут быть получены вычеркиванием  одной  и
той же буквы.

                            Задача 15.
     Имеется N книг и два читателя,  А и В, желающих прочитать эти
книги.  Заданы неотрицательные целые числа A[I] и B[I] такие,  что
читателю А (или В) потребуется  A[I]  (соответственно,B[I])  часов
для прочтения книги I,  1 <=I <=N. Процесс чтения начинается в мо-
мент времени 0.  В любой момент времени каждый читатель  не  может
читать  более одной книги и каждую книгу не могут читать оба чита-
теля.
     Для каждого  читателя порядок чтения книг не имеет значения и
может быть произвольным. В процессе чтения любой книги любым чита-
телем допускаются прерывания. Это означает, что этот процесс может
быть прерван в любой целочисленный момент  времени  и  возобновлен
позднее  с  прерванного  места.  В  промежутке между прерыванием и
последующим возобновлением процесса чтения  книги  читатель  может
читать любую не до конца прочитанную книгу.
     Задано целое число К,  2<=K <=N,  и книги пронумерованы таким
образом,  что  ни один читатель не имеет права начать читать книгу
J,  2<= J <= K, прежде чем книга J-1 не будет прочитана обоими чи-
тателями.
     Требуется:
     1. Вычислить наименьший момент времени Т, раньше которого все
        книги не могут быть прочитаны  всеми  читателями.  Вывести
        вычисленное значение Т.
     2. Построить расписание чтения книг каждым читателем, при ко-
        тором  не нарушается ни одно из перечисленных выше условий
        и процесс чтения всех книг завершается в момент времени Т.
        Расписание для каждого читателя вывести в виде

              < РАСПИСАНИЕ ДЛЯ ЧИТАТЕЛЯ А (или В) >

         <Номер книги>  <Начало >  <Конец>
         .......         ......     .....
         .......         ......     .....

        В таблицах  указанного вида необходимо указать все времен-
        ные интервалы, в течение которых читатель А (или В) читает
        книгу и номер этой книги.
     3. Постарайтесь сократить число прерываний для каждого  чита-
        теля.

                             Задача 16.
     В программистском фольклоре есть предание,  что при приеме  в
одну  из ведущих компьютерных фирм претенденту предлагалась решить
следующую задачу:
     Дана последовательность двузначных чисел
                   24, 81, 63, 26, 41, ...
Продолжить ее. Найти правило формирования последующих членов.

                            Задача 17.
     Продолжить следующую последовательность
                  110 , 20 , 12 , 11 , 10 , ...

                            Задача 18.
     Янис и Петрис играют в следующую игру.  Петрис загадывает де-
картовы координаты двух различных точек A(Ax,Ay) и B(Bx,By).  Из-
вестно,  что среди чисел Ax,  Ay, Bx, By нет двух одинаковых. Янис
может задавать вопросы только следующего вида:  "Какое  расстояние
от точки P(Px,Py) до точки A (до точки B)?",  где Px и Py - числа.
В ответ Петрис называет число,  которое является длиной отрезка PA
(или, соответственно, PB). Определить, какое наименьшее количество
вопросов должен задать Янис,  чтобы он смог назвать координаты ка-
кой-либо  точки,  находящейся на серединном перпендикуляре отрезка
AB,  независимо от того,  какие точки загадал Петрис. Описать, как
найти эту точку. Ответ обосновать.

                            Задача 19.
     Известно,  что  среди 13 монет есть одна отличающаяся по весу
(тяжелее одна или легче - неизвестно).  За 3 взвешивания на чашеч-
ных весах найти эту монету.

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

                            Задача 21.
     Составить тесты для проверки  правильности  работы  программы
определения площади треугольника по его сторонам a, b, c.

                    Задача 22 (Прохоров В.В.).
     Учитель попросил Диму написать программу вида
      Ввод (x,y)
      Пока < условия выполнения итерации >
        НЦ
           < тело цикла >
        КЦ
      Вывод (x,y)
т.е. такие  < условия выполнения итерации > (не содержащие никаких
переменных кроме x и y) и < тело цикла >,  чтобы этот фрагмент для
произвольных  введенных в операторе ввода чисел x=x0 и y=y0 выдавал
бы оператором вывода числа x=x0+y0 и y=x0-y0.
     Помогите Диме.

                         Задача 23.
     Игровой автомат состоит из нескольких  изогнутых  трубок,  по
форме  похожих  на перевернутую вверх ногами букву "Y" .  Сверху у
трубы находится входное отверстие,  а два  выходных  отверстия  --
снизу. Труба может находиться в одном из двух возможных состояний:

                    Вход                           Вход

                   │     │                        │     │
                   │     │                        │     │
                   │     │                        │     │
                   │     │                        │     │
                   │     │                        │     │
                  /  \    \                      /    /  \
                /    / \    \                  /    / \    \
              /    /     \    \              /    /     \    \
            /    /         \    \          /    /         \    \

         левый выход    правый выход    левый выход    правый выход

                Состояние 1:                   Состояние 0:
              закрыт левый выход           закрыт правый выход

                   │     │                        │     │
                   │     │                        │     │
                   │     │                        │     │
                   │     │                        │     │
                   │     │                        │     │
                  /  \    \                      /    /  \
                /    / \    \                  /    / \    \
              /    /     \    \              /    /     \    \
            /    /         \    \          /    /         \    \

                    Рис.3                          Рис.4

     Шарики кладутся вовнутрь один за  другим  через  входное  от-
верстие. В состоянии 1 (Рис. 3), шарик покидает трубу через незаб-
локированный правый выход,  при этом Состояние 1 автоматически из-
меняется на Состояние 0 ( Рис.4,  правый вход заблокирован,  левый
-- нет ). В состоянии 0 все происходит наоборот.
                 A                     B                     C
              │     │               │     │               │     │
              │     │               │     │               │     │
              │     │ G1            │     │ G2            │     │ G3
             /    /  \             /    /  \             /  \    \
           /    / \    \         /    / \    \         /    / \    \
         /    /     \    \     /    /     \    \     /    /     \    \
       /    /         \    \ /    /         \    \ /    /         \    \
     /    /             \       /             \       /             \    \
    │    │               │     │               │     │               │    │
    │    │               │     │               │     │               │    │
    │    │               │     │               │     │               │    │
    │    │               │     │               │     │               │    │
    │    │               │     │               │     │               │    │
    │    │               │     │  G4           │     │ G5            │    │
     \    \             / \     \             /    /  \             /    /
       \    \         /    / \    \         /    / \    \         /    /
         \    \     /    /     \    \     /    /     \    \     /    /
           \    \ /    /         \    \ /    /         \    \ /    /
             \       /             \       /             \       /
              │     │               │     │               │     │
              │     │               │     │               │     │
              │     │  G6           │     │  G7           │     │ G8
             /    /  \             /    /  \             /  \    \
           /    / \    \         /    / \    \         /    / \    \
         /    /     \    \     /    /     \    \     /    /     \    \


     Пусть игральный автомат состоит из 8 "Y"-образных трубок,  их
взаимное расположение показано на Рис.5. Вы можете забрасывать ша-
рики через Вход A, Вход B, или Вход C. Пусть, например, первый ша-
рик опускается через Вход A.  Он покидает трубу G1 через левый вы-
ход,  изменяя ее состояние с 0 на 1, поступает в G6 и покидает ав-
томат через левый выход G6 ( изменяя состояние G6 c 0 на  1).  Эту
процедуру мы запишем следующим образом:
       A
     Затем мы  забросим шарик через Вход A (он находится в Состоя-
нии 1).  Шаpик покидает G1 чеpез пpавый выход, изменяя состояние 1
в состояние 0,  попадает в G4, покидает G4 чеpез пpавый выход, из-
меняя состояние 1 в состояние 0,  попадает в G7,  покидает автомат
чеpез  левый выход ( изменяя G7 из состояния 0 в состояние 1 ).Все
вышеизложенные действия мы запишем в виде:
       AA
     Если мы опустим третий шарик через Вход B, четвертый -- через
Вход C, то все действия запишутся следующим образом:
       AABC
     Необходимо:
     1. Ввести с клавиатуры последовательность из 8 двоичных  цифр
(бит), показывающих соответственно начальное состояние G1-G8:
         бит   7   6   5   4   3   2   1   0
        Вход  G8  G7  G6  G5  G4  G3  G2  G1
     Например, последовательность 11001010 означает,  что G8,  G7,
G4 и G2 находятся в Состоянии 1 ( левый вход заблокирован ), тогда
как G6, G5, G3 и G1 находятся в Состоянии 0  (правый вход заблоки-
рован).
     2. Ввести с клавиатуры вторую последовательность  из  8  бит,
показывающих конечные состояния G'1-G'8.
     3. Напечатать последовательность ходов A, B, или C, указываю-
щую, каким образом можно получить конечную позицию, забрасывая ша-
рики через Входы A, B и C.

                             Задача 24.
     Определить, является  ли  периодической   последовательностью
строка символов A1 A2 ... AN, т.е. имеет ли она вид d d ... d, где
d -- некоторая подпоследовательность символов.

                             Задача 25.
     Если мы из корректно записанного  арифметического  выражения,
содержащего  числа,  знаки  операций  и  открывающие и закрывающие
круглые скобки выбросим числа и знаки операций,  а  затем  запишем
оставшиеся в выражении скобки без пробелов между ними, то получен-
ный результат назовем правильным скобочным  выражением  [скобочное
выражение "(()(()))" - правильное, а "()(" и "())(" - нет].
     Найти число правильных скобочных выражений, содержащих N отк-
рывающихся и N закрывающихся скобок.  N вводится с клавиатуры. N -
неотрицательное целое число.

                             Задача 26.
     Одним из стандартных методов кодирования информации  когда-то
был следующий: текст (длины l) записывался по строкам слева напра-
во сверху вниз в прямоугольнике размера m*n  (m*n>=l),  добиваясь,
по  необходимоси,  пробелами;  после этого текст из прямоугольника
выписывался по столбцам и получалось шифрованное сообщение.
     Например: Исходный текст "It is a nice weather today"
     m=5  n=6
                     1 2 3 4 5 6

                  1  I t _ i s _
                  2  a _ n i c e
                  3  _ w e a t h
                  4  e r _ t o d
                  5  a y _ _ _ _

     Шифрованный текст:"Ia eat wry ne iiat scto ehd  "
     Дается шифрованный текст длины s состоящий из букв  и  пробе-
лов, и известно,что в исходном тексте есть по крайней мере одно из
слов набора a ,...,a ,  k<=10,  (под словом  в  тексте  понимается
             0      k
последовательность символов,  не содержащая пробелов, и окруженная
пробелами, за исключением случаев, когда слово стоит в начале либо
конце текста (тогда ему может не предшествовать (за ним  может  не
следовать) один или несколько пробелов)). Дешифровать текст.

                             Задача 27.
     Пусть слово - это последовательность от 1 до 8 заглавных букв
латинского алфавита.
     Задается множество слов A={a[1],  a[2],...,  a[n]},  n<10. Из
слов множества A составляется текст - последовательность слов, за-
писанных друг за другом без  разделителей  пробелов.  Слова  могут
встречаться в тексте произвольное число раз.
     Дешифровка текста - это разбивка текста на слова множества A.
В дешифрованном тексте слова разделяются пробелами.
       Необходимо :
    1.Определить, существует  ли  для  заданного множества A такой
текст, который дешифруется не единственным образом (сам текст при-
водить не надо).
       Примеры :
    1)  A = { B , C }
       Любой текст дешифруется однозначно.
    2)  A = { B , BC , C }
       Существует текст, который дешифруется двумя способами
                      Текст  --->  Дешифровка
                      BBC    --->  B  B  C
                      BBC    --->  B  BC
    2. Если такой текст существует,  то исключить из  множества  A
минимальное число слов так, чтобы после этого любой текст, состав-
ленный из слов полученного множества A,  дешифровался  однозначно.
Напечатать  эти исключенные слова.  Если такой набор не единствен-
ный, то напечатать все наборы.
    3.Для введенного текста произвести его дешифровку и,  если де-
шифровка не единственная, вывести все варианты.
    Примечание: Порядок выполнения пунктов строго фиксирован.

                            Задача 28.
   На рисунке изображен фрагмент  компьютерной  сети.  Система
состоит из  двух  интерфейсов  Международного Союза ORT и двух
компьютеров. Каждый интерфейс подключен к отдельному компьюте-
ру, один из которых является компьютером-передатчиком,  другой
- компьютером-приемником.  Интерфейсы соединены друг с  другом
следующим образом:  все  восемь выходов интерфейса-передатчика
соединены с восемью входами интерфейса-приемника,  восьмой вы-
ход интерфейса-приемника  соединен  с  восьмым  входом  интер-
фейса-передатчика. Реле входов (выходов)  интерфейсов  нумеру-
ются с 0 по 7.  Для включения реле-выхода с номером A запишите
в порт с адресом 642 байт,  в котором бит с номером A равен 1.
Для выключения  реле-выхода  с номером A запишите в порт с ад-
ресом 642 байт, в котором бит с номером A равен 0. Для получе-
ния информации  о  состоянии реле-входа с номером A прочитайте
байт из порта компьютера с адресом 642 и проанализируйте бит с
номером A. Биты нумеруются, начиная с младшего.
     Задание:
Написать программу, которая осуществляет:
     1. Ввод с клавиатуры строки символов на  компьютере-пере-
датчике.  Передачу строки через связанные интерфейсы на компь-
ютер-приемник.  Отображение данной строки на компьютере-прием-
нике.
     2. Проверку типа компьютера (приемник или передатчик), на
котором загружается программа с выдачей сообщения об этом.
     3. Проверку правильности соединения интерфейсов  согласно
рисунку.
     Примечание:
     Выдача байта информации D в порт с адресом 642 и считыва-
ние байта D из порта с адресом 642 производится следующим  об-
разом:
  ┌──────────────────────┬─────────────────┬────────────────┐
  │Язык программирования │ Запись в порт   │ Чтение из порта│
  ├──────────────────────┼─────────────────┼────────────────┤
  │  С                   │ OUTPORTB(642,D) │ D:=INPORT(642) │
  │  Pascal              │ PORT[642]:=D;   │ D:=PORT[642]   │
  │  Basic               │ OUT 642,D       │ D=INP(642)     │
  └──────────────────────┴─────────────────┴────────────────┘

  ┌───┐   ┌─────────────────┐            ┌─────────────────┐   ┌───┐
  │ К │   │ INPUT    OUTPUT │            │ INPUT    OUTPUT │   │ К │
  │ О │   │                 │            │                 │   │ О │
  │ М │   │ O  0      0   O─┼────────────┼─O  0      0   O │   │ М │
  │ П │   │ O  1      1   O─┼────────────┼─O  1      1   O │   │ П │
  │ Ь ├───┤ O  2      2   O─┼────────────┼─O  2      2   O ├───┤ Ь │
  │ Ю │   │ O  3      3   O─┼────────────┼─O  3      3   O │   │ Ю │
  │ Т │   │ O  4      4   O─┼────────────┼─O  4      4   O │   │ Т │
  │ Е │   │ O  5      5   O─┼────────────┼─O  5      5   O │   │ Е │
  │ Р │   │ O  6      6   O─┼────────────┼─O  6      6   O │   │ Р │
  └───┘   │ O  7      7   O─┼────────────┼─O  7      7   O │   └───┘
          └─┼───────────────┘            └───────────────┼─┘
            └────────────────────────────────────────────┘

                            Задача 29.
     Пометить ребра куба числами от 1 до 12 так,  чтобы  для  всех
вершин сумма пометок входящих ребер была одинакова.

                            Задача 30.
                     "Дырокол". Бабурин Е.А.
    Дырокол пробивает на длинной полосе бумаги по два одина-
ковых отверстия за одно нажатие его рычага и после  несколь-
ких нажатий получается следующее состояние бумаги.

     0    0      0    00     0    00   00        0    0

     Л    П      Л    ПЛ     П    ЛЛ   ПП        Л    П

    Буквы "Л" и "П" под лентой  обозначают,  соответственно,
левое и правое отверстия дырокола.
    По известным координатам отверстий на полосе  определить
возможную ширину между отверстиями дырокола.


                            Задача 31.
                            КОМПОСТЕР
                                   Авторы: АНДРЕЕВА Е.В.
                                           МАРЧЕНКО А.П.
     В билете  пассажира  оказалось пробито отверстий больше,  чем
штырей в компостере.  Пассажир утверждал,  что пользовался  только
одним компостером,  но случайно нажал на него несколько раз. Конт-
ролеру требуется определить, могло ли быть получено заданное распо-
ложение  отверстий  одним  и тем же компостером,  если билет можно
пробивать с обеих сторон неограниченное число  раз  и  произвольно
перемещать  и  поворачивать относительно компостера.  Пробитые от-
верстия не выходят за пределы билета.  В  билете  было  пробито  N
(N<10) отверстий.

ТРЕБУЕТСЯ :
 А. Для компостера с двумя штырями (S=2) составить программу,
    которая :
     1. Определяет, можно  ли  получить  заданным компостером
        требуемое  расположение отверстий в билете.  Если это
        возможно,  то  изображает  вид билета  после  каждого
        нажатия   компостера.  В  противном  случая,  выводит
        соответствующее сообщение.
     2. Определяет количество K различных компостеров  каждым
        из которых можно пробить заданную конфигурацию.
     3. При  K=0  (см. п.2)  находит  компостер,   с  помощью
        которого  можно   пробить  наибольшее  количество  из
        заданных отверстий.
     4. Находит  минимальное  число  нажатий,  требуемое  для
        пробивки заданной конфигурации отверстий, для каждого
        компостера из пункта 2.
 Б. Решить задачу А для компостеров с числом штырей S (S>2).

ПРИМЕЧАНИЯ.
 * Все исходные данные - натуральные числа.
 * Компостеры,  дающие  при  однократном  нажатии совпадающие
   конфигурации отверстий, считаются одинаковыми.
 * Относительное  расположение  отверстий в билете и штырей в
   компостере  вводится  либо  с  клавиатуры, либо из файла с
   именем COMP.DAT .
   Структура вводимой информации: {N,x[1],y[1],...,x[N],y[N],
   S,u[1],v[1],...,u[S],v[S]},   где  x[i], y[i] - координаты
   отверстий  в  билете,  u[i], v[i] -  координаты  штырей  в
   компостере.
 * Нажатие   компостера   (см.  п.1)   моделировать  клавишей
   "Пробел".
 * При  выводе конфигурации на экран (см. п.п.1,3) изображать
   координатную сетку. При этом программа должна осуществлять
   подходящее масштабирование.

             Задача 32 (Литовская олимпиада 1992 г.)
                Тендеpные тоpги на товаpной биpже.
   На бирже есть N продавцов и M покупателей  и  1  товар.  Каждый
продавец определяет для себя и объявляет минимальную цену,  по ко-
торой он согласен продать  товар,  а  каждый  покупатель  называет
максимальную цену,  по которой он еще согласен купить товар.
     1) Найти такую единую цену на товар, чтобы сумма сделок купли-
продажи была максимальной.
     2) Найти такую максимальную единую цену на  товар, чтобы общее
количество продавцов и покупателей, учавствующих в торгах, было мак-
симальным.
     ВВОД:
          <N=> N
          <Цены продажи> с1, ..., сN
          <M=> M
          <Стоимости покупки>  p1, ..., pM
     ВЫВОД:
          <Цена товара по пункту 1:> цена
          <Cумма сделок> сумма
          <Объемы продаж по продавцам> о1, ..., оN
          <Стоимости покупки>  p1, ..., pM

          <Цена товара по пункту 2:> цена
          <Количество участников торгов> количество
          <Номера участников-продавцов:> s1, ..., si
          <Номера участников-покупателей:> b1, ..., bj

                           Задача 33.
     M одинаковых дисков,  на ободе каждого из которых нанесены по
порядку числа от 1 до N,  насажены на общую ось. На диски мы смот-
рим  через  "окошко" - такую планку с прямоугольной прорезью,  что
через прорезь видно только по одному числу с каждого диска. Требу-
ется  развернуть  диски друг относительно друга так,  чтобы макси-
мальная сумма элементов "окошка" при синхронном  вращении  дисков,
была бы минимальна.

