Algorithm
Problem link- https://www.spoj.com/problems/UOFTAE/
UOFTAE - Foxling Feeding Frenzy
You've come across N (1≤N≤200) adorable little Foxlings, and they're hungry! Luckily, you happen to have M (1≤M≤200) crackers on hand, and everyone knows that Foxen love crackers! You'd like to distribute all of your crackers, without splitting any of them, among the Foxlings - but you have to be careful. Foxling i must be fed at least Ai crackers, or it will remain hungry, but no more than Bi of them, or it will become hyper (1≤Ai≤Bi≤200). You certainly don't want any hungry or hyper Foxlings on your hands, and you're curious as to how many ways this can be accomplished.
There are T (1≤T≤100) scenarios as described above. For each one, you'd like to determine the number of different distributions of your crackers that would satisfy all of the Foxlings, modulo 109+7 (as this value can be quite large).
Input
First line: 1 integer, T
For each scenario:
First line: 2 integers, N and M
Next N lines: 2 integers, Ai and Bi, for i=1..N
Output
For each scenario:
Line 1: 1 integer, the number of valid cracker distributions modulo 109+7
Example
Input: 2
2 5
1 4
2 6
3 5
2 2
2 9
2 3 Output: 3
0
Explanation of Sample
In the first scenario, you can give either 1, 2, or 3 crackers to the first Foxling, and the remaining 4, 3, or 2 (respectively) to the second.
In the second scenario, each Foxling must receive at least 2 crackers, while you only have 5 to give out, so you have no valid options.
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 = 2e2+5;
int n, m;
int A[MAXN], B[MAXN];
int dp[MAXN][MAXN];
ll solve(int idx, int left){
if(left < 0) return 0;
if(idx == 0){
if(left >= A[0] && left <= B[0]) return 1LL;
else return 0LL;
}
if(dp[idx][left] != -1)
return dp[idx][left];
ll res = 0;
for(int i = A[idx]; i <= B[idx]; i++){
res += solve(idx - 1, left - i);
res %= MOD;
}
return dp[idx][left] = res;
}
int main(){
io;
int t;
cin >> t;
while(t--){
memset(dp, -1, sizeof dp);
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> A[i] >> B[i];
cout << solve(n-1, m) << endl;
}
return 0;
}Input
2 5
1 4
2 6
3 5
2 2
2 9
2 3
Output
0
Demonstration
SPOJ Solution-Foxling Feeding Frenzy-Solution in C, C++, Java, Python