Input File: ballin.txt
Output File: ballout.txt
Time Limit: 0.2 seconds
For your birthday you have been given a small rubber ball. This ball is particularly bouncy, which makes it great fun for throwing down a flight of stairs.
On each bounce, the ball may jump over one step or it may jump over several steps. The ball never loses momentum — 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.
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.
Given the acceleration of the ball and the length of the flight of stairs, there are many different paths that the ball can take. These paths can be written in lexicographical (dictionary) order and assigned numbers 1,2,3,.... The following table lists all possible paths that a ball with acceleration 1 can take down a flight of 10 stairs.
You must write a program that, given the acceleration of the ball and the length of the flight of stairs, can output the kth path in this list for any k.
The input will consist of a single line containing three integers separated by spaces. The first integer will be n, the length of the flight of stairs (1 <= n <= 120). The second integer will be a, the acceleration of the ball (0 <= a <= n). The third integer will be k as described above (1 <= k).
You are guaranteed that there are at least k possible paths down the flight of stairs for the given length and acceleration, and that there are at most 2,000,000,000 such possible paths.
Your output should consist of a single line describing the kth path down the flight of stairs for the given length and acceleration. The path should be written as a sequence of integers separated by spaces. In particular, there should be no commas or other punctuation in the output.
The following input data corresponds to the table of possible paths illustrated above, with the sixth path in the table being requested.
10 1 6
2 3 5
The score for each input file will be 100% if the correct sequence is written to the output file and 0% otherwise.