Internet Problem Solving Contest

IPSC 2017

Problem D – Dazzling digits

Numbers with repeated digits are boring. Look at them: 44 is boring, 474 is boring, 1 000 000 is sooooo boring it hurts.

Numbers without repeated digits aren’t boring at all. As you read such a number, you will always encounter something new! Look: 52 107 is pretty, and 9 087 432 156 is among the most pleasant numbers one can read.

Problem specification

You are given a positive integer n.

Write n in the form a1 + ⋯ + ak. Each of the ai must be a positive integer. The values ai must not be boring. Their count (i.e., the number k) must be as small as possible.

The values ai don’t have to be distinct. The same digit may appear in multiple ai.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line with a single positive integer n.

In the easy subproblem D1 we have t = 1000 and 1 ≤ n ≤ 10 000.

In the hard subproblem D2 we have t = 30 000 and 1 ≤ n ≤ 2 000 000 000.

Output specification

For each test case, output a single line of the form “k a1ak”.

If there are multiple optimal solutions, you may output any of them.








1 123
2 90 9
2 20469135 978654321