11517 - Exact Change

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

[sreejond]

Is nobody here to help me????

[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

[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.

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

[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.

[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

[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.

[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

[sreejond]

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

[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

[sreejond]

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

[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!

[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

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