All Tracks Algorithms Dynamic Programming 2 Dimensional Problem

You get your Christmas gift!



You pick all the gifts and Santa gives you a christmas gift.You unpack your gift wrapper and finds a a small rubber ball . This ball is particularly bouncy, which makes it great fun for throwing down a flight of stairs of your house.

On each bounce, the ball may jump over one step or it may jump over several steps. The ball never loses momentum, so each bounce must jump over at least as many steps as the previous bounce. In the illustration below, the left hand diagram shows a valid passage down eight steps, whereas the right hand diagram shows an invalid passage down eight steps. enter image description here

The path of the ball down the flight of stairs can be represented as a sequence of positive integers, with each integer representing the number of steps that are jumped over on a single bounce. Thus the left hand diagram above can be represented by the sequence 1, 2, 2, 3, and the right hand diagram above can be represented by the sequence 3, 2, 3.

Note that the final bounce must be exactly the right length to reach the bottom of the staircase. For example, for a staircase of eight steps, the sequence 3, 4, 5 is invalid since the final bounce covers more steps than are available. The sequence 3, 4, 1 is also invalid since, even though it covers the correct amount of steps, the final bounce is smaller than the bounce before it.

Some balls are in fact so bouncy that they accelerate as they make their way down the stairs. If a ball has acceleration a, each bounce must jump over at least a more steps than the previous bounce. For example, if a ball with acceleration 2 makes its way down a flight of 11 stairs, it may follow the path 1, 4, 6 but it may not follow the path 2, 3, 6. Both of these paths are illustrated below.

enter image description here

Your task is to write a program that, given the acceleration of the ball a and the length of the flight of stairs n, returns the number of valid paths the ball can take to cover the flight.

10 1

For n = 10 and a = 1, the output should be 10.

Here are all possible valid paths the ball can take:

enter image description here


[time limit] 3000ms [input] integer n

The length of the flight of stairs.

Constraints: 1 ≤ n ≤ 120.

[input] integer a

Acceleration of the ball.

Constraints: 0 ≤ a ≤ n.

[output] integer

The number of paths the ball can take to jump down the flight.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications