Page 2 of 3
Posted: Thu Aug 18, 2005 10:52 am
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!

Posted: Thu Aug 18, 2005 4:01 pm
the correct ans is 4 of course..but u fail a lot of cases pasted above

Posted: Thu Aug 18, 2005 5:46 pm
hi , jagadish. my program output the same answer pasted above, which one is wrong ??

Posted: Thu Aug 18, 2005 6:07 pm
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

Posted: Fri Aug 19, 2005 2:04 pm
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.

Posted: Tue May 09, 2006 7:21 pm
@Krzysztof Duleba

0 5 1 0 1 9 1.55

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

Posted: Mon Oct 13, 2008 10:59 pm
Indeed.

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

Posted: Mon Dec 15, 2008 4:20 pm
Thanks to Krzysztof Duleba.
For his input and output....
I count \$20.00 as a maximum and got AC.

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

Posted: Tue Dec 29, 2009 5:48 am
i got accepted taking 10\$ as maximum.

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

Posted: Tue Aug 16, 2011 7:30 pm
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

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

Posted: Sat Jul 14, 2012 12:35 pm
Try this case :

Code: Select all

``````2 2 2 2 2 1 4.05
0 0 0 0 0 0
``````

### explain 166 dp problem - what is asked

Posted: Fri Jan 10, 2014 3:52 am
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

### Re: explain 166 dp problem - what is asked

Posted: Sun Jan 12, 2014 10:17 am
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

### Re: explain 166 dp problem - what is asked

Posted: Tue Apr 08, 2014 12:41 pm
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;

}
``````

### Re: explain 166 dp problem - what is asked

Posted: Tue Apr 08, 2014 9:49 pm
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.