Tháng 4.2024, Zalo AI ra mắt chatbot Kiki Giao thông phiên bản thử nghiệm. Nam là 1 tester và anh đang muốn kiểm tra thử độ hiệu quả của Kiki trong việc tìm ra các đường đi tối ưu.
Bỗng nhiên, Nam nghĩ ra 1 cách để làm khó chú Zalo AI này bằng cách đặt một câu hỏi về tối ưu trong việc xây cầu.
Bài toán Nam đưa ra như sau:
- Cho ~n~ cột đá, Kiki cần dựng đứng ~n~ cột đá này và xếp chúng thành 1 đường thẳng theo 1 thứ tự nhất định và đặt ~n-1~ tấm gỗ giữa các cặp cột đá liền kề để làm 1 cây cầu.
- Chiều cao của ~n~ cột đá lần lượt là ~a_1, a_2, ..., a_n~.
- Khoảng cách giữa 2 cột đá liền kề luôn là 1
- Chiều ngang (độ dày) của các cột đá là không đáng kể.
- Luôn có ít nhất 2 cột đá
Nam yêu cầu Kiki phải tìm thứ tự xếp sao cho đường đi từ cái cột đầu tiên tới cái cột cuối dùng là ngắn nhất, và trả về kết quả là tổng chiều dài của các tấm gỗ được sử dụng.
Kiki đã nhanh chóng đưa ra đáp án của mình, nhưng Nam lại không biết được rằng đáp án này có phải là chính xác hay không nên đã nhờ bạn tính toán và sau đó sẽ so sánh 2 kết quả với nhau. Hãy giúp Nam kiểm tra kết quả!
Input format
- Dòng đầu tiên là số nguyên n (~2 \leq n \leq 10^5~)
- Dòng thứ hai chứa n số nguyên dương ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 10^4~)
Output format
- In ra duy nhất 1 số thực tổng chiều dài nhỏ nhất của các tấm gỗ
- Câu trả lời sẽ được chấp nhận nếu sai số ~\leq -10^6~
Constraints
Subtask 1 (gồm 30% số điểm): ~n \leq 15 ~, ~a_i \leq 100~
Subtask 2 (gồm 70% số điểm): ~n \leq 10^5~, ~a_i \leq 10^4~
Sample Input 1:
2
1 1
Sample Output 1:
1.000000
Sample Input 2:
2
3 4
Sample Output 2:
1.414214
Giải thích ví dụ
Sample test 1
Có 1 cách xếp duy nhất:
- (1 1): ~\sqrt{(1-1)^2 + 1}~ = 1
Tổng chiều dài cần dùng nhỏ nhất là 1.000000.
Sample test 2
Có tổng cộng 2 cách xếp:
- (3 4) : ~\sqrt{(3-4)^2 + 1}~ = 1.414214
- (4 3) : ~\sqrt{(4-3)^2 + 1}~ = 1.414214
Tổng chiều dài cần dùng nhỏ nhất là 1.414214.
Comments