Moderator: Board moderators

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

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"

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
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]

LankS
New poster
Posts: 1
Joined: Mon Mar 21, 2005 8:25 pm
Location: Univ. Aveiro - PORTUGAL
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

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
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!

eduaquiles
New poster
Posts: 2
Joined: Tue Oct 09, 2007 3:47 am
Location: UFRGS - Brazil
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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### 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

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

### 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;
}``````

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

### 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.