Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1851
In an examination one student appeared in N subjects and has got total T marks. He has passed in
all the N subjects where minimum mark for passing in each subject is P . You have to calculate the
number of ways the student can get the marks. For example, if N = 3, T = 34 and P = 10 then the
marks in the three subject could be as follows.
Subject 1 Subject 2 Subject 3
1 14 10 10
2 13 11 10
3 13 10 11
4 12 11 11
5 12 10 12
6 11 11 12
7 11 10 13
8 10 11 13
9 10 10 14
10 11 12 11
11 10 12 12
12 12 12 10
13 10 13 11
14 11 13 10
15 10 14 10
So there are 15 solutions. So F (3, 34, 10) = 15.
Input
In the first line of the input there will be a single positive integer K followed by K lines each containing
a single test case. Each test case contains three positive integers denoting N , T and P respectively.
The values of N , T and P will be 1 ≤ N ≤ 70, 1 ≤ P ≤ T ≤ 70. You may assume that the final answer
will fit in a standard 32-bit integer.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
// dp to compute number ways to reach value j with i subjects
long long dp[101][101] = {1};
// for each subject i
for (int i = 1; i < = 100; i++){
dp[i][0] = 1;
// for each total value j
for (int j = 1; j < = 100; j++)
// we could decide to add 1 to this subject to obtain j (dp[i][j-1])
// or not add (dp[i-1][j])
dp[i][j] = dp[i - 1][j] + dp[i][j-1];
}
int n, t, p, tc;
scanf("%d", &tc);
while (tc--) {
scanf("%d %d %d",&n,&t,&p);
t -= n * p; // start score from zero after subtracting minimum needed score
printf("%lld\n", t >= 0 ? dp[n][t] : 0);
}
return 0;
}
Input
3 34 10
3 34 10
Output
15
Demonstration
UVA Online Judge solution - 10910-Marks Distribution - UVA Online Judge solution in C,C++,java