Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Гости из гиперпространства

Автор задачи: Андрей Гайдель

Первоисточник: -

URL первоисточника: -

Задачу добавил: LGR

Успешно сдано решений: 26

    3008 год. Земляне наконец-то обнаружили во Вселенной пришельцев. Правда сразу же очень этому огорчились, ибо эти пришельцы, когда их обнаружили, уже летели на летающих тарелках в гиперпространстве в направлении Земли со скоростью, которую бедным самарским программистам даже сложно представить, в полном вооружении с явным намерением захватить родную планету людей. Этого, конечно же, допустить нельзя. Тогда военные решили запустить в гиперпространство ракету, которая должна будет взорваться в определённый момент. Или даже две ракеты... А лучше, три... В общем, чтобы действовать наверняка, они решили просчитать все возможные варианты местонахождения пришельцев в любой момент времени.
    Известно, что гиперпространство одномерно. Пришельцы движутся по нему только в одну сторону и, если так будет продолжаться, вскоре доберутся до Земли. Кроме того, гиперпространство дискретно, то есть его можно представить как последовательность отдельных точек, количество которых конечно. Количество этих точек между настоящим местонахождением пришельцев и Землёй равно N. Движение в гиперпространстве также дискретно, то есть происходит скачками с некоторой точки на одну из следующих. Известно, что никакое тело не может совершить в гиперпространстве скачок более чем на K точек вперёд. Количество точек, на которое выполнится скачок, совершенно случайно и не зависит ни от чего. В особенности, от мощности гипердвигателя. Вашей задачей будет подсчитать число способов, которыми пришельцы могут добраться до Земли.

    Входные данные
   
Файл input.txt содержит два целых числа N и K через пробел (1<=K,N<=50) - величины, описанные в условии задачи.

    Выходные данные
    Файл output.txt должен содержать единственное целое число - количество способов, которыми пришельцы могут добраться до Земли.

    Пример
   
input.txt
3 2
    output.txt
3
    Пояснение:
    Возможные длины скачков: (1,1,1), (1,2), (2,1).

Сдать задачу

Задать вопрос жюри по этой задаче