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

Рис.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 баллов

Дан автобусный билет с номером, состоящим из 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. Предполагается, что все вводимые данные корректны

РАЗБАЛЛОВКА

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

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

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

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

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

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

ТРЕБУЕТСЯ

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

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

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

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

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

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