158B – Taxi (Codeforces Greedy)
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Sau giờ tan học, $n$ nhóm học sinh quyết định cùng nhau đi taxi về nhà. Nhóm thứ $i$ có $s_i$ học sinh ($1 \le s_i \le 4$).
Mỗi chiếc taxi có thể chở tối đa $4$ hành khách. Các bạn trong cùng một nhóm phải đi chung trên một chiếc xe (không được phép tách nhóm). Các nhóm khác nhau có thể ngồi chung xe nếu tổng số người không vượt quá $4$.
Hãy tính số lượng xe taxi tối thiểu cần thuê để chở tất cả các học sinh về nhà.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $n$ ($1 \le n \le 10^5$) — số lượng nhóm học sinh.
- Dòng thứ hai chứa $n$ số nguyên $s_1, s_2, \dots, s_n$ ($1 \le s_i \le 4$).
Dữ liệu ra
- In ra một số nguyên duy nhất — số lượng xe taxi tối thiểu cần thuê.
Ví dụ
Đầu vào:
5
1 2 4 3 3
Đầu ra:
4
Community Discussion