### 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, (*a*_{1},*a*_{2},...,*a*_{n}) and
(*b*_{1},*b*_{2},...,*b*_{m}),
we will say that
(*a*_{1},*a*_{2},...,*a*_{n}) >
(*b*_{1},*b*_{2},...,*b*_{m})
if, for the smallest positive integer *t* such that *t* ≤ *n*, *t* ≤ *m* and *a _{t} *≠

*b*, we have

_{t}*a*

_{t}>

*b*

_{t}.

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 *a*^{th} 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*a*

^{th}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)

zzh8829on Nov 19, 2013 - 3:51:06 am UTC Suggestion about best solutionsAfter 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...