Tiệm cắt tóc
Đề bài
Mô tả
Uiharu và Misaka cùng mở một tiệm cắt tóc. Mỗi ngày có khách hàng. Mỗi người muốn một kiểu tóc khác nhau nên khối lượng công việc cũng khác nhau. Uiharu và Misaka có những kỹ năng riêng để tăng tốc công việc: Uiharu có thể lập trình cho tông đơ chạy nhanh hơn, cô làm được đơn vị công việc mỗi giây; Misaka có thể điều khiển dòng điện để vận hành tông đơ mà không cần dùng tay, cô làm được đơn vị công việc mỗi giây.
Mỗi khách hàng chỉ được phục vụ bởi một thợ cắt tóc. Uiharu và Misaka muốn tan làm cùng nhau: họ về nhà sau khi khách hàng cuối cùng rời đi. Vì vậy họ cần phân chia công việc thật đều. Hãy giúp họ tìm thời gian ít nhất để hoàn thành công việc trong ngày. Nếu khách hàng cuối cùng rời đi giữa một giây, ta coi công việc kết thúc vào cuối giây đó.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên là số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm hai dòng: dòng đầu chứa ba số , , ; dòng thứ hai chứa số .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số là thời gian ít nhất (tính bằng giây) để hoàn thành công việc.
Ràng buộc
- .
- .
- .
- .
- với mọi .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 5 2 3 2 7 3 6 6 |
5 | Uiharu phục vụ hai khách và (tổng , mất giây), Misaka phục vụ ba khách còn lại (tổng , mất giây). |
| 2 1 1 1 5 3 10 1 1 1 1 |
5 1 |
Bộ thứ hai: Uiharu phục vụ cả ba khách, tổng đơn vị công việc xong trong giây đầu tiên. |
Bình luận