13 мая 1994 года

                       И.А.Волков, В.М.Котов

              СБОРНИК ОЛИМПИАДНЫХ ЗАДАЧ ПО ИНФОРМАТИКЕ
                      С УКАЗАНИЯМИ И РЕШЕНИЯМИ

     Составители сборника  последних несколько лет тренировали сбор-
ную команду школьников Беларуси по информатике. Задачи, представлен-
ные в этом сборнике, давались на школьникам на подготовительных сбо-
рах, отборочных турах,  олимпиадах,  и достаточно  полно  охватывают
возможную тематику олимпиадных задач.  Задачи снабжены комментариями
и указаниями,  зачастую -- полными решениями и программами или прог-
раммными фрагментами. В качестве примеров мы включили несколько пол-
ных программ, написанных школьниками на сборах.
     Мы руководствовались при описании задач следующим принципом:
     Главное, чтобы решение было понятным, а как оно будет описано -
на Паскале,  алгоритмическом языке,  словесно,  или как-то еще -- не
важно.  Насколько нам удалось воплотить его в этой  книге  -  судить
Вам.  Большая  часть  фрагментов программ написана на языке Паскаль,
так как он является одновременно мощным,  ясным и  структурированным
языком программирования.  Мы надеемся,  что даже люди, не знакомые с
Паскалем,  смогут понять зти фрагменты,  используя  знания  Бейсика,
английского языка,  а также комментарии практически у каждого опера-
тора.
     Для небольшой части задач мы не даем ни решений,  ни  указаний.
Эти задачи либо решаются аналогично приведенным ранее в этой главе и
теми же самыми методами, либо являются исследовательскими задачами и
рассчитаны на самостоятельный поиск эффективного решения.
     Почти все задачи даны без указания авторов -- при распростране-
нии  задач информация об авторе почему-то почти всегда пропадает,  и
некоторые из приведенных в книге проблем стали программистским фолк-
лером.  Отсутствие  ссылки ни в коем случае не означает претензию на
авторство с нашей стороны.
     Мы признательны  людям,  чьи  задачи  и/или  решения задач мы
включили  в сборник. Это А.Калейс, Ю.Мокану, В.Прохоров, П.Панков,
В.Завадский, К.Хвенкин, И.Сорока, С.Гафуров, В.Белый, Д.Медведев и
А.Гавpилов.
     Кое-где в  тексте  встречается понятие "Сложность алгоритма".
Если для решения задачи необходимо  проделать  порядка,  например,
N*N операций,  то обычно в этом случае говорится, что предложенный
алгоритм имеет сложность О(N*N).  Когда мы говорим о сложности ал-
горитма, то мы рассматриваем только зависимость роста числа требу-
емых операций от числа N,  игнорируя все константные  множители  и
медленно растущие слагаемые.
     Мы попытались для нескольких задач дать ряд  отличающихся  по
эффективности,  очевидности  и подходам способов решения.  Поэтому
обратите внимание на решения, например, следующих задач:
     Геометрия #16
     Поиск #15
     Рекуррентные #2 и #3.

     Условия задач хранятся в файлах имя.prb (problem),  а решения и
указания - в файлах имя.sol (solutions).
     В поставку входят следующие файлы:
Название
VVEDENIE INF      Введение
ARITHMET PRB      Арифметика
ARITHMET SOL
GEOMETR  PRB      Геометрия
GEOMETR  SOL
POISK    PRB      Дихотомия и поиск
POISK    SOL
RECURR   PRB      Рекуррентные соотношения и
RECURR   SOL      динамическое программирование
SORT     PRB      Сортировки и последовательности
SORT     SOL
STRUCT   PRB      Структуры данных
STRUCT   SOL
GRAPH    PRB      Графы
GRAPH    SOL
PEREBOR  PRB      Переборные задачи
PEREBOR  SOL
RAZNOE   PRB      Разное
RAZNOE   SOL
BELORUS  94       Олимпиада Белоруссии 1994 года
  20 файлов     498726 байт   226 задач

     Так как все файлы текстовые и рассчитаны на стандартный тексто-
