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
Two numbers in a line, U and n.
- U is the inclusive upper bound, is always larger than 0, and less than 20.
- n is the total number of unknowns, which is less than 20.
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 with this equation.
Hint: the implementation
#include<stdio.h>
#define MAX_UNKNOWN 20
int solution[MAX_UNKNOWN] = {0};
int upper;
void show(int stop){
printf("%d", solution[0]);
for(int i = 1; i < stop; i++)
printf(" %d", solution[i]);
printf("\n");
}
void count(int max, int sum, int n_unknown, int stop){
int i, j;
if(n_unknown == stop){
show(stop);
return;
}
// for all possible values, recursively call count()
for(i = 0; i <= max; i++){
// implement this part
}
}
int main(){
int n;
scanf("%d %d", &upper, &n);
count(upper, 0, 0, n);
}