### Problem Description：

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of $s_{i}$ friends (1 ≤ $s_{i}$ ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

### Input Specification:

The first line contains integer n (1 ≤ n ≤ 105) — the number of groups of schoolchildren. The second line contains a sequence of integers $s_{1}$, $s_{2}$, …, $s_{n}$ (1 ≤ $s_{i}$ ≤ 4). The integers are separated by a space, $s_{i}$ is the number of children in the i-th group.

### Output Specification:

Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

5
1 2 4 3 3

4

8
2 3 4 4 2 1 3 1

5

8
1 1 2 1 1 1 3 2

### AC代码：WA代码：

``````#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
#define ms(a,x) memset(a,x,sizeof(a))
int main()
{
ios::sync_with_stdio(false);
int n;
cin >> n;
int s[n+1], car[n+1];
ms(car,0);
Up(i,1,n)
{
cin >> s[i];
Up(j,1,n)
{
if(car[j]+s[i] <= 4)
{
car[j] += s[i];
break;
}
}
}
int cnt = 0;
for(auto it : car)
{
if(it)
{
cnt++;
}
}
cout << cnt << endl;
return 0;
}``````

### AC代码：

``````#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
int main()
{
ios::sync_with_stdio(false);
int n,cnt = 0;
cin >> n;
int a[5]={0};    //a[i]表示有a[i]组是i个人一起搭车的
Up(i,1,n)
{
int _;
cin >> _;
a[_]++;
}
int _ = min(a[1],a[3]);   //3只能和1搭配,所以优先考虑3
a[1] -= _;
a[3] -= _;
cnt += _ + a[3] + a[4] + a[2]/2;    //4直接加,2要和2搭配
if(a[2]&1)   //若2人一组的是奇数
{
cnt++;
if(a[1]>=2)
{
a[1] -= 2;
}
else if(a[1]==1)   //不足2人
{
a[1]--;
}
}
cnt += a[1]/4 + (a[1]%4 ? 1 : 0);   //剩下的1尽可能地坐满
cout << cnt << endl;
return 0;
}``````