CCO '01 P3 - Partitions

View as PDF

Submit solution

Points: 12
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2001 Stage 2, Day 1, Problem 3

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.

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 Specification

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.

Output Specification

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

Comments

There are no comments at the moment.