Moderator: Board moderators

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.
"Everything should be made simple, but not always simpler"
anupam
A great helper

Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm

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;
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]
minskcity
Experienced poster

Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

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
LankS
New poster

Posts: 1
Joined: Mon Mar 21, 2005 8:25 pm
Location: Univ. Aveiro - PORTUGAL

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
keep it real!

jaracz
Learning poster

Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

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
eduaquiles
New poster

Posts: 2
Joined: Tue Oct 09, 2007 3:47 am
Location: UFRGS - Brazil

Now it works... its the matrix...

just use the right index (m5,m10,cokes)

and voil
eduaquiles
New poster

Posts: 2
Joined: Tue Oct 09, 2007 3:47 am
Location: UFRGS - Brazil

### Re: 10626 - Buying Coke

I would rather say that
Code: Select all
`ones_left = original_money - 8*cokes_bought - 5*fives_left - 10*tens_left`
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### 10626 I can't find anything wrong but……

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;}`
zslwyuan
New poster

Posts: 4
Joined: Sun Nov 28, 2010 10:04 am

### Re: 10626 - Buying Coke

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.
afsar
New poster

Posts: 2
Joined: Mon Nov 21, 2011 12:27 pm

Previous