Trong bộ phim "Lost on space" (Mất tích trong vũ trụ), con tàu của gia đình Robinson bị các con nhện ngoài hành tinh xuyên thủng. Toàn bộ dưỡng khí trong tàu bị mất hết, trưởng tàu-tiến sĩ Robinson quyết định quay trở về Trái Đất khẩn cấp. Trước tiên ông bật hệ thống dẫn đường tự động và xác định thời gian để con tàu trở về được Trái Đất là ngày. Tiếp theo là một vấn đề nan giải là làm sao có thể duy trì không khí trong tàu trong suốt quá trình trở về Trái Đất.
Trên tàu có bình chứa không khí phục vụ trường hợp khẩn cấp đánh số thứ tự . Bình thứ có thể tích . Việc sử dụng các bình này được thực hiện theo đúng thứ tự (bình phải sử dụng sau bình ) và nếu thực hiện mở bình thì chỉ thực hiện vào lúc bắt đầu một ngày mới (lúc , do hệ thống bị trục trặc). Vì vỏ tàu đã bị khoan thủng một lỗ nhỏ nên không khí sẽ thoát ra khỏi lỗ này với tốc độ sau mỗi ngày một nửa lượng không khí trong tàu bị thoát ra (nếu lượng không khí là số lẻ thì lấy phần nguyên của giá trị này khi chia cho ).
Hãy xác định một qui trình mở các bình không khí sao cho lượng không khí trong tàu ở ngày ít không khí nhất là lớn nhất.
Để minh họa, giả sử có bình không khí có thể tích lần lượt là và cần duy trì hoạt động trong ngày. Nếu mỗi ngày sử dụng bình thì ta có bảng sau:
Và ngày ít không khí nhất chỉ có (ngày thứ nhất). Tuy nhiên ta có sơ đồ tốt hơn:
và ngày ít không khí nhất bây giờ có (ngày thứ năm). Đây cũng là một trong những phương án tốt nhất.
Dữ liệu:
Dòng đầu tiên ghi hai số nguyên và ;
dòng tiếp theo, dòng thứ ghi số nguyên dương ;
Kết quả:
Ghi ra một số nguyên duy nhất là lượng không khí lớn nhất có được ở ngày ít không khí nhất.
Ví dụ:
Dữ liệu:
5 5
10
40
13
22
7
Kết quả:
24
Giải thích:
Ngày mở hai bình số ; ngày không mở bình nào; ngày mở bình ; ngày mở bình ; ngày mở bình .
