Algorithm
Problem link- https://www.spoj.com/problems/GDIL/
GDIL - Dilemma
Garfield the cat likes candies A LOT. He always keeps a huge stock of it at his home. Today John, his owner, brought home three types of candies. He brought A pieces of Red candy, B pieces of Green candy and C pieces of Blue candy. Garfield is really happy. But the problem is that John won’t allow him to eat all of it at once. He will allow him to eat at most N candies. Garfield is very confused. His love for candies is clouding his judgement and he can’t make a decision on how to choose the N candies.
Garfield is a dumb cat. So he asks you to find out in how many ways he can choose from the available type of candies so that he eats a total of N candies or less.
Note: There is no difference between candies of the same color
Input
The first line contains an integer t, the number of test cases. Each test case contains four space separated integers N, A, B, C.
Output
For each test case output a single line containing the number of ways Garfield can choose the N candies.
Constraints
0 <= t <= 100
0 <= N, A, B, C <= 5000
** No other constraints are applicable.
Sample
Input 3 2 1 2 3 1 1 1 1 2 1 0 1 Output 9 4 4
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
const int MAXN = 1e5+5;
int main(){
io;
int t;
cin >> t;
while(t--){
ll n, a, b, c;
cin >> n >> a >> b >> c;
ll res = 0;
for(int i = 0;i <= a; i++){
for(int j = 0;j <= b; j++){
ll tot = i + j;
if(tot <= n)
res += min(c, n - tot) + 1;
}
}
cout << res << endl;
}
return 0;
}Input
2 1 2 3
1 1 1 1
2 1 0 1
Output
4
4
Demonstration
SPOJ Solution-Dilemma-Solution in C, C++, Java, Python