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

1995 год

Районный тур

Задачи

Задача A. Раскраска

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

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

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

Задача B. Шестеренки

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

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

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

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

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

Задача C. Сопротивление

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

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

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

Исходные данные программы - изображение схемы, записанное по определенным правилам в виде строки символов. В случае А изображением схемы является десятичная запись величины сопротивления. В случае Б - строка (A1-A2-...-An), где A1,...,An - изображения последовательно соединенных схем. В случае В - строка (A1:A2:...:An), где A1,...,An - изображения параллельно соединенных схем.

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

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