Qua cầu ban đêm
Đề bài
Mô tả
Một nhóm người đi bộ đến một con sông vào ban đêm. Họ muốn đi qua một cây cầu, nhưng cây cầu chỉ chịu được một số lượng người giới hạn cùng lúc. Cả nhóm chỉ có đúng một ngọn đuốc, và mỗi lần đi qua cầu đều phải mang theo đuốc. Mỗi người cần một khoảng thời gian nhất định để đi qua cầu; một nhóm đi cùng nhau phải đi theo tốc độ của người chậm nhất trong nhóm. Hỏi cần ít nhất bao nhiêu thời gian để tất cả mọi người sang được bờ bên kia?
Ví dụ, ở ví dụ thứ nhất, cây cầu chịu được người cùng lúc và có người với thời gian qua cầu lần lượt là phút, phút, phút và phút. Thời gian ngắn nhất là phút, đạt được bằng chuỗi các lượt qua cầu sau. Thứ nhất, hai người nhanh nhất đi sang trong phút. Thứ hai, người nhanh nhất quay lại trong phút. Thứ ba, hai người chậm nhất đi sang trong phút. Thứ tư, người nhanh thứ hai quay lại trong phút. Thứ năm, hai người nhanh nhất đi sang trong phút.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và , trong đó () là số người, và () là số người tối đa cây cầu chịu được cùng lúc.
Dòng tiếp theo chứa số nguyên ( với mọi ). Người thứ cần thời gian để đi qua cầu.
Dữ liệu ra
In ra tổng thời gian nhỏ nhất để cả nhóm đi qua cầu.
Ràng buộc
- .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 2 1 2 10 5 |
17 | Gọi mỗi người theo thời gian qua cầu của họ. Lần lượt: sang ( phút), quay lại ( phút), sang ( phút), quay lại ( phút), sang ( phút). Tổng phút. |
| 4 6 1 2 10 5 |
10 | Cầu chịu được người nên cả người đi sang cùng một lượt, mất phút. |
Bình luận