Finding the number of solutions.

Question

$$x_1+x_2+...+x_p+y_1+y_2+...+y_q \ge X$$ where $$x_1,x_2..x_p, y_1,y_2..y_q$$ are all non-negative integers, $$x_1..x_p\le a$$ $$y_1...y_q\le b?$$

The original problem is "You are given $N$ distinct boxes of marbles in total. There are $P$ boxes each containing $A$ number of marbles and remaining $Q$ boxes contains $B$ number of marbles each. Given a number $X$, you have to find total the number of ways in which you can pick at least $X$ marbles from the boxes. Print total number of ways modulo $1000000007$". or in other words how many solutions are there for the above LPP. I am completely lost here,any mathematical relations or approaches are welcome.Also guidance in efficiently coding the solution approach is also needed.Thank you!

Answer 1

Edit: not what the problem was asking. I thought it meant you had to take the whole box.

I am not sure on how to do this with mathematics, but I can help you code the solution.

Some definitions I am going to use:

• box 1 = the type of box that has A marbles
• box 2 = the type of box that has B marbles

---

1. Keep a tally for the Solution. I'll call it $S$ for solution.
2. Start with the least number of box 1's possible while having 0 box 2's
   • This is $min(ceiling(\frac{X}{A}), P)$
3. Keep a running count of how many box 1s you have currently, I'll call it $K$. K = result obtained from step 1
4. Keep a running count of how many box 2s you have currently, I'll call it $L$. L = 0
5. Increase L by one, and decrease K until K is the smallest possible.
   • To satisfy your constraints, K can be it's current value, all the way up to its max, P
   • Add $P-K+1$ to $S$
6. Repeat Step 4 until $L = Q$
7. The answer should be $S$

My Java code here:

public static void main(String[] args) {
    // input
    int P = 5, A = 7, Q = 9, B = 11, X = 100;

    int AMT1 = 0, AMT2 = 0;
    int S = 0;
    int sum = 0;
    for(int i = 0; i < P; i++) {AMT1 += A;if(AMT1 >= X) break;}
    if(AMT1 > P) {
        AMT1 = P;
        sum = AMT1*A;
        while(sum < X) {
            AMT2++;
            sum += B;
        }
    } else sum = AMT1*A;
    while(AMT2 <= Q) {
        System.out.println(AMT1);
        S += P - AMT1 + 1;
        AMT2++;
        sum += B;
        while(sum - A > X) {
            sum -= A;
            AMT1--;
        }
    }
    System.out.println(S);
}