Ciel and Flowers

Ciel and Flowers

Fox Ciel has some flowers: r red flowers, g green flowers and b blue flowers. She wants to use these flowers to make several bouquets. There are 4 types of bouquets:

• To make a "red bouquet", it needs 3 red flowers.
• To make a "green bouquet", it needs 3 green flowers.
• To make a "blue bouquet", it needs 3 blue flowers.
• To make a "mixing bouquet", it needs 1 red, 1 green and 1 blue flower.

Help Fox Ciel to find the maximal number of bouquets she can make.

Input

The first line contains three integers r, g and b (0 ≤ r, g, b ≤ 109) — the number of red, green and blue flowers.

Output

Print the maximal number of bouquets Fox Ciel can make.

Sample test(s)

input

3 6 9

output

6

input

4 4 4

output

4

input

0 0 0

output

0

Note

In test case 1, we can make 1 red bouquet, 2 green bouquets and 3 blue bouquets.

In test case 2, we can make 1 red, 1 green, 1 blue and 1 mixing bouquet.

-------------------------------------editorial--------------------------------

If there are no "mixing bouquet" then the answer will be r/3 + g/3 + b/3. One important observation is that: There always exist an optimal solution with less than 3 mixing bouquet.

The proof is here: Once we get 3 mixing bouquet, we can change it to (1 red bouquet + 1 green bouquet + 1 blue bouquet)

So we can try 0, 1, 2 mixing bouquet and make the remain 3 kind of bouquets use above greedy method. Output one with largest outcome.

-----------------------------------------------code-------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int main()

 {

  lli a,b,c;

  cin>>a>>b>>c;

  lli ans=0;

   if(a>=3 && a%3==0) ans+=(a-3)/3;

   else ans+=a/3;

 

    if(b>=3 && b%3==0) ans+=(b-3)/3;

    else ans+=b/3;

     if(c>=3 && c%3==0) ans+=(c-3)/3;

     else ans+=c/3;

     //cout<<ans<<endl;

     

     int r1,r2,r3;

      if(a%3==0 && a>=3)

       {

        r1=3;

  }

  else r1=a%3;

  

  if(b%3==0 && b>=3)

       {

        r2=3;

  }

  else r2=b%3;

  

  

  if(c%3==0 && c>=3)

       {

        r3=3;

  }

  else r3=c%3;

  

  int temp1=min(min(r1,r2),r3);

 // cout<<r1<<" "<<r2<<" "<<r3<<endl;

  int temp2=0;

  if(r1%3==0 && r1!=0) temp2++;

  if(r2%3==0 && r2!=0) temp2++;

  if(r3%3==0 && r3!=0) temp2++;

  ans+=max(temp1,temp2);

  cout<<ans<<endl;

 }

------------------------------------------------easy one -----------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

int main()

 {

  lli a,b,c;

  cin>>a>>b>>c;

  lli ans=0;

  // one mixing 

   if(a>=1 && b>=1 && c>=1)

     ans=max(ans,(a-1)/3+(b-1)/3+(c-1)/3+1);

     // two mixing 

     if(a>=2 && b>=2 && c>=2)

     ans=max(ans,(a-2)/3+(b-2)/3+(c-2)/3+2);

     

      // three mixing 

     if(a>=3 && b>=3 && c>=3)

     ans=max(ans,(a-3)/3+(b-3)/3+(c-3)/3+3);

     //zero mixing 

     

     ans=max(ans,a/3+b/3+c/3);

     cout<<ans<<endl;

     

     

 }