TAXI - Taxi
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: VietNamVoDich

Để chúc mừng sinh nhật bạn Nhuận ngày 29/2, các bạn học sinh lớp 11A dự định tổ chức dã ngoại đến biển Nha Trang và lớp sẽ đi bằng taxi.

Các bạn trong lớp được chia thành n nhóm, mỗi nhóm thứ i gồm si bạn (1 ≤ si ≤ 4) và mỗi chiếc taxi chở tối đa 4 hành khách.

Vậy lớp 11A cần thuê ít nhất bao nhiêu chiếc taxi để chở các nhóm đi, với điều kiện là các bạn trong nhóm phải ngồi chung taxi (một taxi có thể chở một nhóm trở lên).


Dữ liệu nhập:
- Dòng đầu chứ số nguyên n (1 ≤ n ≤ 105) - số lượng các nhóm học sinh
- Dòng số 2 chứa dãy số nguyên s1, s2, ..., sn (1 ≤ si ≤ 4). Các số nguyên cách nhau bởi dấu cách với si là số trẻ em trong nhóm thứ i.

Dữ liệu xuất:
In 1 số nguyên duy nhất - số lượng tối thiểu taxi cần thiết để chở tất cả trẻ em đến nơi.

Ví dụ

  • input
    5
    1 2 4 3 3
    output
    4
  • input
    8
    2 3 4 4 2 1 3 1
    output
    5

Trong test đầu tiên, các bạn học sinh có thể sắp xếp như sau:
- Nhóm thứ 3 gồm 4 học sinh
- Nhóm thứ 4 gồm 3 học sinh
- Nhóm thứ 5 gồm 3 học sinh
- Nhóm thứ nhất và nhóm thứ 2 gồm 3 học sinh (1 và 2 học sinh)
Vậy dữ liệu ra là 4

Back to Top