EGYPIZZA SPOJ

help
beginner
codechef
edit
spoj
wa

#1

Couldn’t find out the reason for WA on SPOJ ? ? ! … though it’s a easy question … but getting WA … Don’t know which case i m missing …
My Code : : http://ideone.com/m7N8OF

Problem : : http://www.spoj.com/problems/EGYPIZZA/ … Thanks in advance :slight_smile: !


#2

Hi! There’s a slight error in your logic. It doesn’t minimize the total number of pizzas. In fact it is wrong for the test case you provided at ideone.

5

1/2

3/4

1/2

1/4

1/4
Your answer is 4 but the correct answer is 3 (1 pizza for 3/4, 1 pizza for (1/2 + 1/4 +1/4), 1 pizza for 1/2).


For correct implementation see http://discuss.codechef.com/questions/54773/spoj-egypizza.


#3

CODE:

#include<bits/stdc++.h>
using namespace std;
map<string,double> m;
int main()
{

m["1/4"]=0.25;    
m["1/2"]=0.50;
m["3/4"]=0.75;
   int n;
   cin>>n;
   int co25=0, co50=0, co75=0;
   for(int i=0; i<n; ++i)
   {
       string s;
       cin>>s;
       if(m[s]==0.75)
        ++co75;
       else if(m[s]==0.50)
        ++co50;
       else
        ++co25;
   }
   int ans=co75+ceil((double)co50/2.0)+1;
   int wasted=co75;
  if(co50%2)
    wasted+=2;
   co25-=wasted;
   if(co25>0)
   {
       ans+=ceil((double)co25/4.0);
   }
   cout<<ans;
return 0; 

}


#4

@michelangelo answer is 4 itself … What about Pizza for Abotrika?


#5

correct ans is 4