eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Байка про лимон

Байка про лимон

У житті кожного програміста настає день, коли останній контест програно, і приходить час йти на пенсію. Навіть Три Програмісти у свій час не уникнули цієї долі. А щоб зберігти добру пам'ять про себе, Програмісти час від часу складали задачі і проводили контести. За це, звичайно, не платили, але для справжніх програмістів слава важливіша грошей. Проте придумати гарну задачу -- лише половина справи. Потрібно ще придумати для неї політкоректний текст. Вся проблема у тому, що текст до однієї з задач чергового контесту написав Третій Програміст, який взагалі не знає, що таке політкоректність. Він просто придумав історію про розведення цитрусових у домашніх умовах. В результаті слово "лимон" було використано аж \textbf{N} разів. І це притому, що перед контестом задачу буде перечитувати відомий цензор Олександр К.! Якому лимони нагадують про апельсини, а він їх терпіти не може. Цей факт дуже турбує Першого та Другого Програмістів -- вони прекрасно знають, що якщо слово "лимон" зустрінеться Олександру більше \textbf{K} разів підряд, то задачу не буде допущено до контесту. Тому Перший і Другий Програмісти тайком домовились уночі напередодні контесту проникнути на сервер і замінити деякі "лимони" на значно більш політкоректні "банани" таким чином, щоб задачу все ж таки було допущено до контесту. Скількома способами це можна зробити? \InputFile Єдиний рядок містить цілі числа \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10000}) і \textbf{K} (\textbf{0} ≤ \textbf{K} ≤ \textbf{N}). \OutputFile Вивести шукану кількість способів. \textit{\textbf{Підказка}}: Позначимо слово "лимон" літерою "\textbf{Л}", а слово "банан" -- літерою "\textbf{Б}". Тоді у прикладі задана послідовність слів "\textbf{ЛЛЛЛЛ}" може бути перетворена у наступні політкоректні послідовності: "\textbf{ЛЛБЛЛ}", "\textbf{ЛЛБЛБ}", "\textbf{ЛЛББЛ}", "\textbf{ЛЛБББ}", "\textbf{ЛБЛЛБ}", "\textbf{ЛБЛБЛ}", "\textbf{ЛБЛББ}", "\textbf{ЛББЛЛ}", "\textbf{ЛББЛБ}", "\textbf{ЛБББЛ}", "\textbf{ЛББББ}", "\textbf{БЛЛБЛ}", "\textbf{БЛЛББ}", "\textbf{БЛБЛЛ}", "\textbf{БЛБЛБ}", "\textbf{БЛББЛ}", "\textbf{БЛБББ}", "\textbf{ББЛЛБ}", "\textbf{ББЛБЛ}", "\textbf{ББЛББ}", "\textbf{БББЛЛ}", "\textbf{БББЛБ}", "\textbf{ББББЛ}" та "\textbf{БББББ}".
Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
5 2
Вихідні дані #1
24
Автор М.Рибак, І.Грєбнов, Д.Ковальов