vikalp14's blog

By vikalp14, history, 4 years ago, In English

Problem_link

Given a big amount N and the array of denominations S. Assuming infinite supply of each of S = {S1,S2….Sm} denominations, find the number of ways to make change for N cents.

Input Format: First line contains an integer T denoting the total number of test cases. For every test case, there are three lines. First line will contain an integer 'M' denoting the size of array. The second line contains M space-separated integers A1, A2, …, Am denoting the elements of the array. The third line contains an integer 'N' denoting the cents.

Constraints: 1 <= T <= 10 1 <= n <= 100 1 <= S[i] <= 1000 1 <= N <= 1000000 Output Format: Print number of possible ways to make change for N cents in a new line. Since answers can be large, print answer % (1000000000 + 7).

Sample Input: 2 3 1 2 3 4 4 2 5 3 6 10 Sample Output: 4 5 Explanation: For N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

I am getting WA for t-1 test cases ,though I think the code is fine ?!


#include<bits/stdc++.h> using namespace std; #define ll long long ll dp[1000006]; int main() { ll t; cin>>t; while(t--) { ll n; cin>>n; int v[100]; for(int i=0 ; i<n ; i++) cin>>v[i]; ll s; cin>>s; for(int i=0;i<=s;i++) dp[i]=0; dp[0]=1; for(int i=0 ;i<n ;i++) { for(int j=v[i];j<=s;j++) { dp[j] = (dp[j]%1000000007 + dp[j-v[i]]%1000000007) % 1000000007; } } cout<<(dp[s])<<"\n"; } }

Fixed modulo T0 and T1 are AC But getting run time error for the rest T-2 test cases

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

dp[j] += dp[j-v[i]] -> dp[j] = (dp[j] + dp[j - v[i]]) % MOD.

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I thick some thing wrong here but can't get it