# UVa 10910

## Summary

A Dynamic Programming counting problem. Solve the problem by counting it with its subproblems. This is an implicit solution. There is also another explicit solution which gives a direct formula.

## Explanation

${\displaystyle F(N,T,P)}$ can be defined recursively
${\displaystyle F(N,T,P)=\Sigma _{i=p}^{T-(N*P)+P}{F(N-1,T-i,P)}}$ and ${\displaystyle F(0,0,P)=1}$ which basically just states that the number of ways we can have N objects that sum up to T and up to minimum P is just the summation of the number of ways that having the number i as the current number, and the subproblem of N-1 objects that sums up to T-i, still with a minimum P.

Alternate Solution
First, for getting a pass mark in all the N subjects, put 'P' for all the subjects. Now, the number of ways for the rest of the marks to be distributed in 'N' subjects is the number of integrals solutions of ${\displaystyle \sum _{i=1}^{N}X_{i}=T-(N*P)}$. So, finally the answer reduces to ${\displaystyle {}^{T-(N*P)+N-1}\!C_{N-1}}$

## Optimizations

Memoization is fine, and this problem can be solved bottom-up.

## Input

3
3 34 10
3 34 10
7 50 2


## Output

15
15
5245786