Задача I тура (автор А.А.Суханов)

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

Рис.

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

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

ПРИМЕР.

Секунда 1: 6->4

Секунда 2: 4->3

6->7

Секунда 3: 3->1

4->5

Секунда 4: 3->2

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

а) вводит описание сети, проверяет корректность этого описания и, в случае его некорректности, печатает соответствующее сообщение, заканчивая работу;

б) определяет и печатает какой-либо порядок распространения сообщения;

в) определяет и печатает порядок передачи сообщения за минимальное время (порядок распространения сообщения для сети на рис., приведенный в примере 1, является оптимальным).

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

1) N не превосходит 50, а количество каналов связи не превосходит N+5.

2) Программа должна запрашивать имя входного файла; в крайнем случае допускается ввод данных с клавиатуры.

3) Сеть задается набором из N+2 строк в следующем формате:

строка 1: число компьютеров в сети (N);

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

строка 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.

РАЗБАЛЛОВКА

1. Организация диалога с пользователем: - 5 баллов.

2. Пункт А: - 25 баллов.

3. Пункт Б: - 25 баллов.

4. Пункт В: - 30 баллов.

5. Выполнение технических требований: - 15 баллов.

Задача II тура (автор А.П.Овсянников)

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

Задача II тура (автор В.В.Прохоров)

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

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

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

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

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

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

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

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

Примечания

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

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

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

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

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

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

- удобный ввод;

- удобную диагностику ошибок с возможностью их оперативного исправления;

- композиционное и цветовое оформление выводимой на экран информации;

- наличие на экране необходимых для работы подсказок.

РАЗБАЛЛОВКА

Программа, выдающая схему:

- для произвольного оператора присваивания - 25

- только при ограничеии из Примечания 3 - 20

Диагностика ошибочного ввода - 10

Интерфейс - 5

Дополнительные баллы жюри на обе задачи - 20 баллов.

1. Перевести число, записанное в системе счисления с основанием p в число, записанное в системе счисления с основанием q. При этом 1<p<37 и 1<q<37. В системах счисления с основаниями, большими 10, для обозначения остальных цифр используются прописные буквы латинского алфавита, аналогично шестнадцатиричной системе. Так, в любой системе счисления с основанием, большим 10, цифра, обозначающая 10 кодируется символом "A", а в системе с основанием 36 использованы все 26 букв латинского алфавита, то есть цифра, соответствующая 36 обозначается буквой Z.

Числа для перевода ваша программа должна считывать из текстового файла task1.dat. Каждая строка файла состоит из десятичного числа p, обозначающего основание исходной системы счисления, пробела, числа, записанного в системе счисления с основанием p, которое необходимо перевести в другую систему, пробела и десятичного числа, обозначающего новую систему счисления.

Пример входного файла:

2 1010100 8

7 32105 20

16 1AB03 5

Программа должна выдавать на экран копию считанного файла, добавляя в конец каждой строки, после числа q, пробел и результат перевода. Предполагается, что все данные в файле корректны, а исходные числа для перевода не превосходят 2 000 000 000 (в десятичной системе).

2. Нить Ариадны. Тезею из лабиринта Минотавра помог выйти клубок ниток. Вы можете вместо клубка использовать персрнальный компьютер.

Напишите программу, которая вводит маршрут Тезея в лабиринте и находит обратный путь, по которому Тезей сможет выйти из лабиринта по своему маршруту, но без заходов в тупики и петель.

Маршрут Тезея вводится из файла task2.dat, где он представлен строкой, состоящей из букв: N, S, W, E.

Буквы означают:

N - один "шаг" на север,

S - один "шаг" на юг,

W - один "шаг" на запад,

E - один "шаг" на восток.

Например, если файл task2.dat содержит строку EENNESWSSWE то программа должна выдать обратный путь NWW.

3. Весь графический экран вашего компьютера должен представлять собой таблицу 15*15, состоящую из одинаковых прямоугольников. Каждый прямоугольник ваша программа должна заполнить случайным образом одним из 16 цветов, так чтобы в каждой строке и каждом столбце таблицы оказалось не менее 4 различных цветов.

Далее, на каждое нажатие пользователем клавиши "пробел", программа может закрасить один столбец или одну строку таблицы цветом, которым закрашены по крайней мере два прямоугольника этой строки (столбца). Назовем это одним шагом работы программы.

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

4. Билли Бонс положил в сундук некоторое количество золотых монет. На второй год он вынул из сундука сколько-то монет. Начиная с третьего года он добавлял столько монет, сколько было в сундуке два года назад. Сколько монет было в сундуке в первый и во второй года, если через X лет в сундуке оказалось ровно Y монет?

Пояснение: Если в первый год положить 5, а во второй вынуть 3 монеты, то начиная с первого года в сундуке будет 5, 2, 7, 9, 16, 25, ... монет.

Программа должна запрашивать с клавиатуры два числа X и Y на одной строке, разделенных пробелами. Пример ввода: 25 144, то есть X=25, Y=144.