IІІ обласна олімпіада учнів 8-10 класів з інформатики
		Хмельницький, 1989 рік

		Т е о р е т и ч е с к и й    т у р

     1. Дана прямоугольная доска  размером M*N клеток. Часть  клеток
доски заштрихованы. Составить  алгоритм  нахождения  кратчайшего, не
содержащего заштрихованных клеток пути из левого  верхнего в  правый
нижний угол доски. Движение осуществляется из клетки в клетку по ве-
ртикалям и горизонталям.
     2. Схема дорого между населенными пунктами  представлена  цело-
численной таблицей А[1:n, 1:m]. Элемент таблицы A[i,j]=1, если суще-
ствует дорога между i-м и j-м населенными пунктами, и  A[i,j]=O, ес-
дороги нет. Составить алгоритм, проверяющий  существует ли  хотя  бы
два населенных пункта между которыми нет пути (проходящего, быть мо-
жет, через несколько других населенных пунктов).
     3. Детям нужно определить ведущего в некоторой  игре. Для этого
они, став в круг и  определив первого, начинают  считать  с  помощью
"считалки", содержащей M слов. Тот, на ком заканчивается "считалка",
выходит из круга. После этого "считалка" повторяется, причем с  пер-
вого участника. Если после очередного круга "считалки" первый участ-
ник выбыл, то счет начинается со следующего за ним участника. Соста-
вить алгоритм, позволяющий определить порядковый помер того из N иг-
роков (N<M), который выбывает последним.
     4. Составить алгоритм, получающий на входе  число K и  выдающий
K-e по порядку четырехзначное число, у которого никакие две цифры не
равны между собой. Первым таким числом считать О123.

     1. Составить рекурсивный алгоритм вычисления наибольшего обшего
делителя двух натуральных чисел.
     2. В литерной переменой ТЕКСТ записан текст- последовательность
слов; слово - последовательность букв. Два соседних слова разделяют-
ся точкой, запятой или пробелом.
     Составить алгоритм, переписывающий  текст  в  литерную  таблицу
СТРАНИЦА[1:M] так, чтобы в каждом ее элементе - строке было не более
N символов. Перенос слов со строки на строку  не  допускается; длина
слов в тексте не  превосходит N. Число  строк, заполненных  текстом,
должно быть минимально. Точки и запятые должны  сохраниться, но  они
не должны появляться в начале новой строки.
     3. На шахматной доске M \N расставить наименьшее количество фер-
зей так, чтобы все клетки доски находились под боем ходя  бы  одного
ферзя.
     4. Дана упорядоченная по возрастанию линейная таблица натураль
ных чисел A[1]<A[2]<...<A[n]. Найти наименьшее натуральное число, не
представляемое в виде суммы некоторых чисел из данной таблицы.
     Пояснение. Сумма может состоять и из одного слагаемого, но каж
дый элемент может входить в нее не более одного раза.

                 П р а к т и ч е с к и й    т у р

                          Вариант 1

     1. На плоскости даны N различных  точек.  Среди них выбрать три
такие, чтобы треугольник, вершинами которого они  служат, имел  наи-
большую площадь.
     2. Написать программу вывода всех трехзначных десятичных чисел,
сумма цифр которых равна данному целому числу M.
     3. В игру "Щелк" играют  так: поле  M \N заполнено  фишками. Два
игрока по очереди снимают с поля фишки. Игрок при своем ходе  должен
выбрать любую неснятую фишку и снять ее вместе со всеми фишками, но-
мер строки которых больше или равен номеру строки выбранной фишки, а
номер столбца - больше или равен номеру столбца выбранной фишки. На-
пример:
       3                                                  O
строки 2             >>>      O      >>>            >>>
       1
          1 2 3 4 5
           столбцы

      >>>            >>>            >>>
                            O
    Проигрывает тот, кто снимет с поля фишку, стоящую в левом нижнем
углу (т.е. в клетке [1,1]). У кого из игроков есть выигрышная  стра-
тегия при M=2?. Разработать программу, играющую за этого игрока.

                          Вариант 2

     1. На плоскости даны координаты четырех точек. Три из них обра-
зуют треугольник. Проверить, является ли внутренней для треугольника
четвертая точка.
     2. Написать программу вывода всех трехзначных десятичных чисел,
сумма цифр которых равна данному целому числу M.
     3. Игра "Баше" (в игре участвуют двое). Соперники ходят по оче-
реди и за каждый ход любой из играющих может взять  не более M пред-
метов. Проигрывает тот, кто вынужден взять последний предмет. Соста-
вить программу, играющую за игрока с выигрышной стратегией.