zoj 3590 -3+1.md

题目

ZOJ is 10 years old! For celebrating, we are offering the easiest problem in the world to you.

Recently we received a long sequence. We can modify the sequence once by the following two steps.

Choose any element in the sequence, say x(satisfying x ≥ 3), and subtract 3 from x.
Choose any element in the sequence, say x, and add 1 to x.
Now, we want to know how many times at most the sequence can be modified.

Input

The input contains multiple test cases. For each case, the first line contains an integer n(1 ≤ n ≤ 20000). The second line contains n integers describing the sequence. All the numbers in the sequence are non-negative and not greater than 1000000.

Output

Output number of times at most the sequence can be modified, one line per case.

Sample Input

• 1
• 10
• 2
• 10 11

Sample Output

• 4
• 10

参考答案

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>

using namespace std;

long long x,ans,sum,cn2,cn1;
int n;
int main(){
 while(scanf("%d",&n)==1)
 {
 ans=0;
 cn2=0;
 cn1=0;
 for(int i=1;i<=n;i++)
 {
 scanf("%I64d",&x);
 ans+=x/3;
 if(x%3==2) cn2++;
 if(x%3==1) cn1++;
 }
 sum=ans;
 if(ans==0) {printf("0\n");continue;}
 ans+=cn2;
 if(sum<=cn1) ans+=(sum-1);
 else 
 {
 ans+=cn1;
 ans+=(sum-cn1-1)/2;
 }
 printf("%lld\n",ans);
 }
 return 0;
}