[BOJ 6938] Partitions

View as PDF

Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 128M

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

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,\dots,a_n)$ and $(b_1,b_2,\dots,b_m)$, we will say that $(a_1,a_2,\dots,a_n) > (b_1,b_2,\dots,b_m)$ if, for the smallest positive integer $t$ such that $t \le n$ and $t \le m$, we have $a_t > b_t$.</p>

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.

입력 형식

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.

출력 형식

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.

예제 입력

3
1 1
5 4
5 8

예제 출력

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

Comments

There are no comments at the moment.