III Всероссийская олимпиада школьников по информатике

Красноярск, 1991 год

Задачи

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

Задача 1. Черный ящик

На вход "черного ящика" подается любая таблица, содержащая символы латинского алфавита. На выходе получается 3 строки результата. Например:

а) б)

Опишите алгоритм, по которому мог бы работать этот "черный ящик".

Задача 2. Караван

Географическая карта местности задана квадратной сеткой определенного масштаба. В узлах сетки известна высота над уровнем моря. Между соседними узлами высота меняется плавно. Караван перемещается только по линиям сетки. (Перемещение по диагонали запрещается). Путь между двумя соседними точками с углом наклона больше 45 градусов считается непроходимым.

Провести караван из точки А(X1, Y1) в точку В(X2, Y2) по пути с наименьшим перепадом высоты или сообщить об отсутствии решения.

Примечание: Перепадом высот на маршруте называется разность высот между самой высокой и самой низкой точками маршрута.

Задача 3. Царевна

В одной из клеток поля n × n (n > 1) Кощей Бессмертный спрятал Марью Царевну, создав еще неизвестное число m (1 < m < n × n) ее двойников в различных свободных клетках. И царевна, и ее двойники одинаково надежно укрыты и невидимы.

Отправившийся на поиски царевны Иванушка-дурачок попросил у благоволящей к нему щуки датчик биосигналов. Известно, что и Марья Царевна и ее двойники испускают незатухающие направленные биолучи, распространяющиеся параллельно сторонам и диагоналям поля.

Иванушка-дурачок также знает, что интенсивность биолуча Марьи Царевны в m раз выше интенсивности биолучей двойников. Иванушка может установить свой датчик в любую клетку поля и получить величину суммарной интенсивности биолучей, приходящих в клетку.

Помогите Иванушке определить местонахождение настоящей царевны.

Задача 4. Часы

Фирма "Школьник" предлагает разработать для электронных часов младших школьников режимы работы и трехкнопочную систему управления ими.

Опишите режимы работы часов, содержание отображаемой информации в каждом из режимов, функции кнопок.

Не забудьте, что это часы для младших школьников. Они должны быть просты в управлении. На них нецелесообразно иметь большое количество режимов работы.

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

Задача 5. Удав

Прямоугольная область задана своими координатами: (X1,Y1) - левая верхняя вершина и (X2,Y2) - правая нижняя вершина. По границе области ползет удав длины L со скоростью V. Внутри области движется точка со скоростью V1. Точка начинает движение вниз от границы области на заданном расстоянии S от ее верхнего левого угла и под углом A к нижней линии области. Точка движется, отражаясь от стенок до тех пор, пока не столкнется с удавом. Объекты начинают движение одновременно.

Составить программу, вычисляющую количество отражений точки от границ области и время до столкновения с удавом. Если при стократном отражении точка не столкнулась с удавом, программа прекращает работу, сообщив об этом событии.

Задача 6. Полоска

Расположенную вертикально прямоугольную бумажную ленточку с закрепленным нижним концом стали складывать следующим образом:

Затем ленточку развернули , приведя ее в исходное состояние. На ней остались сгибы - ребра от перегибов, причем некоторые из ребер оказались направленными выпуклостью к нам (К - ребра), а некоторые - от нас (О - ребра). Ребра пронумеровали сверху вниз числами от 1 до 2n-1.

  1. Составить программу, запрашивающую:
  2. Составить программу, запрашивающую строку символов из прописных букв "О" и "К", где нахождение на i-том месте символа "О" или "К" определяет тип ребра на расправленной полоске, и выдающую строку из прописных "П" и "З", определяющих последовательность типов сгибаний, посредством которых получена ленточка с исходной последовательностью ребер. Если такой строки не существует, сообщить об этом.