minTaxi

Để tổ chức liên hoan cuối năm, các bạn học sinh lớp 10A1 dự định tổ chức dã ngoại đi chơi và lớp sẽ định sẽ đi bằng taxi. Mỗi bạn đều thuộc mỗi nhóm trong n nhóm của lớp, nhóm thứ i gồm ai bạn với 1 ≤ ai ≤ 4 và mỗi chiếc taxi chở tối đa 4 hành khách.

Vì kinh phí lớp hạn hẹp, nên lớp quyết định sẽ gọi ít xe taxi nhất có thể, 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). Bạn hãy giúp lớp 10A1 tính xem cần bao nhiêu taxi nhé!

Ví dụ:

• Với n = 5, a = [1, 2, 4, 3, 3] thì kết quả min_taxi(n, a) = 4
  Giải thích:
  • Xe taxi thứ 1: sẽ chở nhóm có 4 thành viên
  • Xe taxi thứ 2, 3: mỗi xe sẽ chở nhóm có 3 thành viên
  • Xe taxi thứ 4: sẽ chở nhóm có 2 thành viên và nhóm có 1 thành viên
• Với n = 5, a = [2, 2, 2, 2, 1] thì kết quả min_taxi(n, a) = 3
  Giải thích:
  • Xe taxi thứ 1, 2: mỗi xe sẽ chở 2 nhóm có 2 thành viên
  • Xe taxi thứ 3: sẽ chở nhóm có 1 thành viên

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.1s với C++, 0.6s với Java và C#, 0.8s với Python, Go và JavaScript.

• [Đầu vào] integer n.
  1 ≤ n ≤ 105

• [Đầu vào] array of integer a.
  a.size = n

          1 ≤ a[i] ≤ 4

• [Đầu ra] integer.
  Số lượng taxi cần gọi ít nhất