E. WATERMOV - Chuyển nước

Các bé học sinh trường mầm non SuperKids tỏ ra say mê với các trò chơi đòi hỏi tư duy thuật toán chuyên nghiệp. Nhân dịp đến thăm trường, giáo sư X bày ra một trò chơi cho các bạn nhỏ tại đây.

Ban đầu, người chơi được cho thùng nước đánh số từ tới . Thùng thứ có lít nước. Người chơi được quyền múc một lượng nước bất kỳ từ một thùng chuyển sang thùng liền sau (chuyển từ thùng sang thùng với tùy chọn thỏa mãn ). Năng lượng tiêu tốn cho thao tác này đúng bằng lượng nước được chuyển (có thể không phải là số nguyên).

Nhiệm vụ của người chơi là phải làm cho lượng nước trong các thùng sắp xếp thứ tự không giảm, tức là:

Yêu cầu: Hãy tìm phương án chơi sao cho tổng năng lượng tiêu tốn là ít nhất.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương ;
• Dòng thứ hai chứa số nguyên không âm cách nhau bởi dấu cách.

Dữ liệu ra:

• Ghi ra một số thực duy nhất với chữ số sau dấu chấm thập phân là tổng năng lượng tiêu tốn nếu các bé chơi theo phương án của bạn.

Ví dụ:

Dữ liệu vào:

6
1 3 0 0 3 0

Dữ liệu ra:

4.5

Giải thích:

Ta sẽ chuyển nước để được lượng nước trong các thùng là :

• Chuyển lít từ thùng sang thùng ;
• Chuyển lít từ thùng sang thùng ;
• Chuyển lít từ thùng sang thùng .