Задачи 5-ой Всероссийской олимпиады школьников (1993 год)


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

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

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

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

ПРИМЕР 1: 

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

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

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

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ

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

    строка 1: число компьютеров в сети (N);
    строка 2: список всех соседей компьютера 2 (представляется набором чисел, разделенных пробелами);
    строка 3: список всех соседей компьютера 2;
    ... ...
    строка N+1: список всех соседей компьютера N;
    строка N+2: номер центрального компьютера.

    Так, приведенная на рис.1 сеть может быть представлена следующим образом: 

    7
2 3
1 3
1 4 2
6 5 3
4
7 4
6
6
  4. Вывод результатов должен быть таким, как в примере 1.

РАЗБАЛЛОВКА

Организация диалога с пользователем 5 баллов
Пункт А 25 баллов
Пункт Б 25 баллов
Пункт В 30 баллов
Выполнение технических требований 15 баллов

Максимальная оценка за первый тур: 100 баллов

Задача "СТО"

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

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

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

ПРИМЕЧАНИЯ

  1. Знаки операций означают:
    '+' сложение;
    '-' вычитание (унарный минус не допускается!);
    '*' умножение;
    '/' деление нацело;
  2. Используется стандантный приоритет операций, т.е. выражение

    6*5/7+5-1/3

    интерпретируется как

    ((((6*5)/7)+5)-(1/3))

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

ТЕХНИЧЕСКИЕ ТРЕБОВАНИЯ

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

    Номер:

  2. Программа выводт полученное выражение как это показано ниже:

    0+(19+1)*5+0=100

  3. Если для введенного номера решение найти не удается, программа должна печатать:

    123456=?

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

РАЗБАЛЛОВКА

1. Организация диалога с пользователем 2 балла
2. Полное решение 33 балла
Частные решения:
- не используется '/' 28 баллов
- не используется '*', '/' 10 баллов
- не используются скобки 11 баллов
- не используется скобки и '/' 10 баллов
- не используется скобки, '*' и '/' 5 баллов
3. Удаление из выражения лишних скобок 5 баллов

Задача "ТРАНСИМЕДЖИНАРИЗАТОР"

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

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

< Имя переменной>:=< Формула>

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

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

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

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

ТРЕБУЕТСЯ

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

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

Технические требования
  1. Программа должна выдавать на экран сообщение о том, решает она задачу в общем случае или при указанных в примечании 3 ограничениях.
  2. Интерфейс по возможности должен обеспечивать:

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

РАЗБАЛЛОВКА

Программа, выдающая схему:
- для произвольного оператора присваивания 25 баллов
- только при ограничении из примечания 3 20 баллов
Диагностика ошибочного вывода 10 баллов
Интерфейс 5 баллов

Дополнительные баллы жюри за задачи второго тура: 20 баллов
Максимальная оценка за второй тур: 100 баллов