166 - Making Change

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

Post by oulongbin »

hi ,i am so confused.can someone tell why i always got WA??

Code: Select all

#include <iostream>
using namespace std;
#include <cstring> 
#include <cstdio>
#include <cmath> 
//#include <fstream>
//ifstream fin("in.txt");
//#define cin fin


int shop[501];
int min;
int money;
int numOfCoin[7];
int num;

void init()
{
	int i,j;
	int cnt;
	memset(shop,0,sizeof(shop));
	for(i=500;i>=5;i-=5)
	{
		j=i;
		cnt=0;
		if(j>=200)
		{
			cnt+=j/200;
			j%=200;
		}
		if(j>=100)
		{
			cnt+=j/100;
			j%=100;
		}
		if(j>=50)
		{
			cnt+=j/50;
			j%=50;
		}
		if(j>=20)
		{
			cnt+=j/20;
			j%=20;
		}
		if(j>=10)
		{
			cnt+=j/10;
			j%=10;
		}
		if(j>=5)
		{
			cnt+=j/5;
			j%=5;
		}
		shop[i]=cnt;
	}
}

void backtrack(int type,int cnt,int sum)
{
	if(sum>=money)
	{
		if(num+shop[sum-money]<min)
			min=num+shop[sum-money];
		return ;
	}
	if(type>6)
		return;
	if(cnt<numOfCoin[type])
	{
		switch(type)
		{
		case 1:sum+=5;break;
		case 2:sum+=10;break;
		case 3:sum+=20;break;
		case 4:sum+=50;break;
		case 5:sum+=100;break;
		case 6:sum+=200;break;
		}
		num++;
		backtrack(type,cnt+1,sum);
		switch(type)
		{
		case 1:sum-=5;break;
		case 2:sum-=10;break;
		case 3:sum-=20;break;
		case 4:sum-=50;break;
		case 5:sum-=100;break;
		case 6:sum-=200;break;
		}
		num--;
		backtrack(type+1,0,sum);
	}
	else
	{
		backtrack(type+1,0,sum);
	}
}

int main()
{
	int i,j;
	double temp;
	init();
	while(1)
	{
		j=0;
		for(i=1;i<7;i++)
		{
			cin>>numOfCoin[i];
			j+=numOfCoin[i];
		}
		if(j==0)
			break;
		cin>>temp;
		money=int(temp*1000)/10;
		min=99999999;
		num=0;
		backtrack(1,0,0);
		printf("%3d\n",min);
	}
	return 0;
}
in this sample:
0 5 1 0 1 9 1.55

my program output : 4
but i see someone output :3

which one is right??
thanks!

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish »

the correct ans is 4 of course..but u fail a lot of cases pasted above
if u can think of it .. u can do it in software.

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

Post by oulongbin »

hi , jagadish. my program output the same answer pasted above, which one is wrong ?? :D

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish »

just pointing out a couple of of them..

0 0 0 1 1 2 4.05
0 1 0 0 0 1 1.65

my output :
6
4

yours:
3
1
if u can think of it .. u can do it in software.

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

Post by oulongbin »

hi,jagadish.thank you very much.i finally get AC.
it is the problem of precision.
i run the program well in VC,but wrong in gcc. :D

El-idioto
New poster
Posts: 45
Joined: Mon Jul 14, 2003 9:42 pm
Location: Zoetermeer, The Netherlands

Post by El-idioto »

@Krzysztof Duleba

Your program is wrong.

The answer for entry 125 in your list is wrong:

0 5 1 0 1 9 1.55

Correct answer is 4, but your app gives 3.

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Re: I need some I/O for 166(making change), plz help

Post by Krzysztof Duleba »

Indeed.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: I need some I/O for 166(making change), plz help

Post by mak(cse_DU) »

Thanks to Krzysztof Duleba.
For his input and output....
I count $20.00 as a maximum and got AC.
Mak
Help me PLZ!!

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: I need some I/O for 166(making change), plz help

Post by Obaida »

i got accepted taking 10$ as maximum. :D
try_try_try_try_&&&_try@try.com
This may be the address of success.

Ahmad
New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

Re: I need some I/O for 166(making change), plz help

Post by Ahmad »

According to my Acc prog the Ans is

Code: Select all

  4
  5
  2
  3
  4
  3
  5
  4
  4
  3
  1
  2
  2
  1
  3
  3
  4
  4
  7
  4
  4
  1
  3
  3
  2
  1
  5
  2
  4
  2
  5
  3
  2
  6
  4
  9
  3
  3
  3
  2
  3
  3
  1
  2
  2
  3
  4
  3
  3
  3
  1
  1
  4
  6
  2
  3
  3
  3
  3
  2
  4
  4
  3
  3
  4
  2
  2
  4
  4
  2
  2
  3
  2
  3
  4
  4
  5
  1
  4
  2
  5
  5
  4
  2
  3
  3
  4
  5
  4
  4
  3
  4
  4
  2
  3
  2
  3
  4
  4
  2
  3
  4
  6
  5
  4
  3
  2
  2
  5
  3
  1
  2
  3
  3
  3
  5
  3
  2
  4
  2
  4
  3
  3
  1
  4
  3
  3
  4
  2
  3
  5
  3
  3
  5
  1
  3
  3
  3
  3
  1
  2
  2
  2
  4
  5
  4
  4
  3
  2
  3
  2
  2
  4
  2
  3
  2
  3
  4
  3
  6
  3
  2
  4
  3
  3
  4
  5
  4
  5
  3
  5
  6
  3
  4
  2
  5
  2
  3
  6
  2
  3
  1
  3
  3
  3
  3
  2
  4
  3
  3
  4
  1
  2
  2
  5
  2
  1
  3
  3
  4
