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

Регион

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

Учебный год

2011-2012

Параллель

7-8 классы

Разработчик

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

 

A. Торт

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

Никифор на день рождения собирается угостить друзей тортом. Известно, что на дне рождения может быть либо M, либо N человек, включая самого именинника. На какое минимальное количество частей ему нужно разрезать торт (не обязательно всех равных), чтобы при любом из указанных количеств собравшихся, все съели торт поровну?

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

В единственной строке входного файла input.txt записаны два натуральных числа M и N через пробел (1M, N30000).

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

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

Пример

input.txt

output.txt

1

2 3

4

Пояснение

Торт нужно разрезать на части 1/3, 1/3, 1/6 и 1/6. Тогда при 2-х участниках праздника каждый съест по 1/3 + 1/6, а при 3-х каждый съест соответственно: 1/3, 1/3, 1/6 + 1/6 = 1/3.

B. Степенные числа

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

Число n называется степенным, если его можно получить из некоторого числа умножением на себя хотя бы один раз. Например, 4 степенное число, так как 4=2·2, 27 тоже степенное число, так как 27=3·3·3, а 28 не является степенным числом. Определить являются ли заданные числа степенными.

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

В первой строке входного файла input.txt записано одно натуральное число n - количество исследуемых чисел (1  n  10). Во второй строке через пробел записаны n чисел - исследуемые числа. Каждое из них больше 1 и меньше 109.

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

Выходной файл output.txt содержит n строк. В i-й строке записано “YES”, если i-е число является степенным и “NO” иначе.

Пример

input.txt

output.txt

1

2

27 28

YES

NO

C. Колокол

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

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

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

В первой строке входного файла input.txt записано число n (1 £ n £ 30000). Во второй строке записаны через пробел элементы массива, числа по абсолютной величине не большие 32767.

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

В единственную строку выходного файла output.txt нужно вывести элементы полученного массива, разделенные одним пробелом.

Пример

input.txt

output.txt

1

5

1 2 3 4 5

1 3 5 4 2

D. Ленточка

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

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

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

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

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

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

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

Входной файл input.txt содержит в первой строке число n – количество сгибаний ленточки (n не более 60), во второй строке - набор n символов из прописных латинских букв "P" и "Z". Третья строка содержит в начале число k – количество рассматриваемых рёбер (не более 10), а далее их номера (числа от 1 до 2n-1).

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

В единственную строку выходного файла output.txt нужно вывести k символов (прописные латинские буквы "K" или "O") – типы рассматриваемых ребра.

Примеры

input.txt

output.txt

1

2

PP

1 1

K

 

2

2

ZZ

2 1 2

OK