Guests from the Hiperspace
Автор задачи: Андрей Гайдель
Первоисточник: -
URL первоисточника: -
Задачу добавил: LGR
Успешно сдано решений: 26
The 3008-th year. People at last have found out in the universe of the newcomers. The truth at once very much to this were afflicted, for these newcomers, when them have found out, already flied on UFOs in hiperspace in a direction of the Earth with speed, which is difficul) to the poor Samara programmers even for presenting, in complete arms with obvious intention to grasp a native planet of the people. It is impossible to admit it, certainly. Then the militarians have decided to launch in hiperspace a rocket, which should blow up at the certain moment. Or even two rockets... And three are better... Work for certain, they have decided to count all possible variants of a site of the newcomers at any moment of time.
It is known, that hiperspace is 1D. The newcomers moves on it only in one party, and, if so will proceed, soon arraive up to the Earth. Besides hiperspace discretely, i.e. it which quantity certainly is possible to present as a sequence of separate points. The quantity of these points between the present site of the newcomers and Ground is equal N. The movement in the hiperspace also discretely, i.e. occurs by jumps from some point on one of the following. It is known, that any body can not make in hiperspace movement more than on K of points forward. Quantity of points, on which will be executed movement, completely casually and does not depend on anything. In particular, from capacity hiperengine. By your task will count up number of ways, with which the newcomers can reach the Earth.The entrance data
The file input.txt contains two integers N and K through a blank.
The target data
The file output.txt should contain a sole integer - quantity of ways, with which the newcomers can reach the Earth.
Example
input.txt
3 2
output.txt
3
The explanatory:
Possible lengths of jumps: (1,1,1), (1,2), (2,1).