#K5896. Unique Gold Coin Distribution
Unique Gold Coin Distribution
Unique Gold Coin Distribution
You are given two integers: T representing the total number of gold coins and P representing the number of pirates. Your task is to find all possible ways to distribute the coins among the pirates subject to the following rules:
- Each pirate must receive at least one coin.
- All pirates receive a unique number of coins, i.e. no two pirates get the same number.
- The sum of coins received by all pirates must equal T.
In mathematical terms, if the coin counts are \(a_1, a_2, \dots, a_P\) with \(a_1 < a_2 < \dots < a_P\), then they must satisfy:
\(a_1 + a_2 + \dots + a_P = T\) and \(a_i \ge 1\) for all i.
If there is no valid distribution, output a single line with []
.
inputFormat
The input consists of a single line containing two space-separated integers T and P where:
- T (1 ≤ T ≤ 109) is the total number of gold coins.
- P (0 ≤ P ≤ 20) is the number of pirates.
Note: If P is 0, there is no valid distribution.
outputFormat
If a valid distribution exists, output each valid distribution on a separate line. For a distribution, print the coin amounts allocated to each pirate in increasing order separated by a single space. If more than one valid distribution exists, you may output them in any order.
If there is no valid distribution, output a single line containing []
.
10 4
1 2 3 4
</p>