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 si friends (1 ≤ si ≤ 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)?
課後 n 組學童出去，決定去拜訪 Polycarpus 慶祝他的生日。 我們知道第 i 組由 si 個朋友組成（1 ≤ si ≤ 4），他們想一起去找Polycarpus。 他們決定乘出租車去那裡。 每輛車最多可搭載四名乘客。 如果每組的所有成員都乘坐同一輛出租車（但一輛出租車可以乘坐多組），孩子們最少需要的出租車數量是多少？
The first line contains integer n (1 ≤ n ≤ 105) — the number of groups of schoolchildren. The second line contains a sequence of integers s1, s2, ..., sn (1 ≤ si ≤ 4). The integers are separated by a space, si is the number of children in the i-th group.
第一行包含整數 n (1 ≤ n ≤ 105) — 學童組的數量。 第二行包含一個整數序列 s1, s2, ..., sn (1 ≤ si ≤ 4)。 整數之間用空格隔開，si 是第 i 組的孩子數。
Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.
打印單個數字 — 將所有孩子帶到 Polycarpus 所需的最少出租車數量。
5 1 2 4 3 3
4
8 2 3 4 4 2 1 3 1
5
公開 測資點#0 (4%): 1.0s , <1K
公開 測資點#1 (4%): 0.4s , <1K
公開 測資點#2 (4%): 0.4s , <1K
公開 測資點#3 (4%): 0.4s , <1K
公開 測資點#4 (4%): 0.4s , <1M
公開 測資點#5 (4%): 0.4s , <1M
公開 測資點#6 (4%): 0.4s , <1M
公開 測資點#7 (4%): 0.4s , <1M
公開 測資點#8 (4%): 0.4s , <1M
公開 測資點#9 (4%): 0.4s , <1M
公開 測資點#10 (4%): 0.4s , <1M
公開 測資點#11 (4%): 0.4s , <1M
公開 測資點#12 (4%): 0.4s , <1M
公開 測資點#13 (4%): 0.4s , <1M
公開 測資點#14 (4%): 0.4s , <1M
公開 測資點#15 (4%): 0.4s , <1M
公開 測資點#16 (4%): 0.4s , <1M
公開 測資點#17 (4%): 0.4s , <1M
公開 測資點#18 (4%): 0.4s , <1M
公開 測資點#19 (4%): 0.4s , <1M
公開 測資點#20 (4%): 0.4s , <1M
公開 測資點#21 (4%): 0.4s , <1M
公開 測資點#22 (4%): 0.4s , <1M
公開 測資點#23 (4%): 0.4s , <1M
公開 測資點#24 (4%): 0.4s , <1M
In the first test we can sort the children into four cars like this:
- the third group (consisting of four children),
- the fourth group (consisting of three children),
- the fifth group (consisting of three children),
- the first and the second group (consisting of one and two children, correspondingly).
There are other ways to sort the groups into four cars.
在第一個測試中，我們可以像這樣將孩子分成四輛車：
第三組（由四個孩子組成），
第四組（由三個孩子組成），
第五組（由三個孩子組成），
第一組和第二組（分別由一個和兩個孩子組成）。
還有其他方法可以將這些組分成四輛車。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||