B. Такси

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хичээл тарсны дараа $n$ бүлэг хүүхэд Поликарпад төрсөн өдрийн мэнд хүргэхээр гэрт рүү нь явжээ. $i$-р бүлэгт $s_i$ ($1 ≤ s_i ≤ 4$) хүүхэд байгаа ба тэд хамтдаа явахыг хүсэж байгаа. Тэд такси барихаар шийдсэн ба таксинд хамгийн ихдээ 4 хүн багтана.

Тийм бол бүх хүүхдүүдийг авч явахын тулд хамгийн цөөндөө хэдэн такси хэрэгтэй вэ? Бүлэг бүрийн хүүхдүүд нэг таксинд сууж явах ёстой ба нэг таксинд олон бүлэг багтааж болно.

Оролт

Эхний мөрөнд бүлгийн тоо $n$ ($1 ≤ n ≤ 10^5$). Дараагийн мөрөнд $n$ ширхэг $s_i$ тоо.

Гаралт

Бүх хүүхдийг багтааж чадах хамгийн цөөн таксины тоо.

Орчуулсан: gmunkhbaatarmn

Жишээ тэстүүд

Оролт
5
1 2 4 3 3
Гаралт
4
Оролт
8
2 3 4 4 2 1 3 1
Гаралт
5

Тэмдэглэл

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.

Сэтгэгдлүүдийг ачааллаж байна...