Page 2 of 2
Posted: Tue Jul 20, 2004 1:11 pm
by anupam
Hello Yarin, You told that you had tested my solution. But After changing the limit I got 504 for your inout. So, there be aything wrong. Please help. 
Posted: Sun Aug 08, 2004 10:08 pm
by minskcity
Hi, I'm getting WA on this problem too
. Here is my aproach:
1) buy coke using (10 + 1 + 1 + 1) while n10 + n5 < c; (create fives)
2) buy coke using (10) while n10 > 0; (no fives are needed anymore)
3) buy coke using (5 + 1 + 1 + 1) while n5/2 < c;
4) buy coke using (5 + 5) while n5 >= 2;
5) buy coke using (8*1);
6) print the number of coins used.
What's wrong with this aproach??? Here is my code:[cpp]#include <iostream>
using namespace std;
long c, n1, n5, n10, t;
int main(){
cin >> t;
while(t-- && cin >> c >> n1 >> n5 >> n10){
long out = 0;
while(n10 && c && n5 + n10 < c){
out += 4;
n5++;
n10--;
c--;
}
while(n10 && c){
n10--;
c--;
out++;
}
while(c && n5 && n5/2 < c){
out += 4;
n5--;
c--;
}
while(c && n5 > 2){
out += 2;
n5 -= 2;
c--;
}
out += c*8;
cout << out << endl;
}
return 0;
}
[/cpp]
Posted: Mon Mar 21, 2005 8:30 pm
by LankS
Hi
I'm getting realy mad about this problem. I thought I hade all the cases covered but I keep on getting WA. All the inputs I get (even the ones taken from this forum) give a right output. I don't know what is the case I'm forgetting...
If someone please put here some inputs....
Thanks
Posted: Wed Jul 27, 2005 10:04 am
by jaracz
input 20 200 3 0
20 200 2 0 coins:1 money in machine:5
19 200 1 0 coins:2 money in machine:2
19 200 0 0 coins:3 money in machine:7
18 199 0 0 coins:4 money in machine:0
...
this mean:
put 5coin -- nothing happened
put 5coin -- 1st coke bought 2$ left
put 5coin -- nothing happened (money = 7)
--no more 5coins so put 1coin--
put 1coin -- 2nd coke bought
and now buy the rest of coke left(C)
You may assume that the machine won't run out of coins and that I always have enough coins to buy all the cokes I want.
so you can calculate the rest of coins as follow
coins += C*8(18*8);
so coins = 148
Regards
Posted: Wed Oct 24, 2007 4:14 am
by eduaquiles
Yeah... the same WA problem... all 5 tests:
f1 := f(m1+2,m5,m10-1,cocas-1,arrei) + 1;
f2 := f(m1-3,m5+1,m10-1,cocas-1,arrei) + 4;
f3 := f(m1+2,m5-2,m10,cocas-1,arrei) + 2;
f4 := f(m1-3,m5-1,m10,cocas-1,arrei) + 4;
f5 := f(m1-8,m5,m10,cocas-1,arrei) + 8;
f := min(f1,f2,f3,f4,f5)
I'm going crazy... hahaha
Did I miss some case? oO
Posted: Wed Oct 24, 2007 5:01 am
by eduaquiles
Now it works... its the matrix...
just use the right index (m5,m10,cokes)
and voil
Re: 10626 - Buying Coke
Posted: Fri Jan 22, 2010 8:37 am
by serur
I would rather say that
Code: Select all
ones_left = original_money - 8*cokes_bought - 5*fives_left - 10*tens_left
10626 I can't find anything wrong but……
Posted: Tue Jan 25, 2011 4:01 am
by zslwyuan
I can't find anything wrong but failed this case:
1
150 500 100 20
My Code:
Code: Select all
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int dpp[151][101][51],used[151][101][51],cct,t,C,N1,N5,N10,M;
int dp(int c,int n5,int n10)
{
int n1=M-(C-c)*8-n5*5-n10*10;
if (n1<0||n5<0||n10<0) return 202364231;
if (c==0)return dpp[c][n5][n10]=0;
if (used[c][n5][n10]==cct)return dpp[c][n5][n10];
used[c][n5][n10]=cct;
int a=202364231;
if(n1>=8)a<?=dp(c-1,n5,n10)+8;
if(n1>=3&&n5>=1)a<?=dp(c-1,n5-1,n10)+4;
if(n10>=1)a<?=dp(c-1,n5,n10-1)+1;
if(n5>=2)a<?=dp(c-1,n5-2,n10)+2;
if(n10>=1&&n1>=3)a<?=dp(c-1,n5+1,n10-1)+4;
return dpp[c][n5][n10]=a;
}
int main()
{
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
scanf("%d\n",&t);
memset(dpp,-1,sizeof(dpp));memset(used,-1,sizeof(dpp));
while (t--)
{
cct=-10*(t+5);
scanf("%d %d %d %d\n",&C,&N1,&N5,&N10);
M=N1+N5*5+N10*10;
int ans=202364231;
if(N1>=8)ans<?=dp(C-1,N5,N10)+8;
if(N1>=3&&N5>=1)ans<?=dp(C-1,N5-1,N10)+4;
if(N10>=1)ans<?=dp(C-1,N5,N10-1)+1;
if(N5>=2)ans<?=dp(C-1,N5-2,N10)+2;
if(N10>=1&&N1>=3)ans<?=dp(C-1,N5+1,N10-1)+4;
printf("%d\n",ans);
}
return 0;
}
Re: 10626 - Buying Coke
Posted: Mon Nov 21, 2011 1:03 pm
by afsar
zslwyuan,
Instead of calculating "n1", you need to consider passing "n1" in the "dp" function and apply necessary deduction (or addition) in the recursive "dp" call.
Thanks.