Problem B
Built to Scale
A factory is making widgets of weights up to $N$ using $K$ types of metal pieces with different weights. There are unlimited copies of each type of metal piece. Every widget must have a certain weight; any of the metal pieces can be used to construct each widget, as long as the total weight is correct.
The current widget maker uses an exhaustive search algorithm to determine the way to make the widget using the fewest total number of metal pieces, or report that it is impossible. Unfortunately, management thought that this was too slow and inefficient, and commissioned a new widget maker by a certain shoddy company whose name we will not mention here.
The new, cheaper widget maker uses the following algorithm:
-
Let $w$ be the required weight of the widget.
-
Take the heaviest metal piece with weight $w’ \leq w$. If no such piece exists, report failure.
-
Subtract $w’$ from $w$. If $w$ is now zero, report the number of pieces used.
-
Repeat.
You know that such a widget maker obviously does not always find the most efficient way to build the widgets (in fact, it may not even find a way at all!) You informed management of this, but they did not listen and bought the cheaper widget maker anyway.
Tomorrow, management will run stress tests to compare the new widget maker and the old one. The stress tests proceed as follows. You will bring $K$ types of metal pieces with different weights $w_1, w_2, \dots , w_ K$. Then, they will try creating each widget from weight $1$ to weight $N$, making sure that the new widget maker agrees with the old widget maker on all the possible widgets (that is, either both widget makers report failure, or both widget makers report success using the same number of pieces.)
You wish to choose the types of metal pieces such that this stress test fails. You know, however, that your manager has a fragile ego and might fire you if the new widget maker fails too quickly (they will look incompetent for buying such a shoddy piece of machinery!) Hence, you want it to fail only on the last of the $N$ tests (that is, on the widget with weight $N$).
Is it possible for you to engineer this situation to happen? If yes, which pieces should you bring?
Input
The first and only line of input contains exactly two integers, $N$ and $K$ ($1 \leq K \leq N \leq 200$), the maximum weight of the widgets and the number of types of metal pieces, respectively.
Output
If there is no set of $K$ metal pieces with distinct weights such that the stress test outlined above fails exactly on the last test, output a single line containing the string IMPOSSIBLE.
Otherwise, output a single line containing $K$ distinct integers $w_1, w_2, \dots , w_ K$ ($1 \leq w_ i \leq N$), the weights of the metal pieces in one such set.
If there are multiple correct answers, you can output any of them.
| Sample Input 1 | Sample Output 1 |
|---|---|
22 7 |
1 2 3 5 7 11 13 |
| Sample Input 2 | Sample Output 2 |
|---|---|
22 22 |
IMPOSSIBLE |
