Дистанционный практикум по программированию

Многие операционные системы при наличии одного процессора могут имитировать многозадачность, т.е. такой режим, при котором несколько вычислительных процессов выполняются одновременно. Осуществляется это за счёт последовательного выполнения частей параллельных процессов. В частности, если должны параллельно выполняться два процесса, то процессор будет исполнять каждый из них поочерёдно в течение фиксированного кванта времени, например, 10 мс. В этом случае у пользователя создаётся иллюзия параллельной работы двух процессов.

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

Пусть должны исполняться два процесса — A и B, каждый из которых требует N единиц времени для своего завершения. В первый квант времени начинает исполняться процесс A, а в последний квант времени завершается исполнение процесса B. Никакой процесс не должен ожидать продолжения своей работы более K единиц времени. При этих условиях возможны различные варианты исполнения процессов A и B, каждый из которых будет характеризоваться определённым расписанием. Например, для N = 3 и K = 3 существует 6 таких возможных расписаний:

AAABBB

AABABB

AABBAB

ABAABB

ABABAB

ABBAAB

Если же K = 2, то таких расписаний будет 5, так как расписание AAABBB станет недопустимым.

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

Формат входных данных:

В первой строке входного файла записана пара натуральных чисел, N и K (1 £ N, K £ 30), разделённых пробелом.

Формат выходных данных:

Выходной файл должен содержать единственное число — искомое число способов составления расписания работы для процессов A и B.

Пример файлов входных и выходных данных:

INPUT	OUTPUT
3 3	6
3 2	5