Ở giữa đêm, một nhóm du khách muốn qua một cây cầu cũ và đổ nát. Họ đã chỉ có một chiếc đèn pin, ánh sáng của đèn pin chỉ cho phép nhiều nhất hai khách du lịch qua cầu cùng một lúc. Các du khách không thể qua cầu mà không có đèn pin hoặc trong các nhóm lớn hơn hai trừ khi họ muốn rơi xuống sông. Mỗi du khách cần một lượng thời gian nhất định để vượt qua cây cầu. Hai khách du lịch qua cầu với nhau cần một khoảng thời gian của người chậm nhất trong nhóm hai người qua cầu. Hãy tính thời gian ngắn nhất để nhóm du khách qua cầu?
Ví dụ: Giả sử nhóm du khách có người. Người đầu tiên của họ cần phút để vượt qua cây cầu, người thứ hai là phút, người thứ ba là phút và người thứ tư là phút. Các hình ảnh sau đây cho thấy làm thế nào họ có thể vượt qua cây cầu trong 44 phút. Tuy nhiên, họ có thể làm nó nhanh hơn. Làm thế nào?
Một phương pháp qua cầu trong phút. Các con số trong vòng tròn biểu thị thời gian (theo phút) qua cầu của khách du lịch.
Yêu cầu: Tìm thời gian ngắn nhất để đoàn du khách qua cây cầu.
Dữ liệu vào:
Dòng đầu chứa số nguyên dương là số khách du lịch ;
Dòng thứ trong dòng tiếp theo, mỗi dòng ghi một số nguyên dương là thời gian để du khách thứ qua cầu. Tổng thời gian qua cầu của du khách không vượt quá .
Dữ liệu ra:
Gồm một số duy nhất là thời gian ngắn nhất để đoàn du khách qua cầu.
