X городская олимпиада школьников
Санкт-Петербурга по информатике

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

5 марта 1995 года

Задачи

Задача A. Плоская укладка

Максимальная оценка: 60 баллов

Имеется сеть из N (3 ≤ N ≤ 15) узлов, некоторые из которых соединены дугами. Задан замкнутый путь P, проходящий по дугам сети и содержащий каждый узел ровно один раз. Напишите программу, которая рисует на экране узлы и соединяющие их дуги так, чтобы узлы находились в вершинах правильного N-угольника, и никакие две дуги не пересекались и не проходили через вершины многоугольника. Узлы изображаются маленькими кружочками желтого цвета. Дуги изображаются кривыми, состоящими из отрезков и (или) дуг окружностей. Дуги, содержащиеся в пути P, рисуются фиолетовым цветом, а остальные - зеленым. Рисунок должен быть подходящим образом отмасштабирован.

Исходные данные расположены в текстовом файле (имя файла вводится с клавиатуры) по следующему формату: количество узлов N; количество дуг M; список из M дуг, каждая дуга задается парой номеров соединяемых узлов; замкнутый путь P, заданный списком из N+1 номеров узлов в порядке обхода (номер первого узла совпадает с номером последнего).

Пример файла исходных данных:

4 5
1 2 4 2 1 3 3 4 1 4
2 4 3 1 2

Числа в исходном файле разделяются пробелами и (или) символами перевода строки. Если сеть невозможно нарисовать требуемым образом, программа должна выдать на экран соответствующее сообщение и закончить работу. Допускается частичное решение задачи, проверяющее только возможность изображения схемы (15 баллов). Исходные данные корректны и их проверка не требуется.

Предусмотрите возможность спокойно разглядеть Ваше творение.

Задача B. Язык LIST-95

Ограничение времени: 1 минута
Максимальная оценка: 40 баллов

Лаборатория интеллектуальных систем разработала новый язык программирования с названием LIST-95. Язык предназначен для работы с длинными списками. Единственный тип в языке - это список из целых чисел, не превосходящих по модулю одного миллиарда. Константами в этом языке являются конечные арифметические прогрессии (которые задаются начальным элементом, разностью и числом элементов). Разность прогрессии может равняться нулю, тогда список будет состоять из заданного количества одинаковых чисел. Единственный оператор - это оператор присваивания, в правой части которого стоит либо прогрессия, либо бинарная операция, операндами которой могут быть только имена переменных. Допустимыми являются следующие операции:

Сцепление (конкатенация) списков. Обозначение: A#B. Результат: список, полученный приписыванием элементов списка B в конец списка A.

Сложение списков одинаковой длины. Обозначение: A+B. Результат: список, полученный поэлементным сложением элементов списков A и B.

Умножение списков одинаковой длины. Обозначение: A*B. Результат: список, полученный поэлементным умножением элементов списков A и B.

Прогрессии представляются в языке так:

<Начальное значение, Разность, Число элементов>,

а оператор присваивания так:

Переменная := Константа

или

Переменная := Переменная Операция Переменная.

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

Напишите программу, которая вводит число N (1 ≤ N ≤ 1000000000), программу на языке LIST-95 и определяет значение N-го элемента результирующего списка.

Исходные данные расположены в текстовом файле (имя файла вводится с клавиатуры) по следующему формату. Первая строка содержит число N. Со второй строки и до конца файла расположена программа на языке LIST-95. Текст программы не содержит пробелов и пустых строк. В конце последней строки программы символов перевода строки нет.

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

Пример файла исходных данных:

        
23
X:=<1,2,2000000>
A:=<2,2,2000000>
X:=X+X
A:=A#X

Для приведенного выше примера программа должна выдать, что на 23-ем стоит число 46.