Đề thi Học sinh giỏi Tin học/4
Mô tả bài toán
[sửa]Trong dịp nghỉ hè, các bạn học sinh lớp 12 dự định tổ chức liên hoan cuối cấp tại nhà hàng nọ và sẽ đi bằng taxi. Các bạn được chia thành n nhóm, 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. Điều kiện là các bạn cùng một nhóm phải ngồi chung một taxi (một chiếc taxi có thể chở nhiều nhóm, miễn là đủ chỗ), như vậy bài toán đặt ra là lớp 12 cần thuê ít nhất bao nhiêu chiếc taxi.
Dữ liệu
[sửa]- Dữ liệu vào
Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 105) là số lượng các nhóm học sinh.
Dòng thứ hai 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, Si là số học sinh trong nhóm thứ i.
- Dữ liệu ra
Một số nguyên duy nhất là số lượng taxi thỏa mãn yêu cầu đề bài.
Ví dụ
[sửa]| DỮ LIỆU VÀO | DỮ LIỆU RA |
5 1 2 4 3 3 |
4 |