ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Timus Top Coders: Third Challenge

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

C. Басня о лимоне

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

В жизни каждого программиста наступает день, когда последний контест проигран, и приходит время уходить на пенсию. Даже Три Программиста в своё время не избежали этой участи. А чтобы сохранить добрую память о себе, Программисты время от времени составляли задачи и проводили контесты. За это, конечно, не платили, но для настоящих программистов слава важнее денег.
Однако придумать хорошую задачу – только половина дела. Нужно ещё сочинить для неё политкорректный текст.

Задача

Вся проблема в том, что текст к одной из задач очередного контеста написал Третий Программист, который вообще не знает, что такое политкорректность. Он просто сочинил историю о разведении цитрусовых в домашних условиях. В результате слово «лимон» было использовано целых N раз.
И это притом, что перед контестом задачу будет перечитывать известный цензор Александр К.! Которому лимоны напоминают об апельсинах, а он их терпеть не может. Сей факт очень беспокоит Первого и Второго Программистов – они прекрасно знают, что если слово «лимон» встретится Александру более K раз подряд, то задача не будет допущена к контесту.
Поэтому Первый и Второй Программисты тайно сговорились в ночь накануне контеста залезть на сервер и заменить некоторые «лимоны» на гораздо более политкорректные «бананы» таким образом, чтобы задача всё-таки была допущена к контесту. Сколькими способами это можно сделать?

Исходные данные

Единственная строка содержит целые числа N (1 ≤ N ≤ 10000) и K (0 ≤ KN).

Результат

Вывести искомое количество способов.

Пример

исходные данныерезультат
5 2
24

Замечания

Обозначим слово «лимон» буквой «Л», а слово «банан» – буквой «Б». Тогда в примере исходная последовательность слов «ЛЛЛЛЛ» может быть преобразована в следующие политкорректные последовательности: «ЛЛБЛЛ», «ЛЛБЛБ», «ЛЛББЛ», «ЛЛБББ», «ЛБЛЛБ», «ЛБЛБЛ», «ЛБЛББ», «ЛББЛЛ», «ЛББЛБ», «ЛБББЛ», «ЛББББ», «БЛЛБЛ», «БЛЛББ», «БЛБЛЛ», «БЛБЛБ», «БЛББЛ», «БЛБББ», «ББЛЛБ», «ББЛБЛ», «ББЛББ», «БББЛЛ», «БББЛБ», «ББББЛ» и «БББББ».
Автор задачи: Никита Рыбак, Илья Гребнов, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1513. Басня о лимоне