UOFTAE - Foxling Feeding Frenzy
You've come across $N$ ($1 \leq N \leq 200$) adorable little Foxlings, and they're hungry! Luckily, you happen to have $M$ ($1 \leq M \leq 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 $A_i$ crackers, or it will remain hungry, but no more than $B_i$ of them, or it will become hyper ($1 \leq A_i \leq B_i \leq 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 \leq T \leq 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 $10^9+7$ (as this value can be quite large).
First line: 1 integer, $T$
For each scenario:
First line: 2 integers, $N$ and $M$
Next $N$ lines: 2 integers, $A_i$ and $B_i$, for $i = 1..N$
For each scenario:
Line 1: 1 integer, the number of valid cracker distributions modulo $10^9+7$
2 3 Output:
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.
Screwed up the base case. Otherwise nice DP :) Use long long.
yes a easy one but firstly took about 2 hr of time :(
Easy DP :)
First do BEHAPPY if you are stuck on this. (it will help you to figure out the recurrence then apply memoization for this problem)
AC in one go !! ...Abhinandan Agarwal _/\_.... your comments are always very helpful :p !! Keep guiding us .. :-) Well no negative crackers indeed !! :pLast edit: 2015-08-20 22:55:25
Do check for negative no. of crackers !!!
AC in one go! :D
same memoized code for BEHAPPY accepted here too..just changed to long long..as said by @Abhishek no need to worry about modulo
AC without considering modulo.. :P
no need to worry about range overflows ,the answer fits within long long int in C++ , just dont forget to