Average
View as PDFSau cuộc thương lượng đổi ao sâu cá mè lấy quạt mo của Phú ông và Bờm không thành, Phú ông nhờ Bờm bán hết số cá trong ao và nếu giá bán cao hơn giá của Phú ông đưa ra thì số tiền lãi sẽ thuộc về Bờm. Trong ao cá có N con cá được đánh số thứ tự từ ~1~ đến ~N~, con cá thứ ~i~ ~(i=1..N)~ có giá là ~X_i~ đồng. Bờm quyết định tính lại giá bán mới sao cho tất cả các con cá đều bán với một giá như nhau. Giá mới sẽ là trung bình cộng giá hiện tại của ~N~ con cá nhưng với cách tính trung bình cộng do Bờm nghĩ ra như sau:
- Lấy hai số ~X_i~ và ~X_j~ ~(1 ≤ i, j ≤ N; i ≠ j)~ ra khỏi dãy số và thay vào dãy số một số mới là ~(X_i~ + ~X_j)/2~.
- Tiếp tục thực hiện cách tính như trên cho đến khi dãy số chỉ còn một số duy nhất và số đó chính là giá mới của mỗi con cá mà Bờm sẽ bán.
Yêu cầu: Bạn hãy giúp Bờm thực hiện cách tính trên để có được tiền lãi cao nhất sau khi bán hết tất cả số cá trong ao.
Dữ liệu vào gồm hai dòng:
- Dòng đầu ghi số nguyên ~N~ ~(1 ≤ N ≤ 10^5)~.
- Dòng thứ hai ghi số ~N~ số nguyên dương ~X_1~, ~X_2~, …, ~X_N~ là giá hiện tại của N con cá tương ứng, mỗi số có giá trị không vượt quá ~10^9~.
Giữa các số trên cùng dòng được ghi cách nhau một dấu cách.
Kết quả: Một số thực với độ chính xác 5 chữ số thập phân là tiền lãi cao nhất sau khi bán hết số cá theo yêu cầu bài toán.
Ví dụ 1:
INPUT
4
2 4 5 2
OUTPUT
3.00000
Ví dụ 2:
INPUT
3
5 5 4
OUTPUT
0.25000
Giới hạn:
- Có 60% số test với ~N ≤ 10^3~.
- Có 40% số test với ~10^3 < N ≤ 10^5~.
Comments
Tip to AC: if(s2*n==s1) cout<<0;
hay ta
oh