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

1994 год

Районный тур

Задачи

Задача 1. Редуктор

"У редукторов нет никакого стыда,
Их и вовсе ничто не волнует,
Им и в бок не стреляет,
и в спину не дует,
не служба у них, а мечта..."
М.Щербаков.

Дан набор шестеренок, для каждой известно количество зубьев. Их можно скреплять так, чтобы они вращались совместно на одной оси. Известно, что первая шестеренка крутится по часовой стрелке и делает P оборотов в минуту (на ее ось ничего насаживать нельзя). Требуется подобрать промежуточные шестеренки, при необходимости насаживая их на общие оси и вводя в зацепление так, чтобы последняя шестеренка крутилась также по часовой стрелке и делала Q оборотов. (Не обязательно использовать все шестеренки).

Описание входных данных:

количество шестеренок 
обороты первой шестеренки 
обороты последней шестеренки 
количество зубьев у 1-ой шестеренки 
    (она должна быть первой в искомой цепочке шестеренок) 
количество зубьев у 2-ой шестеренки 
........................ 
количество зубьев у n-ой шестеренки 
    (она должна быть последней).

На выходе должно быть:

        
фраза "решение есть" или "решения нет"

если решение есть, то

        
первая пара шестеренок 
вторая пара шестеренок 
......................... 
последняя пара шестеренок

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

Задача 2. 1994 цифра Фибоначчи

Это очень длинная и грустная история,- начала
Мышь со вздохом. Помолчав, она вдруг взвизгнула:
- Прохвост..."
Л.Кэролл. Алиса в Стране Чудес

Ряд чисел Фибоначии предстваляет собой последовательность натуральных чисел такую, что первое и второе числа равны единице, а каждое следующее равно сумме двух предыдущих:

1 1 2 3 5 8 13 21 34 ...

Числа Фибоначчи выписываются одно за другим вплотную. Определите, какой будет 1994-ая цифра в такой последовательности. (Обратите внимание, что соответствующее число Фибоначчи может оказаться весьма большим.)

Задача 3. Восстановление скобок

"Случилось так, как и думал всяк..."
Гамлет.

Случилось вот что. Некто взял правильно записанное математическое выражение со скобками и выкинул из него все, кроме скобок:

( ( ) ( ( ) ( ) ) ( ( ) ) ( ) )

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

( ( ) ( ( ) ( ) ) ( ( ) ) ( ) )
14 0 4 0 4 2 0 0

Получается ряд чисел:

14 0 4 0 0 2 0 0

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

        
последовательность целых неотрицательных чисел.