Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

First of all, I am not trying to show off anything.....
I get accepted on 10626 with a O(1) solution. But from the ranklist, it seems that someone use longer runtime and large memory to solve it. Is there any DP solution to this problem?? I am really curious to know
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

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

### 10626 Buying Coke ( but using more coins)

I tried a simple approach and knew that I was gonna get WA. Well, I wasn't wrong.. I did get WA. But I would like to know : what is the mistake in my approach?

First I use all the 10 coins to buy as many cokes ( number of one coin increases by two for each 10 coin).

Then If the total number of 5 coins is more than the remaining coke, then i
use 2 five coins to buy a coke... this process continues until number of 5 coins left equals to the coke remaining.

then i buy coke using 5 1 1 1, until 5 finishes.

then i use 1 1 1 1 1 1 1 1, until required work is done.

Can somebody point out the mistake.

Thanks.
Last edited by sohel on Mon Mar 15, 2004 9:58 am, edited 1 time in total.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
A simple example where you fail is:
you want to buy 4 cokes and have 3 coins of value 10, 2 coins of value 1.
You would need to insert 11 coins. But here how you can do it with 10 coins:
insert 10 (1 x 10) get 2 x 1 back
insert 10 (1 x 10) get 2 x 1 back
insert 13 (1 x 10, 3 x 1) get 1 x 5 back
insert 8 (1 x 5, 3 x 1)

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Few days ago I posted a message about this problem, but it suddently disappeare. (Seems the board has bug.....)

I post it again here:

I get accepted on 10626 with a O(1) solution. But from the ranklist, it seems that someone use longer runtime and large memory to solve it. It seems that there is some DP-like solution. Can anyone tell me how to do that? I am really curious to know.... Thanks!
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
I'm more curious about the O(1) solution...

The DP solution is this simple recurrence:

f(cokes_left,fives_left,tens_left):
ones_left=original_money-8*cokes_left-5*fives_left-10*tens_left;
min=infinity
if (ones_left>=8) min<?=f(cokes_left-1,fives_left,tens_left);
if (fives_left>=2) min<?=f(cokes_left-1fives_left-2,tens_left);
if (tens_left>=1) min<?=f(cokes_left-1,fives_left,tens_left-1);
if (fives_left>=1 && ones_left>=3) min<?=f(cokes_left-1,fives_left-1,tens_left);
if (tens_left>=1 && ones_left>=3) min<?=f(cokes_left-1,fives_left+1,tens_left-1);
return min;

ie test all combinations. There are few enough states to use memorize them all.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Oh thanks~~
At first, I try to find a DP solution, but I forget this relation
ones_left=original_money-8*cokes_left-5*fives_left-10*tens_left;
So I wonder how to use 32MB memory to hold all states.........

Here is my O(1) solution,
Warning! Spoiler

In some case, you need to insert coins more than enough to get a change of a larger coin back. Actually, there is only one case like that:
insert 13 (1 x 10, 3 x 1) get 1 x 5 back.
And you only need to do this if you have the chance to insert 8 x 1 to buy a coke. Consider you have 1 coin of value 10, 6 coins of value 1.

Before make the change,
insert 10 (1 x 10) get 2 x 1 back
insert 8 (8 x 1)

After do the change,
insert 13 (1 x 10, 3 x 1) get 1 x 5 back
insert 8 (1 x 5, 3 x 1)

So you need to consider how many times will (8 x 1) happen, and how many extra coin of value 5 you can get back from the machine.
My signature:
We can learn much more in discussion than reading source code.
• I HATE testing account.
• Don't send me source code for debug.

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
but what should be the output for test... which is.....

1
2 1 0 0
my output is
0

is it good ??

plz.. give me more tests.... becouse i keep WA... ;-(

Regards.
MIras

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
i have an O(1) solution, like .. but it got WA, i must have done an error somewhere.

what i would like to help me spot my error, is lots of input/output test cases. if someone with AC can please give me some... thanx

this problem seems very simple, but its tricky :/
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.
haha i just got accepted, that was a silly mistake!!! i'm glad i finally solved this problem.

miras:

2 1 0 0 is not a valid input, you cannot encounter such an input, because it is guaranteed that you have enough money to buy to cokes... so for 2 cokes you'd have at least 16 units.

on a side note, i found an interesting fact about this problem. the number of coins of value 1 doesnt matter. you dont need it to solve the problem... the answer will be the same regardless the number of coins of value 1 (provided of course the input is valid, ie you have enough money)

good luck miras and everyone trying to solve this problem!!!
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
on a side note, i found an interesting fact about this problem. the number of coins of value 1 doesnt matter. you dont need it to solve the problem... the answer will be the same regardless the number of coins of value 1 (provided of course the input is valid, ie you have enough money
Yes, I noticed this when I created the problem... was trying to figure out a case where it DID matter, only to realize there were no such case :-/

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
I can't find where the problem is...
checking all possible cases with dp.
so why wa?

is there any critical case??

here is the code. please check it..

Code: Select all

``````
#include<stdio.h>
#define A 155
#define B 200
#define C 40
long a[A][B][C],m,noo,nff,ntt,nn;
long no,min,b;
main()
{
freopen("in.txt","r",stdin);
long cas,z,i,j,k,n,nf,nt;
scanf("%ld",&cas);
for(z=0;z<cas;z++)
{
scanf("%ld%ld%ld%ld",&nn,&noo,&nff,&ntt);
m=noo+5*nff+10*ntt;
for(i=0;i<A;i++) for(j=0;j<B;j++) for(k=0;k<C;k++) a[i][j][k]=0;
for(i=0;i<A;i++) a[i][0][0]=i*8;//any no. of 1
a[1][1][0]=4;//only one 5 + 3 1s
for(i=2;i<B;i++) a[1][i][0]=2;//if any no. of 5
for(i=0;i<B;i++) for(j=1;j<C;j++) a[1][i][j]=1;//any no of five+ any ten
for(n=2;n<A;n++) for(nf=0;nf<B-11;nf++) for(nt=0;nt<C;nt++)
{
min=1000000;
no=m-8*(nn-n)-5*nf-10*nt;
if(no<0) continue;
if (nt>=1 && no>=3) {b=a[n-1][nf+1][nt-1]+4;if(b<min) min=b;}
if (no>=0) {b=a[n-1][nf][nt]+8;if(b<min) min=b;}
if (nt>=1) {b=a[n-1][nf][nt-1]+1;if(b<min) min=b;}
if (nf>=2) {b=a[n-1][nf-2][nt]+2;if(b<min) min=b;}
if (nf>=1 && no>=3) {b=a[n-1][nf-1][nt]+4;if(b<min) min=b;}
a[n][nf][nt]=min;
}
printf("%ld\n",a[nn][nff][ntt]);
}
return 0;
}
``````
waiting for any kind of help... [/i][/b]
Last edited by anupam on Sat Jul 03, 2004 5:49 pm, edited 1 time in total.
"Everything should be made simple, but not always simpler"

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
"Everything should be made simple, but not always simpler"

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
Try the input

150 500 100 20

arrays being to small (correct answer is 640).

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
Hello Yarin, I think my array of only five was too lttle because there is an entry like a[..][nf+1][..].

But, would you please mention what you meant by too small array? BTW, Nice problem. and, my program gives 504 after extending the array.
which means prob. I am missing something. Prob. in the init statements of DP.
Am I right?
Is there any thing wrong in the init statements?