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

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

11517 - Exact Change

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

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

Re: WA-11517

Post by sreejond » Thu Jun 04, 2009 1:33 pm

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

Post by saiful_sust » 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

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

Re: WA-11517

Post by sreejond » 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.

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

Re: WA-11517

Post by saiful_sust » 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??????????????????????????????????????

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

Re: WA-11517

Post by sreejond » 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.

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

Re: WA-11517

Post by sohel » 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

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

Re: WA-11517

Post by sreejond » 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.

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

Re: WA-11517

Post by saiful_sust » 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

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

Re: WA-11517

Post by sreejond » 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)

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

Re: WA-11517

Post by saiful_sust » 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

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

Re: 11517 - Exact Change

Post by sreejond » Wed Jun 10, 2009 9:05 pm

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

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

Re: 11517 - Exact Change

Post by liauys » 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!

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

Re: 11517 - Exact Change

Post by Imti » 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

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

Re: 11517 - Exact Change

Post by sir sbu » 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;
}

Post Reply

Return to “Volume 115 (11500-11599)”