## 11517 - Exact Change

Moderator: Board moderators

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### 11517 - Exact Change

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;
}
Last edited by sreejond on Wed Jun 10, 2009 9:01 pm, edited 3 times in total.

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: WA-11517

Is nobody here to help me????

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### 11517_Exact Change

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

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: WA-11517

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.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: WA-11517

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??????????????????????????????????????

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: WA-11517

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.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: WA-11517

@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

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: WA-11517

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.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: WA-11517

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

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: WA-11517

Thank you saiful.
I modified my code. Now ur case is working.
But still WA.(Above 2 weeks)

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: WA-11517

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

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: 11517 - Exact Change

For your case it's working again.
But WA still behind me.
I edit my code.

liauys
New poster
Posts: 7
Joined: Thu Jul 02, 2009 6:37 pm

### Re: 11517 - Exact Change

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!

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 11517 - Exact Change

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

sir sbu
New poster
Posts: 2
Joined: Thu Aug 02, 2012 8:08 pm

### Re: 11517 - Exact Change

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;
}