Page 1 of 2

10626 - Buying Coke

Posted: Wed Mar 10, 2004 3:38 pm
by ..
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 :roll:
Thanks in advance.

10626 Buying Coke ( but using more coins)

Posted: Sun Mar 14, 2004 11:56 am
by sohel
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.

Posted: Sun Mar 14, 2004 1:01 pm
by Adrian Kuegel
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)

Posted: Sun Mar 14, 2004 8:43 pm
by ..
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!

Posted: Mon Mar 15, 2004 12:47 am
by Yarin
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.

Posted: Mon Mar 15, 2004 6:42 am
by ..
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.

Posted: Fri Apr 09, 2004 12:54 pm
by miras
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

Posted: Fri Apr 16, 2004 5:30 am
by epsilon0
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 :/

Posted: Fri Apr 16, 2004 5:54 am
by epsilon0
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!!!

Posted: Sun Apr 18, 2004 1:18 am
by Yarin
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 :-/

Posted: Fri Jul 02, 2004 10:55 pm
by anupam
Please help in this problem.
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... :oops: [/i][/b]

Posted: Fri Jul 02, 2004 11:23 pm
by anupam
Please help. frustated. WA 5 times. what is to check more?? :cry:

Posted: Sat Jul 03, 2004 5:26 pm
by Yarin
Try the input

150 500 100 20

Your program will output the wrong answer due to your
arrays being to small (correct answer is 640).

Posted: Sat Jul 03, 2004 5:52 pm
by anupam
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?
Help please.

Posted: Sun Jul 04, 2004 9:38 pm
by Yarin
Change the array size to 200 (and the for-loops as well) for the five crowns, and it should work (I tested changing your solution). The reason is that the number of five crowns maybe well exceed the initial values due to the 10+1+1+1 -> 5 exchange.