Задача A (Схема)
	Автор(ы): А.Суханов, И.Миронов

Количество тестов: 1
Ограничение времени: 30 секунд

На текстовом табло размером M строк на N столбцов (1< =M,N< =100) изображена схема, состоящая из одинарных и двойных ломаных линий, идущих по строкам и по столбцам табло. Линии, точки поворота ломаных и точки пересечения изображаются подходящими символами псевдографики. Пустые клетки экрана изображаются символом "." (ASCII-код 249). Ниже приведены допустимые символы псевдографики и их ASCII-коды:

рис.1

Напишите программу, которая по заданным ломаным строит изображение на табло. Исходные данные расположены в файле по следующему формату. Первая строка содержит размеры табло M и N. Каждая из следующих строк содержит описание ломаной. Ломаная задается толщиной линии (1 или 2) и последовательным перечислением координат точек излома (первая координата - номер строки, вторая - номер столбца). Файл исходных данных не содержит пустых строк.

Вывести в выходной файл изображение схемы в виде матрицы из M строк, по N символов в каждой.

Примечания:

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

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

4 9
1 1 5 4 5
2 1 2 1 8 3 8 3 2 1 2

Пример выходного файла OUTPUT.TXT для нашего примера:

	Задача B (Дырокол)
	Автор(ы): А.Суханов

Количество тестов: не более 6
Ограничение времени: 30 секунд на весь набор тестов

На горизонтальном столе лежит клетчатый лист бумаги размером 2**N на 2**N (3< =N< =500) клеток. Его складывают N-3 раза так, что за одно складывание передняя половина листа накладывается поверх задней, а затем правая половина листа накладывается поверх левой. Таким образом, на одном шаге линейные размеры листа уменьшаются в два раза, а в конце получается стопка 8 на 8 клеток. Из этой стопки при помощи дырокола удалили некоторые клетки (из всех слоев одновременно). Требуется определить на сколько частей распадется исходный лист бумаги (частью считается область, состоящая из клеток, связанных по вертикали и (или) горизонтали). Во входном файле содержится один или несколько наборов исходных данных. Каждый набор - это N и матрица 8 на 8 нулей и единиц (0 - оставляем клетку, 1 - удаляем). Все числа в исходном файле (в том числе и элементы матрицы) разделяются пробелами и (или) символами перевода строки. Для каждого набора исходных данных вывести в выходной файл с новой строки искомое количество кусков. Исходные данные корректны, и их проверка не требуется.

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

4
0 1 0 0 0 0 1 0
1 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0

Пример выходного файла OUTPUT.TXT для нашего примера:

11

	Задача C (Иванушка и Царевна)
	Автор(ы): А.Суханов

Количество тестов: не более 5
Ограничение времени: 60 секунд на весь набор тестов

рис.3

Царевна привязана к высокому столбу, расположенному в центре большого болота (точка с координатами (0, 0)), и громко плачет. Злой Кощей обвязал Царевну веревкой I (1< I< 6) раз (по часовой стрелке). Конец этой достаточно длинной веревки попал в руки к Иванушке, который, собирается освободить Царевну и взять ее в жены. Для этого ему требуется, держа в руках веревку, обойти вокруг Царевны ровно I раз (против часовой стрелки) и вернуться в исходную точку. Болото глубокое и непроходимое, поэтому Иванушка может перемещаться по нему, только прыгая с одной кочки на другую. В результате такого прыжка за ноги Иванушке зацепляется определенное (заданное для каждой пары кочек) количество зелёных водорослей. Напишите программу, которая находит такой путь спасения Царевны, при котором за ноги Иванушке зацепляется минимальное суммарное количество зелёных водорослей.

Во входном файле содержится один или несколько наборов исходных данных. Каждый набор - это

1. Количество кочек N (3<N<10).
2. Количество оборотов I.
3. Координаты кочек - N пар вещественных чисел (X1,Y1), ... (XN, YN).
4. Матрица A размером N на N, элемент матрицы с координатами (строка i, столбец j) содержит количество зелёных водорослей, которое зацепляется за ноги Иванушке, когда он прыгает с кочки i на кочку j; диагональные элементы матрицы нулевые и 0<A[i,j]<10000.
5. Номер начальной кочки S, на которой стоит Иванушка.

Наборы исходных данных и все числа во входном файле разделяются пробелами и (или) символами перевода строки. Кочки занумерованы натуральными числами от 1 до N. Вывод программы: Для каждого набора исходных данных вывести в выходной файл с новой строки минимальное суммарное количество зеленых водорослей и путь Иванушки, заданный последовательным перечислением номеров кочек, по которым он прыгает (путь должен начинаться и заканчиваться номером начальной кочки S).

Примечяния:

Чтобы не повредить Царевну, Иванушка не должен допускать, чтобы Царевна была замотана более 10 раз (как по, так и против часовой стрелки). Ни один отрезок, соединяющий кочки, не проходит через центр болота. В болоте ничего, кроме низкостелющихся зелёных водорослей не растет, поэтому Иванушка может не беспокоиться, что веревка начнет на что-либо наматываться и запутываться. Кочки расположены таким образом, что искомый путь всегда будет существовать. Исходные данные корректны, и их проверка не требуется.

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

7 1
-14.5 3 17 21 0 30 15 -23 -2 -12 -33.1 -5 -7 17
0 2 10 13 9 7 15
9 0 9 31 1 9 1
9 9 0 13 9 1 9
9 9 1 0 9 9 9
9 1 9 1 0 9 9
9 9 9 9 1 0 9
1 9 7 9 9 9 0
1

Пример выходного файла OUTPUT.TXT для нашего примера (см. изображение пути на рис.3):

10 1 2 5 4 3 6 5 2 7 1

	Задача D (Длинное равенство)
	Автор(ы): И.Миронов

Количество тестов: не более 10
Ограничение времени: 60 секунд на весь набор тестов

Рассматриваются арифметические выражения без скобок, содержащие целые числа (неограниченной длины) и знаки операций: + (плюс), - (минус) и * (умножить). Требуется проверить равенство вида A=B, где A и B - выражения, построенные по описанным выше правилам.

Файл исходных данных содержит одно или несколько равенств, разделенных символом ";" (точка с запятой). Для каждого такого равенства вывести в выходной файл с новой строки результат сравнения: "верно" или "неверно". Файл исходных данных может содержать пробелы и (или) символы перевода строки. Программа должна игнорировать эти символы, как незначимые (разрываться могут даже числа). Длина файла исходных данных не превосходит 40 Кбайт. Исходные данные корректны и их проверка не требуется.

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

21-4*2 = -4 *-3; 23233542512352143524
12 - 232335425123521435242*10+  8 =0

Пример выходного файла OUTPUT.TXT для нашего примера:

неверно
верно