Algorithm


Problem link- https://www.spoj.com/problems/GDIL/

GDIL - Dilemma

no tags 

 

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;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
3
2 1 2 3
1 1 1 1
2 1 0 1

Output

x
+
cmd
9
4
4
Advertisements

Demonstration


SPOJ Solution-Dilemma-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python