Bridge Building

View as PDF

Submit solution

Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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ả!

ảnh minh họa

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

Please read the guidelines before commenting.


There are no comments at the moment.