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

1994 год

Теоретический тур

Задачи

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

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

Примеры

входные данныевывод программы
((??)?        
((()))
(()())                
)?         
восстановить невозможно         

Задача B. Кубики

Даны несколько разверток кубиков с гранями, пронумерованными от 1 до 6 (наподобие игральной кости). Определить, какие из них соответствуют одним и тем же кубикам.

Исходные данные программы: число разверток R (R ≤ 10) и сами эти развертки. Развертка кубика задается перечислением номеров его граней в порядке: левая, правая, верхняя, передняя, нижняя и задняя грани.

На выходе должно быть количество различных кубиков M и для каждого кубика - номера соответствующих разверток.

Пример

входные данныевывод программы
3
1 2 6 4 5 3
4 6 1 5 3 2
4 1 3 6 2 5
Число различных кубиков - 2
Развертки кубика N 1: 1 2
Развертки кубика N 2: 3

Задача С. Игра "Ну, погоди!"

Правила известной компьютерной игры "Ну, погоди!" следующие. В замкнутом лабиринте 10×10 клеток ставятся фишки Волка и Зайца. За Волка играет первый игрок, за Зайца - второй. Игроки делают ходы по очереди, передвигая фишку на одну из свободных соседних клеток (по горизонтали или по вертикали). Первым ходит Волк. Продолжительнсть игры ограничена K ходами для каждого игрока. Первый игрок выигрывает, если ему удастся поставить Волка на соседнюю с Зайцем клетку. Иначе выигрывает второй игрок.

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

Исходные данные программы: координаты фишек Волка и Зайца в любой удобной для Вас системе координат, продолжительность игры K и лабиринт, заданный матрицей 10×10 нулей и единиц: 0 - свободная клетка, 1 - занятая.

Примечания