1. Домик

Все вы помните детскую задачу «Нарисовать домик, не отрывая карандаша от листа бумаги и не проводя одну и ту же линию дважды». Теперь ее нужно решить с помощью компьютера, правда требуется найти все возможные варианты рисования домика, начиная с левого нижнего угла. Нумерация вершин дома приведена на рисунке. Например, следующая последовательность должна быть выдана на экран 153125432.

Все варианты должны быть перечислены в порядке возрастания.

Форма представления результата (числа, вообще говоря, будут другими):

12435123

13245123

…

15123421

 

2. Шифр

Некоторый текст, состоящий из прописных русских букв, был зашифрован следующим образом: сначала из текста были удалены все пробелы и знаки препинания, затем он был переписан в таблицу размером n строк x m столбцов (n и m неизвестны) построчно, далее считан из таблицы по столбцам и затем каждая буква текста была заменена  на букву, отстоящую вправо от нее в алфавите на k позиций. При поиске заменяющей буквы в случае достижения конца алфавита переходим на начало алфавита (буквы алфавита записаны по кругу). В алфавите нет буквы Ё.

Например, исходный текст – ГАЛЯМЫЛАРАМУ,

Таблица, составленная из текста, размером 4 х 3:

ГАЛ

ЯМЫ

ЛАР

АМУ

Текст после считывания по столбцам – ГЯЛААМАМЛЫРУ.

Текст после замены букв со сдвигом на 2 – ЕБНВВОВОНЭТХ. (Буква Я при этом превращается в букву Б).

Расшифруйте следующее сообщение и пришлите в качестве ответа.

УБГЩГЩНЩЯЦЦЫЭБЮЬШЮЪЩЯЮЯЩЮЮВГУЯВВЩЩСЦАЦГНЫЖЭЯЯАЩЫЮАЯБЬЯЫЯДЯЪЩДЬЯЭУГЭРИЦФАЩБССЩХХНШЦГЬЬЦСПУТЦФСРАГЮЮЭЯЯГЯЦДЯСБТЦРБГВГЩЙЬУМ

Известно, что оно содержит слово АЛГОРИТМ.

 

3. Сочетания

Точное вычисление числа способов взять М из N предметов – достаточно сложная задача при больших значениях N и М. Даны два числа M и N: 5£ М£N£100. Вычислить точное число способов выбора М из N предметов. Данное значение можно получить по формуле , где

 

Исходные данные будут такими, что результат С будет находиться в интервале от 1 до 231.

На вход программы подаются значения N и М. Для завершения работы программы вводятся значения N и М равные 0. Для каждой пары N и М вывести число C.

Пример исходных данных

100  6
 20  5
 18  6
  0  0

Результаты для примера:

1192052400
15504
18564

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

100 94
74 7
73 66
32 16
47 9
23 11
0 0