Biểu diễn áo dài

Xem dạng PDF
Gửi bài giải
Điểm: 0,01 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: AODAI.INP
Output: AODAI.OUT
Tác giả:
bedao
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nhân dịp kỷ niệm ngày Quốc tế Phụ nữ 8/3, Đoàn trường X dự định tổ chức cho các em học sinh nữ trong toàn trường thi trình diễn áo dài. Các em học sinh nữ được chia thành ~N~ nhóm, nhóm thứ ~i~ gồm ~S_i~ người (~1 \leq S_i \leq 4~) và mỗi lượt trình diễn chỉ được biểu diễn tối đa ~4~ người. Hỏi đoàn trường X cần tổ chức ít nhất bao nhiêu lượt trình diễn để tất cả các học sinh nữ đều được biểu diễn phần thi áo dài của mình, với điều kiện các em trong cùng một nhóm phải trình diễn áo dài cùng một lượt (Một lượt biểu diễn có thể có một hoặc nhiều nhóm cùng biểu diễn).

Yêu cầu: Hãy xác định số lượt trình diễn tối thiểu để tất cả các em học sinh nữ tham gia phần thi của mình.

Input

Đọc từ file AODAI.INP gồm 2 dòng:

  • Dòng thứ nhất gồm một số nguyên dương ~N~ (~1 \leq N \leq 10^3~).

  • Dòng thứ hai gồm ~N~ số nguyên dương ~S_1, S_2, ..., S_N~ (~1 \leq S_i \leq 4~).

Output

Ghi ra file AODAI.OUT một số nguyên dương duy nhất là đáp án đề bài yêu cầu.

Sample Input 1

4
4 3 2 1

Sample Output 1

3

Sample Input 2

6
4 1 2 3 2 3

Sample Output 2

4

Notes

Trong ví dụ thứ nhất ta có thể chia ra 3 lượt trình diễn với cách xếp như sau:

  • ~\{1, 2\}, \{3\}, \{4\}~

  • ~\{1, 3\}, \{2\}, \{4\}~

Trong ví dụ thứ hai ta có thể chia ra 4 lượt trình diễn với cách xếp như sau:

  • ~\{1, 3\}, \{2, 2\}, \{3\}, \{4\}~

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 1
    23162035  đã bình luận lúc 9, Tháng 8, 2025, 13:20

    Ý tưởng:

    • Đếm số nhóm có 1, 2, 3, 4 người. Mỗi nhóm 4 người chắc chắn chiếm 1 lượt, do đó cộng vào kết quả
    • Ghép mỗi nhóm 3 người với 1 nhóm 1 người (nếu có), nếu không thì nhóm 3 người đứng riêng một lượt
    • Ghép các nhóm 2 người với nhau thành lượt 4 người. Nếu còn dư một nhóm 2 người thì ghép tối đa với 2 nhóm 1 người, nếu không đủ thì vẫn cần thêm 1 lượt
    • Ghép các nhóm 1 người còn lại: mỗi lượt chứa tối đa 4 người, do đó chia cho 4 và làm tròn lên