Page 1 of 3

### 11517 - Exact Change

Posted: Tue Jun 02, 2009 10:16 pm
Please help me.
I got WA again and again.
I cant find my bug.
Here is my code.
Can anybody check it.

Code: Select all

``````#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXI(a,b) (a>b?a:b)

long W[110],Val[110],C[110][10010],coin[110][10010],MAX,kase,M,N;

int cmp(const void *a,const void *b)
{
int *p=(int *)a;
int *q=(int *)b;
return (*p-*q);
}

void  MCarry()
{
MAX=100000;
int i, j,check;
for(i = 1; i<=N; i++)
for(j = W[1]; j<=10000; j++)
{
if(W[i] > j)
{
C[i][j] = C[i-1][j];
coin[i][j]=coin[i-1][j];
}
else
{
check = MAXI(C[i-1][j], C[i-1][j - W[i]] + Val[i]);
if(check==j && (C[i-1][j] <= (C[i-1][j - W[i]] + Val[i]) ) )
{
C[i][j] = MAXI(C[i-1][j], C[i-1][j - W[i]] + Val[i]);
coin[i][j]+=(coin[i-1][j-W[i]]+1);
}
if(check==j && (C[i-1][j] > (C[i-1][j - W[i]] + Val[i]) ) )
{
C[i][j] = MAXI(C[i-1][j], C[i-1][j - W[i]] + Val[i]);
coin[i][j]+=coin[i-1][j];
}
if(j > MAX)	break;
if(j > M && C[i][j]!=0 && MAX > j)
MAX=j;
}
}
}

int main()
{
//	freopen("h.txt","r",stdin);

long i;
scanf("%ld",&kase);

while(kase--)
{
memset(coin,0,sizeof(coin));
memset(C,0,sizeof(C));
scanf("%ld",&M);
scanf("%ld",&N);
for(i=1;i<=N;i++)
{
scanf("%ld",&W[i]);
Val[i]=W[i];
}

qsort((void *)W, N+1, sizeof(W[0]), cmp);

for(i=1;i<=N;i++)
Val[i]=W[i];

MCarry();
if(C[N][M])
{
printf("%ld %ld\n",C[N][M],coin[N][M]);
}
else
{
printf("%ld %ld\n",C[N][MAX],coin[N][MAX]);
}
}
return 0;
}``````

### Re: WA-11517

Posted: Thu Jun 04, 2009 1:33 pm
Is nobody here to help me????

### 11517_Exact Change

Posted: Thu Jun 04, 2009 11:20 pm
Hi I donot check ur code but ur code fail in some test case

try this cases:
INPUT:

Code: Select all

``````5
12 5
1 2 2 2 5
4 4
2 1 1 1
20 4
4 4 5 10
1 2
1 1
2 1
3
``````
OUTPUT:

Code: Select all

``````12 5
4 3
23 4
1 1
3 1
``````
• IMPOSSIBLE MEANS I M POSSIBLE

### Re: WA-11517

Posted: Fri Jun 05, 2009 7:31 pm
Thank you saiful_sust for your response.
But my code give correct result for your case.
But i still get WA.
I cant found where is my bug.
Can you(anyone) please check my code.

Thanks in advance.

### Re: WA-11517

Posted: Fri Jun 05, 2009 9:29 pm
PLz check ur code then post

try to take input from file

ur code donot pass
the test case (given by me)
ur code return

Code: Select all

``````12 5
4 8
20 5
1 3
3 1
``````
BUT correct is:

Code: Select all

``````12 5
4 3
23 4
1 1
3 1
``````

Is it ok??????????????????????????????????????

### Re: WA-11517

Posted: Sun Jun 07, 2009 6:50 am
It seems to me there is some problem with you.
I dont understand if my code work good in my compiler,
why it give wrong output in your compiler.
saiful my code give correct output for your case.
Before response you should look closely.

Thnx for your effort.

### Re: WA-11517

Posted: Sun Jun 07, 2009 10:48 am
@sreejond: I ran your code with the input given by saiful_sust and your code produces

Code: Select all

``````12 5
4 8
20 5
1 3
3 1``````

### Re: WA-11517

Posted: Sun Jun 07, 2009 11:43 am
Sorry saiful.
In my code posted here i cant initialize it.
Now i edited it.
Sorry friend. I do apologize for my mistake.
But it still WA.
Thnx sohel vai for your reply.

### Re: WA-11517

Posted: Sun Jun 07, 2009 8:41 pm
Another case 4 u

Code: Select all

``````1
1000 10
10 900 20 200 300 400 10 10 20 20
``````

Code: Select all

``````1100 2
``````
• IMPOSSIBLE MEANS I M POSSIBLE

### Re: WA-11517

Posted: Mon Jun 08, 2009 6:38 am
Thank you saiful.
I modified my code. Now ur case is working.
But still WA.(Above 2 weeks)

### Re: WA-11517

Posted: Wed Jun 10, 2009 11:49 am
sorry man.I m busy with my exam.
I don't see ur code.......BUT
Another case for u

Code: Select all

``````1
13 5
9 5 2 3 3
``````
OUTPUT:

Code: Select all

``````13 4
``````

### Re: 11517 - Exact Change

Posted: Wed Jun 10, 2009 9:05 pm
You r so helpful.
For your case it's working again.
But WA still behind me.
I edit my code.

### Re: 11517 - Exact Change

Posted: Sat Jul 18, 2009 4:29 pm
Hi sreejond, I don't know whether u've got AC, but this is the case where your program failed:

input:
1
10000
2
9999
9999

output:
19998 2

Hope this helps!

### Re: 11517 - Exact Change

Posted: Sat May 28, 2011 9:46 am
I modified my 0-1 knapsack code and its working well..But I'm getting TLE.Please can anyone say me how concept of coin change problem helps to solve this problem.Here is My code:

Code: Select all

``````//Cut After Acc
``````

### Re: 11517 - Exact Change

Posted: Sat Sep 22, 2012 9:08 am
hi
i don't know why my code is WR
it's my code
#include <iostream>
#include <vector>
#include <string.h>
#include <cmath>
#include <queue>
#include <map>
#include <string>
#include <algorithm>
#include <stdio.h>
using namespace std;
#define ll long long
#define vec vector

int n;
int m;
int cnt2;
bool flag;
bool flag1;
bool mark [101];
vec <int>amin;
int a[101][30001];
int f(int u,int sum)
{
if(sum >= n )
{
if(flag && cnt2 == sum)
flag1=1;
return sum;
}
if(u == -1 )
{
return 10000000;
}
if(a[sum] > 0)
return a[sum];
mark =1;
int cnt=f(u-1,sum+amin);
if(flag1)
return cnt;
mark =0;
int cnt1=f(u-1,sum);
if(flag1)
return cnt1;
if(cnt < cnt1 )
{
mark =1;
}
else
{
mark =0;
cnt=cnt1;
}
return a[sum]=cnt;
}
int main ()
{
int number;
cin>>number;
while(number--)
{
cin>>n>>m;
memset(a,0,sizeof a);
memset(mark,0,sizeof mark);
for(int i=0;i<m;i++)
{
int k;
cin>>k;
amin.push_back(k);
}
flag=0;
flag1=0;
sort(amin.begin(),amin.end());
cnt2=0;
cnt2=f(m-1,0);
flag=1;
memset(a , 0,sizeof a );
memset(mark , 0,sizeof mark );
int k=f(m-1,0);
k=0;
for(int i=0;i<m;i++)
k+=mark ;
cout<<cnt2<<" "<<k<<endl;
amin.clear();
}
return 0;
}