Trên một máy tính đặc biệt, thời gian để thực hiện việc tính tổng của hai số nguyên dương trên máy tính là phụ thuộc vào độ lớn của chúng. Trung bình để cộng hai số nguyên dương a và b ta phải trả chi phí thời gian có giá trị bằng 5% giá trị của tổng hai số này (a + b). Giả sử ta cần phải tính tổng của N số nguyên dương cho trước. Dễ thấy là có nhiều cách tổ chức thực hiện công việc tính toán này, mỗi cách đòi hỏi chi phí thời gian khác nhau.

Chẳng hạn như cần tính tổng các số 10, 11, 12, 13. Ta có thể thực hiện lần lượt:

• Cộng 10 và 11 (mất chi phí 1.05),
• Kết quả thu được đem cộng với 12 (mất chi phí 1.65),
• Và cuối cùng cộng với 13 (mất chi phí 2.3).

Tổng chi phí theo cách thực hiện này là 5.

Một cách thực hiện khác là:

• Cộng 10 và 11 (1.05),
• Tiếp đến cộng 12 với 13 (mất chi phí 1.25),
• Cuối cùng cộng hai kết quả thu được (mất chi phí 2.3).

Như vậy chi phí tổng cộng theo cách thứ hai là 4.6.

Yêu cầu:
Cho dãy gồm N số nguyên dương. Cần tìm cách tính tổng của các số này với tổng chi phí thời gian là nhỏ nhất.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương N (~2 ≤ N ≤ 15000~).
• Trong các dòng tiếp theo ghi N số nguyên dương mà ta cần tính tổng, hai số liên tiếp được ghi cách nhau bởi ít nhất một dấu cách hoặc dấu xuống dòng.

Dữ liệu ra:

Ghi ra tổng chi phí theo cách thực hiện tính tổng tìm được. Kết quả được ghi với hai chữ số sau dấu chấm thập phân.

Ví dụ:

SUMATION.INP

4
10 11 12 13

SUMATION.OUT

4.60

SUMATION.INP

2
3 3

SUMATION.OUT

0.30

ĐỀ DỰ PHÒNG

Tài liệu tham khảo