Good Luck :D

@li_kuet
New poster
Posts: 44
Joined: Fri May 25, 2012 6:22 pm
Location: Chittagong, Bangladesh

Re: I need some I/O for 166(making change), plz help

Post by @li_kuet »

Try this case :

Code: Select all

2 2 2 2 2 1 4.05
0 0 0 0 0 0
Correct answer is 4

kaban
New poster
Posts: 1
Joined: Fri Jan 10, 2014 3:49 am

explain 166 dp problem - what is asked

Post by kaban »

Thus if we need to pay 55c, and we do not hold a 50c coin, we could pay this as 2*20c + 10c + 5c to make a total of 4 coins. If we tender $1 we will receive 45c in change which also involves 4 coins, but if we tender $1.05 ($1 + 5c), we get 50c change and the total number of coins that changes hands is only 3.
I m not asking for solution , I don't get what example is saying:

so, we need to pay 55c , coins = {5,10,20} , 55c = 2*2 + 1*10 + 1*5 - 4 coins.

But what is next ? "if we tender 1$ we will receive 45c? what does it mean ? 1 - 45 = 55 ?

and the last is 1.05?

can someone give a bit more detail? i dont' understand the question

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: explain 166 dp problem - what is asked

Post by brianfry713 »

For the first sample input the bill is .95, you pay $1 and get back .05, so 2 total coins change hands.
For the second sample input the bill is .55, you pay $1 and .05 and get back .50, so 3 total coins change hands.

There are many ways to pay the bill and receive change, the goal of this problem is to minimize the sum of the number of coins you pay plus coins received.

Also check out
http://online-judge.uva.es/board/viewtopic.php?t=6026
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

Re: explain 166 dp problem - what is asked

Post by jddantes »

Why is mine RE?

Code: Select all

#include <stdio.h>

int val[] = {5,10,20,50,100,200};
int coins[101] ={};
int main()
{
    coins[1] = 1;
    int i;
    for(i=2; i<101; i++)
    {
        coins[i] = 1000000;

        int num = i*5;
        int j;
        for(j=0; val[j] <= num; j++)
        {
            if(coins[(num - val[j])/5] + 1 < coins[i])
            {
                coins[i] = coins[(num-val[j])/5] + 1;
            }
        }
    }
    /*
    for(i=1; i<100; i++)
    {
        printf("%d coins to make %d\n",coins[i],i*5);
    }
    */
    while(1)
    {
        int hand[6] ={};
        int total = 0;
        for(i=0; i<6; i++)
        {
            scanf("%d",&hand[i]);
            total+=hand[i]*val[i];
        }

        if(hand[0] == 0 && hand[1] == 0 && hand[2] == 0 && hand[3] == 0 && hand[4] == 0 && hand[5] == 0)
            return 0;

        float ff;
        scanf("%f",&ff);
        ff *= 100;
        int num = (float)ff;
        //printf("Num is %d\n",num);
        //Get min ans:
        //For each amount you can make greater than or eqaul to num, let's call this pay
        //cp = min coins you have for pay
        //ans = cp + coins[pay-num]
        int pay_arr[total/5+1];
        for(i=num/5; i<total/5 +1; i++)
        {
            if(i*5 < num)
                pay_arr[i] = 0;
            else
            {
                pay_arr[i] = 1000000;
            }
        }

        int a,b,c,d,e,f;
        for(a=0; a<=hand[0]; a++)
        {
            for(b=0; b<=hand[1]; b++)
            {
                for(c=0; c<=hand[2]; c++)
                {
                    for(d=0; d<=hand[3]; d++)
                    {
                        for(e=0; e<=hand[4]; e++)
                        {
                            for(f=0; f<=hand[5]; f++)
                            {

                                int pay = a*val[0] + b*val[1] + c*val[2] + d*val[3] + e*val[4] + f*val[5];

                                if(pay<num)
                                    continue;

                                int num_coins = a + b + c + d + e + f;
                                //printf("I can make %d using %d coins\n",pay,num_coins);
                                if(num_coins < pay_arr[pay/5])
                                {
                                    pay_arr[pay/5] = num_coins;
                                    //printf("OPTIMAL I can make %d using %d coins\n",pay,pay_arr[pay/5]);
                                }
                            }
                        }
                    }
                }
            }
        }
        /*
        for(i=num/5; i<total/5 +1; i++)
        {
            if(pay_arr[i] < 1000000)
            {
                printf("I can make %d using %d coins\n",i*5,pay_arr[i]);
            }
        }
        */
        int min_ans = 1000000;
        for(i=num/5; i<total/5 + 1; i++)
        {
            if(pay_arr[i]==1000000)
                continue;
            int ans = pay_arr[i] + coins[(i*5-num)/5];
            //printf("I pay %d (%d coins) get %d change (%d coins) for a total of %d coins used\n",i*5,pay_arr[i],i*5-num,coins[(i*5-num)/5],pay_arr[i]+coins[(i*5-num)/5]);
            if(ans<min_ans)
                min_ans = ans;
        }
        printf("%3d\n",min_ans);
    }
    return 0;

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: explain 166 dp problem - what is asked

Post by brianfry713 »

On the sample input, line 15 of your code:
for(j=0; val[j] <= num; j++)
Is throwing a seg fault as j increases past the end of the val array.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”