Mount Allison Programming Showdown 2019


2019-03-16 08:00 AKDT

Mount Allison Programming Showdown 2019


2019-03-16 13:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -552 days 17:55:39

Time elapsed


Time remaining


Problem D

The Modern Arithmetic Puzzle Society (MAPS) has developed a new arithmetic puzzle for its members. This latest puzzle is based on equinumerous numbers. A nonnegative integer $m$ is equinumerous if the canonical base-$2$ representation of $m$ has an equal number of $0$’s and $1$’s when leading zeroes are ignored. So, for example, $9=1001_2$ is equinumerous, but $6=110_2$ is not. Note that MAPS defines the number $0$ to be equinumerous, since it has no $0$’s and no $1$’s in its base-$2$ representation once leading zeroes are ignored. A puzzle consists of two positive integers $n$ and $k$. A solution to the puzzle is a sequence of $k$ equinumerous numbers that sum to $n$. Before MAPS releases its new puzzles to its members, it wants to verify that its puzzles have solutions. You have been enlisted to find a solution to each puzzle, or otherwise report that a puzzle has no solution.


The first line of input is an integer $T$, the number of puzzles in the input file, satisfying $1\leq T\leq 100$. Each of the next $T$ lines contain two space-separated integers $n$, $k$, satisfying $1\leq n\leq 10^{18}$ and $2\leq k\leq 20$, where $n$ is the target sum, and $k$ is the number of equinumerous summands to be used in a solution to the puzzle.


For each puzzle consisting of integers $n$, $k$, output one line with $k$ space-separated equinumerous integers that sum to $n$ if there is a solution to the puzzle. These integers should be in the usual base-$10$ representation. Otherwise, output the word “Impossible”. If there are multiple solutions to a puzzle, then output any one of them.

Sample Input 1 Sample Output 1
2 2
7 2
77 4
2 0
10 56 9 2