Có n (1 <= n <= 10^6) người cần qua cầu trong đêm tối. Cầu rất yếu nên chỉ đi 1 lúc tối đa được 2 người. Họ cần có đèn mới qua được cầu; mà cả nhóm chỉ có duy nhất 1 cái đèn. Vì vậy nên mỗi lần 2 người qua sông thì phải cử 1 người cầm đèn quay trở lại. Mỗi người qua cầu với các tốc độ lần lượt là a[i] giây với (1 <= i <= n; 1 <= a[i] <= 100). Hai người đi cùng nhau thì sẽ đi theo tốc độ của người đi chậm hơn. Ta cần tìm thời gian ít nhất để tất cả n người qua bên kia cầu.

Ví dụ:

Test 1: N = 4; a = {1, 3, 8, 12}.

Trong test 1 đi theo cách như sau:

1) Người 1 và 2 qua cầu: mất 3 giây.

2) Người 1 cầm đèn quay trở lại: mất 1 giây.

3) Người 3 và 4 qua cầu: mất 12 giây.

4) Người 2 cầm đèn quay trở lại: mất 3 giây.

5) Người 1 và 2 qua cầu: mất 3 giây.

Tổng cộng mất 22 giây.

Test 2: N = 5; a = {1, 3, 6, 8, 12}.

Trong test 2 đi theo cách như sau:

1) Người 1 và 2 qua cầu: mất 3 giây.

2) Người 1 cầm đèn quay trở lại: mất 1 giây.

3) Người 4 và 5 qua cầu: mất 12 giây.

4) Người 2 cầm đèn quay trở lại: mất 3 giây.

5) Người 1 và 3 qua cầu: mất 6 giây.

6) Người 1 cầm đèn quay trở lại: mất 1 giây.

7) Người 1 và 2 qua cầu: mất 3 giây.

Tổng cộng mất 29 giây.

Test 3: N = 1; a = {4}.

Người 1 qua cầu mất 4 giây. Tổng cộng mất 4 giây.

Nguồn