Задача A. Факториал ≡

Условие

Для заданного натурального числа N выведите значение N!

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3

6

Задача B. Фибоначчи_rec ≡

Условие

Необходимо вывести N первых чисел Фибоначчи, начиная с 0.

Формат входного файла

Входной файл содержит одно целое неотрицательное число N.

Формат выходного файла

Выходной файл должен содержать N первых чисел последовательности Фибоначчи.

Ограничения

Unbalanced TeX0 ≤ N ≤ 10

Примеры тестов

2

0 1

Задача C. Восстановление сетки ≡

Условие

Турнир по олимпийской системе, состоящий из N раундов, проводятся между 2^N участниками по следующей схеме: сначала составляется последовательность из расставленных в произвольном порядке игроков. В первом раунде первый в последовательности участник соревнуется со вторым, третий с четвёртым, и т.д. Проигравшие выбывают из турнира, и на втором раунде победитель первой пары играет с победителем второй, победитель третьей с победителем четвёртой, и т.д. Наконец, после N-го раунда остаётся ровно один участник, который становится победителем турнира.

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

Назовём упорядоченной такую первоначальную последовательность участников, что в каждом матче сетки победителем оказывается первый участник. Например, первоначальная последовательность в приведённой справа сетке не соответствует этому условию — чтобы это исправить, нужно расположить участников в порядке: Life, MarineKing, TaeJa, Leenock, Mvp, Symbol, Rain, Hero.

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

Рекомендуется рассмотреть частичные решения

N ≤ 10;

Формат входного файла

Входной файла содержит целое число N, за которым следуют 2^N − 1 пар чисел W_i L_i, означающих, что участник с номером W_i победил участника с номером L_i. Участники пронумерованы от 1 до 2^N.

Формат выходного файла

Выходной файл должен содержать 2^N целых чисел — номера участников, перечисленные в соответствии с упорядоченной первоначальной расстановкой.

Ограничения

1 ≤ N ≤ 20

Примеры тестов

3
1 2  3 1  7 3
7 6  6 5  7 8  3 4

7 8 6 5 3 4 1 2 

Задача D. Дерево Штерна-Броко ≡

Условие

Один из способов построения множества всех неотрицательных несократимых дробей вида m / n называется деревом Штерна-Броко.

Начнем с дробей 0/1 и 1/0, а затем будем повторять следующую операцию: вставить дробь (m + m′) / (n + n′) между двумя соседними дробями m / n и m′ / n′.

Например первый шаг дает одну новую дробь между 0/1 и 1/0: 0/1, 1/1, 1/0. Следующий шаг добавляет две дроби, получая 0/1, 1/2, 1/1, 2/1, 1/0. Весь процесс можно представить в виде бесконечного бинарного дерева (см. рисунок).

Воспользуемся символами L и R для обозначения левой и правой ветвей при продвижении от корня вниз к определенной дроби. Тогда строка символов L и R однозначно определяет местоположения дроби в дереве. Например, строка LRRL соответствует дроби 5/7.

Формат входного файла

Входной файл содержит два целых числа m n — числитель и знаменатель несократимой дроби соответственно.

Формат выходного файла

Выходной файл должен содержать строку, являющаяся представлением дроби в дереве Штерна-Броко.

Ограничения

1 ≤ N, M ≤ 10⁵; N ≠ M

Примеры тестов

5 7

LRRL

Задача E. Два компьютера ≡

Условие

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

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5 7 10 3 5 6

16

Задача F. Автомобильные номера ≡

Условие

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

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

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

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

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

Формат входного файла

Входной файл содержит одну строку, которая представляет собой корректный автомобильный номер.

Формат выходного файла

Примеры тестов

X772KX

9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX