10626 - Buying Coke

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

[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]

[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

[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

[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

[eduaquiles]

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

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

and voil

[serur]

I would rather say that

Code: Select all

ones_left = original_money - 8*cokes_bought - 5*fives_left - 10*tens_left

[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;
}

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