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

Троицк, 1993 год

Задачи

Задача 1. Компьютерная сеть

Компьютерная сеть состоит из связанных между собой двусторонними каналами связи N компьютеров, номера которых от 1 до N. Эта сеть предназначена для распространения сообщения от центрального компьютера всем остальным. Компьютер, получивший сообщение, владеет им и может распространять его дальше по сети. Запрещается передавать сообщение на один и тот же компьютер дважды. Время передачи сообщения по каналу связи занимает одну секунду, при этом передающий и принимающий компьютеры заняты на все время передачи данного сообщения. На рисунке приведен возможный вариант такой сети.

В начальный момент времени центральный компьютер может передавать сообщение одному из непосредственно связанных с ним компьютеров, т.е. соседу. После окончания передачи, этим сообщением будут владеть оба компьютера. Каждый из них может передать сообщение одному из своих соседей и так далее, пока все компьютеры не будут владеть сообщением.

Для сети, показанной на рисунке, возможный порядок распространения сообщения от центрального компьютера с номером 6 приведен в примере.

Пример

Секунда 1: 6->4 
Секунда 2: 4->3 
6->7 
Секунда 3: 3->1 
4->5
Секунда 4: 3->2

Задание

Написать программу, которая:

  1. вводит описание сети, проверяет корректность этого описания и, в случае его некорректности, печатает соответствующее сообщение, заканчивая работу
  2. определяет и печатает какой-либо порядок распространения сообщения;
  3. определяет и печатает порядок передачи сообщения за минимальное время (порядок распространения сообщения для сети на рисунке приведенный в примере, является оптимальным).

Технические ограничения

  1. N не превосходит 50, а количество каналов связи не превосходит N+5.
  2. Программа должна запрашивать имя входного файла; в крайнем случае допускается ввод данных с клавиатуры.
  3. Сеть задается набором из N+2 строк в следующем формате: Так, приведенная на рисунке сеть может быть представлена следующим образом: 
    7
2 3
1 3
1 4 2
6 5 3
4
7 4
6
6
  4. Вывод результатов на экран должен быть таким, как в примере.

Система оценки

  1. Организация диалога с пользователем: - 5 баллов.
  2. Пункт А: - 25 баллов.
  3. Пункт B: - 25 баллов.
  4. Пункт C: - 30 баллов.
  5. Выполнение технических требований: - 15 баллов.

Задача 2. Сто

Дан автобусный билет с номером, состоящим из N цифр. Расставить между цифрами знаки арифметических операций ('+', '-', '/', '*') и скобки таким образом, чтобы значение полученного выражение было равно 100. Можно образовывать многозначные числа из стоящих рядом цифр.

Выражение должно быть корректным с точки зрения арифметики. Допустимы лишние скобки, не нарушающие корректности выражения.

Требуется написать программу, решающую эту задачу.

Примечания

Знаки операций означают:

Используется стандантный приоритет операций, т.е. выражение 6*5/7+5-1/3 интерпретируется как ((((6*5)/7)+5)-(1/3))

Число цифр N в номере билета не больше 6.

При возникновении затруднений в решении задачи допустимо частное решение, использующее не все знаки арифметических действий и/или скобки.

Технические Требования

Программа вводит номер с клавиатуры с приглашением 

Номер:
Программа выводт полученное выражение как это показано ниже: 
0+(19+1)*5+0=100
Если для введенного номера решение найти не удается, программа должна печатать: 
123456=?

Предполагается, что все вводимые данные корректны

Система оценки

  1. Организация диалога с пользователем 2 балла
  2. Полное решение 33 балла
  3. Частные решения:
  4. Удаление из выражения лишних скобок 5 баллов

Задача 3. Трансимеджинаризатор

Существуют 2 основные формы информационных описаний - текстовая и графическая

Текстовым представлением оператора присваивания будем считать запись вида 

<Имя переменной>:=<Формула>
Здесь <Формула> состоит из целых десятичных констант, имен переменных, имен произвольных функций одного аргумента, а также знаков арифметических операций ('+', '-', '*', '/') и круглых скобок. Ограничимся случаем, когда имена функций, переменных и константы - только односимвольные.

Графическим представлением оператора присваивания будем считать схему, состоящую из элементов вида:

и соединяющих их линий. Количество "входов" у элемента равно количеству аргументов соответствующей операции или функции, <Имя> - знак арифметической операции или имя функции.

Пример

Оператору присваивания "a:=S((b+c)*(d+e))" можно сопоставить такую схему:

Требуется

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

Примечания

Считать, что схема, соответствующая вводимому оператору, при разумном выводе заведомо помещается на экран дисплея.

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

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

Технические требования

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

Интерфейс по возможности должен обеспечивать:

Система оценки