11517 - Exact Change

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

double_zero
New poster
Posts: 8
Joined: Sat Jun 28, 2014 12:42 pm

Re: 11517 - Exact Change

Post by double_zero » Sun Dec 14, 2014 9:27 pm

i Keep Getting WA, But My Code Work's Fine With Every Test Case That's in here and udebug random input.
Could anyone help me by giving a testcase that breaks my Code? or tell me whats Wrong With My Code?

Code: Select all

#include <iostream>
#include <math.h>
#include <algorithm>
#include <fstream>
#include <functional>
#define int8 long long
#define p pair<int, int>
#define cost first
#define cnt second
//#define cin fin
//#define cout fout
#define INF (int)1e9

 using namespace std;

int t,n, a[110];
p d[10010][110];

p Min(p& a, p& b){
	if(a.cost<b.cost)
		return a;
	else if( a.cost==b.cost && a.cnt<b.cnt )
		return a;
	return b;
}

p solve(int m, int i, int coins){
	if(m>=t) return p(m,coins);
	if(i<0) return p(INF,INF);
	if(d[m][coins].cost!=-1) return d[m][coins];
	
	p a1=solve(m+a[i],i-1,coins+1),a2=solve(m,i-1,coins);
	p ans=Min(a1,a2);
	
	return d[m][coins]=ans;
}

 int main(){
 	//ifstream fin("in.txt");
	//ofstream fout("out.txt");
 	int tc; cin >> tc;
	while(tc--){
		for(int i=0 ; i<10010 ; i++)
			for(int j=0 ; j<110 ; j++)
				d[i][j].cost=-1;
		cin >> t >> n;
		for(int i=0 ; i<n ; i++) cin >> a[i];
		p ans=solve(0,n-1,0);
		cout << ans.cost << " " << ans.cnt << endl;
	}
 	return 0;
 }


brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11517 - Exact Change

Post by brianfry713 » Tue Dec 16, 2014 1:31 am

Input:

Code: Select all

1
8366
50
8079
3292
8007
9881
7512
3939
4569
8436
9913
1773
6034
3988
762
5415
2610
1289
8358
9291
7223
4553
9531
8257
2162
4507
7471
1728
9532
3511
5482
7897
8660
3560
7540
3018
3440
1404
6957
8008
9839
6869
6133
2224
7208
3246
3990
9817
4534
2348
5459
1757
AC output:

Code: Select all

8366 4
Check input and AC output for thousands of problems on uDebug!

nafeeur_kuet
New poster
Posts: 6
Joined: Sat Dec 20, 2014 5:19 am

Re: 11517 - Exact Change

Post by nafeeur_kuet » Sat May 16, 2015 8:41 pm

Getting WA!!
I am getting confused about this test case:
1
12
5
1
2
2
2
5
uDebug output:
12 5
But by the means of question it should be
12 3
12=5+5+2
Because in question "---you would like to minimizethe number of coins or bills that you pay out."

oja
New poster
Posts: 11
Joined: Fri Apr 24, 2015 5:34 pm

Re: 11517 - Exact Change

Post by oja » Sun May 17, 2015 11:56 pm

This is not the usual coin change problem where the number of each coin/bill is unlimited. The number of each coin/bill is the number of times it
appears in the input. You are allowed to use the bills/coins as many times as they appear in the input. In the input you've given, there's only one 5
so you can use 5 just once.

Post Reply

Return to “Volume 115 (11500-11599)”