-
Notifications
You must be signed in to change notification settings - Fork 0
/
coin-sums.cpp
42 lines (37 loc) · 957 Bytes
/
coin-sums.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//https://www.hackerrank.com/contests/projecteuler/challenges/euler031/problem
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
ll dp[9][100001];
ll value[9] = {0, 1 , 2 , 5 , 10 , 20 , 50 , 100 ,200};
for(ll i = 0; i <=100000; i++)
dp[0][i] = 0;
for(ll i = 0 ; i < 9; i ++)
dp[i][0] = 1;
for(ll i = 1 ; i <=8; i++)
{
for( ll j = 1; j<= 100000; j ++)
{
if(j < value[i])
{
dp[i][j] = dp[i - 1][j] % mod;
}
else
{
dp[i][j] = (dp[i - 1][j] % mod + dp[i][j - value[i]] % mod)%mod;
}
}
}
ll t;
cin >> t;
while( t-- )
{
ll n;
cin >> n;
cout << dp[8][n] << endl;
}
return 0;
}