Задана белая доска размером NxN клеток, выкрашенных в белый и черный цвета. За один ход можно перекрасить все клетки одной строки или одного столбца в противоположный цвет. Напишите программу, которая вводит число N (2<=N<=50), начальную раскраску доски NxN и определяет последовательность ходов, с помощью которых получается белая доска, или сообщает, что такой последовательности не существует. Раскраска доски задается таблицей NxN нулей и единиц, где 0 - белая клетка, 1 - черная.

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

строка 1
столбец 4
столбец 1
строка 4

На плоскости расположена система из N одинаковых шестеренок, которая приводится в движение вращением шестеренки ╧ 1 по часовой стрелке. Сцепленные шестеренки могут вращаться только в разных направлениях.

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

Исходные данные программы: количество шестеренок N (1<=N<=100) и набор пар (i,j), которые определяют номера сцепленных шестеренок.

Например, для системы шестеренок, изображенной на рис.2, исходными данными будут число 5 и пары (1,2), (2,3), (4,5), (2,4), (3,5) Вывод программы может быть следующим:

шестеренка 1: по часовой стрелке
шестеренка 2: против часовой стрелки
шестеренка 3: по часовой стрелке
шестеренка 4: по часовой стрелке
шестеренка 5: против часовой стрелки

Задана электрическая схема из резисторов (сопротивлений). Схема является параллельно-последовательной (П.-П. схема), т.е. содержит только последовательные и параллельные соединения резисторов. Формально, понятие П.-П. схемы можно представить следующими правилами:

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

1. в случае А сопротивление схемы равно сопротивлению единственного входящего в нее резистора;

2. в случае Б сопротивление схемы равно сумме сопротивлений последовательно соединенных схем;

3. в случае В сопротивление схемы вычисляется по формуле: R=1/(1/R1+...+1/Rn), где R1, ..., Rn - сопротивления параллельно соединенных схем.

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

Например, для схемы, заданной строкой (16:(22-42)) искомое сопротивление будет равно 12.8.

Городской теоретический тур (2-ой тур)

Исходные данные - натуральное число N. Составьте программу, которая вычисляет количество различных лесенок, состоящих ровно из N одинаковых кубиков. Здесь лесенка Ц это набор из ступенек, размер которых уменьшается снизу вверх. Лесенка содержит по крайней мере две ступеньки, ступенька состоит по крайней мере из одного кубика. На рисунке приведен пример такой лесенки для N=11, а для N=5 таких лесенок две.

Рассматриваются цепочки из нулей и единиц одинаковой (большой) длины. Над ними можно выполнять следующие операции:

NOT - все нули заменяются единицами, а единицы Ц нулями (у этой операции один аргумент);

AND - операция с двумя аргументами: числа, стоящие в одинаковых местах, умножаются, и полученное число записывается в то же место результата;

OR - операция с двумя аргументами: числа, стоящие в одинаковых местах, сравниваются, и наибольшее из них записывается в то же место результата. Таким образом, OR (a, b) = NOT ( AND ( NOT (a), NOT (b) ) ).

Напишите программу, которая вводит натуральное число N (Nг1995), четыре цепочки a, b, c и d длины N и определяет:

(1) можно ли последовательным применением перечисленных операций получить d из a, b и c;

(2) при утвердительном ответе строит нужную последовательность операций (достаточно одной последовательности).

Пример 1. Для N=6, a=011000, b=111010, c=010001 и d=100010, вывод программы может быть следующим:

(1) Да

(2) AND(NOT(a),OR(b,a))

Пример 2. Для N=6, a=011000, b=111010, c=010001 и d=000010, ответ на пункт (1) отрицательный.

Яблоня называется двоичной, если в каждой точке ветвления ствол или ветвь разветвляется надвое. Точки ветвления, корень и концы веток Ц это узлы дерева. Известна масса каждого участка яблони между двумя соседними узлами. Первоначально в яблоне N узлов, а нужно оставить M. Яблоню можно резать в основаниях ветвей, при этом ветвь и вся часть дерева, растущая выше, удаляются.

Исходные данные: N, M (1<M<N<=100) и список из N-1 тройки. Каждая тройка содержит номера узлов, определяющих участок и его массу (узлы перенумерованы от 1 до N).

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

Например, для исходных данных: N=8, M=3 и набора троек (1, 2, 19), (2, 4, 13), (3, 2, 12), (3, 8, 17), (3, 6, 11), (5,8,10) и (8,7,8), вывод программы может быть следующим:

Обрезать ветки: (2,4),(3,8),(3,6).

Городской практический тур (3-ый тур)

Оценка задачи: 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 баллов). Исходные данные корректны и их проверка не требуется.

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

Оценка задачи: 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.

Ограничение времени: 1 минута на каждый тест.