Zonal Informatics Olympiad 2012 problem



I have been unable to solve a problem which was given in the Zonal Informatics Olympiad 2012 paper. The problem is given below along with the link to the page where you can view the question paper and solutions.


A toy set contains blocks showing the numbers from 1 to 9. There are plenty of blocks
showing each number and blocks showing the same number are indistinguishable. We
want to examine the number of different ways of arranging the blocks in a sequence so
that the displayed numbers add up to a fixed sum.
For example, suppose the sum is 4. There are 8 different arrangements:
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
The rows are arranged in dictionary order (that is, as they would appear if they were
listed in dictionary).
In each of the cases below, you are given the desired sum S and a number K. You have
to write down the Kth line when all arrangements that add up to S are written down
as described above. For instance, if S is 4 and K is 5, the answer is 2 1 1. Remember
that S may be large, but the numbers on the blocks are only from 1 to 9.

(a) S = 9, K = 156 (b) S = 11, K = 881 © S = 14, K = 4583

I just need the logic to solve this problem.


look for the pattern… you ll get the logic then… dont give up so easily… posting this question ll get u an answer… but how ll tht answer serve you any purpose? try urself and reach to solution that way you can learn more and it ll be more rewarding and satisfying experience…


A hint: Write down all arrangements of sum = 1. Use this result to generate arrangements of sum = 2. Use both the previous results to generate arrangements of sum = 3. Go on…


A small hint


I know that… But I have given this problem over 1 and a half Hour. It has been on my mind for over 2 weeks yet I have failed. Now is the time to look at the solution and understand where I went wrong. I completed the 2013 paper in 40 minutes with all options correct and couldn’t get even 1 option right in this question.
Thanks by the way.