Page 1 of 3

11517 - Exact Change

Posted: Tue Jun 02, 2009 10:16 pm
by sreejond
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
by sreejond
Is nobody here to help me????

11517_Exact Change

Posted: Thu Jun 04, 2009 11:20 pm
by saiful_sust
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
by sreejond
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
by saiful_sust
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
by sreejond
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
by sohel
@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
by sreejond
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
by saiful_sust
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
by sreejond
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
by saiful_sust
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
by sreejond
You r so helpful. :)
For your case it's working again. :D
But WA still behind me. :cry:
I edit my code.

Re: 11517 - Exact Change

Posted: Sat Jul 18, 2009 4:29 pm
by liauys
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
by Imti
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
by sir sbu
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;
}