10626 - Buying Coke

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by anupam » Tue Jul 20, 2004 1:11 pm


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. :oops:
"Everything should be made simple, but not always simpler"

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

Post by minskcity » Sun Aug 08, 2004 10:08 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;
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]

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

Post by LankS » Mon Mar 21, 2005 8:30 pm

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

User avatar
jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland

Post by jaracz » Wed Jul 27, 2005 10:04 am

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

Post by eduaquiles » Wed Oct 24, 2007 4:14 am

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 :roll:

Did I miss some case? oO :-?

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

Post by eduaquiles » Wed Oct 24, 2007 5:01 am

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

Post by serur » Fri Jan 22, 2010 8:37 am

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

Post by zslwyuan » Tue Jan 25, 2011 4:01 am

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

Post by afsar » Mon Nov 21, 2011 1:03 pm

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.

Post Reply

Return to “Volume 106 (10600-10699)”