Description
An example of a multivariable linear inequality is like
where the ai's are coefficients, the xi's are unknowns, and the operation can be "less than(<)", "greater than(>)", or "greater than or equal to."
This problem ask you to list all the solutions of a specific kind of multivariable Linear Inequality, where all the unknowns are non-negative integers, all coefficients are 1, and it has constraints at both side. A mathematical representation is like:
Input
Three numbers in a line, L, U, and n.
- L is the exclusive lower bound.
- U is the inclusive upper bound, is always larger than L, and less than 20.
- n is the total number of unknowns, which is less than 20.
In other words, they are all the parameters we need to calculate the solution of the following inequality.
Output
The output should be all the solutions listed in ascending order. See the definition and example output below.
Solution
A solution is a set of non-negative numbers separated by space and ended with a newline(\n).
Ascending order
For any solution S1(x1, x2, ...) and the solution S2(y1, y2, ...) next to it,
If they share the same prefix of numbers,
then the first number not in the common prefix in S2 MUST larger than that in S1.
Otherwise,
Appendix: Properties and Facts
The total number of solutions of the multivariable integer linear inequality
is
since it is the number of combinations with repetition(重複組合).
So you can verify if the number of lines of your output, which is the number of solutions, is
because the solution set of
is the difference set of
and