Expression Evaluation Error
Contest: Codeforces Round 742 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, greedy, implementation, math

On the board, Bob wrote $$$n$$$ positive integers in base $$$10$$$ with sum $$$s$$$ (i. e. in decimal numeral system). Alice sees the board, but accidentally interprets the numbers on the board as base-$$$11$$$ integers and adds them up (in base $$$11$$$).

What numbers should Bob write on the board, so Alice's sum is as large as possible?

Input format:
The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains two integers $$$s$$$ and $$$n$$$ ($$$1 \leq s \leq 10^9$$$; $$$1 \leq n \leq \min(100, s)$$$) — the sum and amount of numbers on the board, respectively. Numbers $$$s$$$ and $$$n$$$ are given in decimal notation (base $$$10$$$).

Output format:
For each test case, output $$$n$$$ positive integers — the numbers Bob should write on the board, so Alice's sum is as large as possible. If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$70_{10} + 27_{10} = 97_{10}$$$, and Alice's sum is $$$$$$70_{11} + 27_{11} = 97_{11} = 9 \cdot 11 + 7 = 106_{10}.$$$$$$ (Here $$$x_b$$$ represents the number $$$x$$$ in base $$$b$$$.) It can be shown that it is impossible for Alice to get a larger sum than $$$106_{10}$$$.

In the second test case, Bob can only write a single number on the board, so he must write $$$17$$$.

In the third test case, $$$3_{10} + 4_{10} + 100_{10} + 4_{10} = 111_{10}$$$, and Alice's sum is $$$$$$3_{11} + 4_{11} + 100_{11} + 4_{11} = 110_{11} = 1 \cdot 11^2 + 1 \cdot 11 = 132_{10}.$$$$$$ It can be shown that it is impossible for Alice to get a larger sum than $$$132_{10}$$$.

Example input:
6
97 2
17 1
111 4
100 2
10 9
999999 3

Example output:
70 27 
17 
3 4 100 4
10 90
1 1 2 1 1 1 1 1 1 
999900 90 9

Editorial:
Let's greedily construct the largest possible sum for Alice, digit by digit. That is, the leftmost position should have the largest value possible, then the second-leftmost position, and so on.
The maximum value of the leftmost digit of Alice's sum is clearly equal to the leftmost digit of the number $$$s$$$, since it cannot be larger. Similarly, the maximum possible value for the second-leftmost digit in Alice's sum cannot be larger than the corresponding digit in $$$s$$$, and so on. In general, Alice's sum cannot be larger than the number $$$s$$$ when interpreted as a base-11 number.
So how can we maintain the sum of $$$s$$$ when we express it as a sum of $$$n$$$ numbers? The idea is to split $$$s$$$ into a sum of powers of $$$10$$$. For example, if $$$s=25$$$, and Bob writes down $$$[10, 10, 1, 1, 1, 1, 1]$$$. Then Alice will not have any carries, and so the answer will just be $$$s$$$ interpreted as a base-11 number.
But what if we need to write down more numbers than the sum of the digits of $$$s$$$? Then, we're forced to split a power ten into units. When we split a power of $$$10$$$, it can be seen that we should split the smallest power of $$$10$$$ that isn't $$$1$$$ (call it $$$10^k$$$) as $$$10^{k-1}$$$ and $$$9 \cdot 10^{k-1}$$$. We can check all powers of $$$10$$$, and it can be shown that this is the best way to split.
For example, if $$$s=21$$$ and $$$n=4$$$, then we do the following process: $$$[21]$$$ to $$$[20, 1]$$$ to $$$[10, 10, 1]$$$ to $$$[10, 9, 1, 1]$$$. If $$$s=110$$$ and $$$n=3$$$, we do the following process: $$$[110]$$$ to $$$[100, 10]$$$ to $$$[100, 9, 1]$$$. Note that, in this last case, splitting $$$10=9+1$$$ is better than splitting $$$100=90+10$$$, since the sum of $$$100_{11} + 9_{11} + 1_{11} = 10A_{11}$$$, and $$$90_{11} + 10_{11} + 1_{11} = A1_{11}$$$.
Time complexity: $$$\mathcal{O}(n^2 \log_{10}(s))$$$ if you lazily iterate over all currently split numbers, or $$$\mathcal{O}(n \log{n} \log_{10}(s))$$$ if you use a priority queue.