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

(1,1,1,1,1)
(2,1,1,1)
(2,2,1)
(3,1,1)
(3,2)
(4,1)
(5)

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.

Input

The 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.

Output

For 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".

Sample Input

3
1 1
5 4
5 8

Sample Output

(1)
(3,1,1)
Too big

All Submissions
Best Solutions


Point Value: 20
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 18, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

zzh8829 on Nov 19, 2013 - 3:51:06 am UTC Suggestion about best solutions
  • (3/2)
I submitted a wrong solution, it passed official data but not all possible cases.
After I fix my solution, it can pass all cases now. Unfortunately new one takes longer time (obviously xD).
So what happened is my wrong solution is in the best solution tab and apparently it shouldn't be there.
My suggestion is let user choose which one is the best. This will avoids above situation and benefits user who want to improve their passed solutions by reading the real best solutions.

btw: src/136689 is wrong, can you pls delete it...