Муниципальный этап всероссийской олимпиады школьников по информатике

Регион

Ханты-Мансийский автономный округ – Югра

Учебный год

2011-2012

Параллель

9-11 классы

Разработчик

Алексеев А.В., к.п.н., доцент

 

A. Баланс скобок

(Время: 1 сек. Память: 16 Мб)

Дана последовательность, состоящая из открывающихся и закрывающихся круглых, квадратных и фигурных скобок.

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

Входные данные

Входной файл input.txt состоит из хотя бы одной и не более 10 строк. В каждой строке записана одна последовательность скобок. Длина последовательности не более 255.

Выходные данные

В единственную строку выходного файла output.txt нужно вывести символы 0 или 1. Их общее количество равно количеству введённых строк. Для каждой строки выводится 0, если из неё может получиться правильное скобочное выражение, и 1, иначе.

Пример

input.txt

output.txt

1

([{}])

([{

01

 

B. Три грибника

(Время: 1 сек. Память: 16 Мб)

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

Известно, что все вместе они собрали N грибов. Сколько грибов было у каждого из них перед привалом?

Входные данные

В единственной строке входного файла input.txt записано одно натуральное число N (≤ 30000).

Выходные данные

В единственную строку выходного файла output.txt нужно вывести три числа через пробел - первоначальное количество грибов у Пети, Васи и Коли соответственно. Предполагается, что ответ для данного N существует.

Пример

input.txt

output.txt

1

120

65 20 35

 

C. Бессмыслица

(Время: 1 сек. Память: 16 Мб)

Никифор утверждал, что бессмыслица, повторенная много раз, становится истиной. Для доказательства этого он применил следующую процедуру: переставил на клавиатуре своего компьютера клавиши в произвольном порядке и набрал некоторый текст. Получилась, естественно, бессмыслица. Он и эту бессмыслицу набрал на том же компьютере с той же подправленной клавиатурой. Новую бессмыслицу Никифор набрал еще раз и так далее – времени-то у него много.

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

Входные данные

В единственной строке входного файла input.txt записано одно целое число N (1 < N < 60) – количество клавиш на клавиатуре компьютера Никифора.

Выходные данные

В единственную строку выходного файла output.txt нужно вывести одно целое число – максимальное количество шагов проделанной Никифором процедуры.

Пример

input.txt

output.txt

1

4

4

2

5

6

 

D. Ленточка - 2

(Время: 1 сек. Память: 16 Мб)

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

- на первом шаге ее согнули пополам так, что верхняя половина легла на нижнюю либо спереди (P - сгибание) либо сзади (Z - сгибание),

- на последующих n-1 шагах выполнили аналогичное действие с получающейся на предыдущем шаге согнутой ленточкой, как с единым целым.

Затем ленточку развернули, приведя ее в исходное состояние. На ней остались сгибы - ребра от перегибов, причем некоторые из ребер оказались направленными выпуклостью к нам (K - ребра), а некоторые - от нас (O - ребра). Ребра пронумеровали сверху вниз числами от 1 до 2n-1.

Требуется написать программу, которая по заданной строке символов из прописных букв "O" и "K", где нахождение на i-ом месте символа "O" или "K" определяет тип ребра на расправленной полоске, находит строку из прописных "P" и "Z", определяющих последовательность типов сгибаний, посредством которых получена ленточка с этой последовательностью ребер.

Входные данные

В первой строке входного файла input.txt записано число n – количество сгибаний (n не более 20), во второй строке - строка из 2n-1 символов "O" или "K", определяющих типы ребер на расправленной ленточке.

Выходные данные

В единственную строку выходного файла output.txt нужно вывести строку из n символов "P" и "Z", задающую последовательность сгибаний. Если такой последовательности сгибаний не существует, то вывести в файл "NO".

Примеры

input.txt

output.txt

1

2

OOK

PZ

2

2

OOO

NO