2001 Canadian Computing Competition, Stage 2
Day 1, Problem 3: Partitions
Given a positive integer k, a partition is a sequence of positive integers in decreasing order whose sum is k.
For example, (12), (2,2,2,2,2,2) and (5,3,2,1,1) are all partitions of 12.
Given two distinct partitions, (a1,a2,...,an) and (b1,b2,...,bm), we will say that (a1,a2,...,an) > (b1,b2,...,bm) if, for the smallest positive integer t such that t ≤ n, t ≤ m and at ≠ bt, we have at > bt.
This ordering lets us put all the partitions of a given integer k in lexicographical order, where each partition in the ordering is greater than all the partitions before it.
For example, if k = 5, the partitions in lexicographical order are
Given k and a positive integer a, you are to find the ath partition in the list of partitions of k sorted in lexicographical order.
InputThe input will consist of a line with N, the number of test cases, followed by N lines, each of the form k a, where k and a are positive integers. k will not exceed 100, while a can be any positive 32-bit integer.
OutputFor each test case, your program should output the ath partition in the list of partitions of k, or, if a is greater than the number of partitions of k, output "Too big".
3 1 1 5 4 5 8
(1) (3,1,1) Too big
Point Value: 20
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 18, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3