Задача #1. Фишка на поле

Имя входного файла input.txt Имя выходного файла output.txt Максимальное время работы на одном тесте 2 секунды

Рассмотрим прямолинейное поле длины N, в первой клетке которого стоит игровая фишка. За один ход мы можем переместить ее на не более чем K клеток вперед. Требуется подсчитать количество различных способов прохода фишкой поля от позиции 1 до позиции N. Формат входных данных Входной файл содержит два числа целых -- N (2<=N<=30) и K (0<=K<=30). Формат выходных данных Выходной файл должен содержать искомое количество путей. Пример входного файла Пример выходного файла 4 2 3

Задача #2. Двойные единицы

Имя входного файла input.txt Имя выходного файла output.txt Максимальное время работы на одном тесте 2 секунды

Среди всех N-битных двоичных чисел найти количество таких, у которых в двоичной записи нет подряд идущих k единиц. Формат входных данных Входной файл содержит два числа целых -- N (2<=N<=30) и K (0<=K<=30). Формат выходных данных Выходной файл должен содержать одно число -- ответ на задачу. Пример входного файла Пример выходного файла 4 2 8

Задача #3. Файловая система

Имя входного файла input.txt Имя выходного файла output.txt Максимальное время работы на одном тесте 2 секунды

В файловой системе настенного персонального компьютера ВС-1 (Висячая Система) файлы организованы в каталоги. В компьютере нет понятия устройства, и поэтому полное имя файла является строкой, состоящей из имен каталогов и имени файла, разделенных символом "\", причем "\" не может быть ни первым, ни последним символом, а также встречаться два раза подряд. Имя файла (каталога) может быть произвольной длины, но длина полного имени файла не может быть длиннее N символов. В качестве символов, допустимых к употреблению в именах файлов (каталогов), могут использоваться символы из алфавита, состоящего из K букв (символ "\" не входит в их число). Для данных N и K определить максимальное число файлов, которое можно записать на данный компьютер. Формат входных данных Входной файл содержит два целых числа -- N (1<=N<=10) и K (1<=K<=5) Формат выходных данных Ваходной файл должен содержать одно число -- ответ на задачу. Пример входного файла Пример выходного файла 3 2 18