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

Регион

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

Учебный год

2007-2008

Параллель

3-й тур

Разработчик

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

 

A. Коридор

(Время - 1 сек., память - 16 Мб)

Прямоугольный коридор длиной N метров и шириной M метров решили застелить N прямоугольными плитками шириной 1 метр и длиной M метров, таким образом, чтобы не было не застеленной поверхности.

Требуется написать программу, которая найдет количество способов это сделать. Например, для коридора с размерами 6 на 4 существует четыре способа застелить плитками 1 на 4.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

В единственной строке входного файла input.txt записаны два целых числа – M (длина плитки и ширина коридора) и N (длина коридора). Для этих чисел верны неравенства 2  M  N  50.

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

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

Примеры

input.txt

output.txt

1

4 6

4

2

2 2

2

 

B. Различные цифры

(Время - 1 сек., память - 16 Мб)

Дано целое число N.

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

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

В единственной строке входного файла input.txt записано одно целое число N (1  N  109), представленное в десятичной системе счисления.

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

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

Пример

input.txt

output.txt

1

100

11 12 13 14 15 16 17 18 20 21 22 23 25 26 27 28 29 30 31 32 33 34 35 36

 

C. Слово

(Время - 1 сек., память - 16 Мб)

Числа Фибоначчи строятся следующим образом: первые два равны единице, а каждое следующее равно сумме двух предыдущих. Например, первые десять чисел Фибоначчи равны: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. В заданном тексте символы нумеруются слева направо, начиная с единицы.

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

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

В единственной строке входного файла input.txt записан текст, состоящий из латинских строчных букв. В тексте не более 30000 символов.

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

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

Примеры

input.txt

output.txt

1

a

a

2

abc

abc

3

abcdefghij

abceh