10626 - Buying Coke
Moderator: Board moderators
10626 - Buying Coke
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
Thanks in advance.
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
Thanks in advance.
My signature:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
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.
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)
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)
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!
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:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
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.
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.
Oh thanks~~
At first, I try to find a DP solution, but I forget this relation
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.
At first, I try to find a DP solution, but I forget this relation
So I wonder how to use 32MB memory to hold all states.........ones_left=original_money-8*cokes_left-5*fives_left-10*tens_left;
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:
- Please make discussion about the algorithm BRFORE posting source code.
We can learn much more in discussion than reading source code. - I HATE testing account.
- Don't send me source code for debug.
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 :/
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
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!!!
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
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 :-/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
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..
waiting for any kind of help... [/i][/b]
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;
}
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"
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.
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.
"Everything should be made simple, but not always simpler"