вый редактор, то нами были приняты следующие обозначения:

   1. элемент "A итое" может писаться  несколькими способами:
     A[i], A(i), A , Ai, A_i;
                  i

   2. знаки отношений:
      <= меньше или равно,
      >= больше или равно,
      <> не равно;

   3. операция возведения в степень "a  в  степени i"
      a^i или a**i;

   4. сумма:
        n
       SUM x[i] = x[1] + x[2] + ... + x[n]
       i=1

     или

        n
       __
       \  x[i] = x[1] + x[2] + ... + x[n]
       /
       ~~
       i=1

   5. произведение:
        n
        П x[i] = x[1]*x[2]*...*x[n]
       i=1

   6. множество -- {}:
      Пример: { L(i): 0<i<n+1 } -- множество элементов L(i) таких, что
индекс i лежит в пределах от 1 до n.

   7. в заголовке некоторых программ  стоят  директивы  компиллятору:
               {$A-,B-,D-,E+,F-,I-,L-,N-,O-,R-,S-,V-}
Они отключают проверки во время выполнения и позволяют  в  несколько
раз увеличить скорость работы программы.
   8. символ '#' означает 'номер'.

     Файлы набраны в альтернативной кодовой таблице.  Если Ваш руси-
фикатор не совпадает с использованным нами,  то, возможно, на экране
будут неверно отображаться следующие символы:
     твердый знак -- ъ
     псевдографика;
     если это действительно так, то сделайте контекстную замену этих
символов на соответствующие Вашему русификатору.
     Решения, приведенные в книге,  не единственные  (не  существует
единственно правильного  решения)  и  не всегда самые оптимальные --
наиболее эффективные решения обычно  используют  достаточно  сложные
структуры данных.
     Если в решении встречаются ссылки на другие задачи, то задачи
из другой главы даются с указанием названия главы,  а задачи теку-
щей главы - только своим номером.
     Так как не бывает книг без ошибок и опечаток,  то они есть и  в
нашей книге, и мы будем признательны всем тем, кто их обнаружит и со-
общит нам свои замечания и пожелания по поводу книги по адресу:
     г.Минск, пр. Скорины 4, Белгосуниверситет, Факультет прикладной
математики, кафедра САПР, Котову В.М. (pабочий тел. 207914, дом.тел.
726953).
     Только лицам, официально купившим этот сборник, гарантируется
консультация.
     Мы просили бы не копировать пиратские версии сборника.

     Успехов!
       До встречи на олимпиадах!

                             КСТАТИ!
     По новому положению об олимпиаде задачи всех уровней олимпиад
распространяются через Республиканскую заочную физ.-мат.-хим. шко-
лу, тел. (8-0172) 399172.

     Литература, использованная при подготовке сборника:
     Брудно А.Л., Каплан Л.И. Московские олимпиады по програм-
мированию. М. Наука. 1990.
     Задачи ленинградских олимпиад по информатике  и  вычисли-
тельной технике. Л. Ленинградский механический институт. 1988.
     Вирт Н. Алгоритмы + структуры данных = программы. М. Мир.
1985.
     Рейнгольд Э.,  Нивергельт Ю.,  Део Н. Комбинаторные алго-
ритмы. Теория и практика. М. Мир. 1980.
     Ахо А.,  Хопкрофт Дж., Ульман Дж. Построение и анализ вы-
числительных алгоритмов. М. Мир. 1979.
     Кристофидес Н. Теория графов. Алгоритмический подход.
     Арсак Ж.  Программирование игр и головоломок.  М.  Наука.
1990
     Бейда А.А.  Королев С.А. Игровые задачи и ЭВМ. Минск. На-
родная асвета. 1991.
     Бентли Д.  Жемчужины творчества программистов. М. Радио и
связь. 1990.
     Препарата Ф.,  Шеймос М. Вычислительная геометрия. Введе-
ние. М. Мир. 1989.
     Роджерс Д.  Алгоритмические  основы машинной графики.  М.
Мир. 1989.
     Липский В. Комбинаторика для программистов. М. Мир. 1988.
     а также  материалы  журнальных  статей и материалы разных
олимпиад.
