Có N người ở các vị trí nguyên Xi. Nếu chọn điểm hẹn nguyên P, chi phí của người i là (Xi−P)2. Hãy tìm tổng chi phí nhỏ nhất.
Input
Dòng đầu chứa N. Dòng thứ hai chứa N số nguyên Xi.
Output
In giá trị nhỏ nhất của ∑(Xi−P)2 trên mọi số nguyên P.
Constraints
1≤N≤100.
1≤Xi≤100.
P là một số nguyên.
Scoring
Subtask 1 (50% số điểm): N≤20.
Subtask 2 (50% số điểm): Không có giới hạn bổ sung.
Example
Test 1
Input
3
1 4 7
Output
18
Giải thích: Chọn P=4 cho chi phí (1−4)2+(4−4)2+(7−4)2=9+0+9=18. Các vị trí nguyên khác đều cho tổng lớn hơn, nên đáp án là 18.
Lời giải tóm tắt
Ý tưởng: Duyệt P từ 1 đến 100. Với từng vị trí ứng viên, cộng bình phương khoảng cách của mọi người và lấy tổng nhỏ nhất.
Chứng minh tính đúng đắn: Một điểm tối ưu không cần nằm ngoài đoạn từ vị trí nhỏ nhất đến lớn nhất, nên miền 1..100 bao phủ mọi ứng viên cần thiết. Thuật toán tính đúng chi phí cho từng ứng viên và lấy nhỏ nhất.
Độ phức tạp:O(100N) thời gian và O(N) bộ nhớ.
Lỗi cài đặt thường gặp: Dùng trung vị, vốn tối ưu cho tổng khoảng cách tuyệt đối chứ không phải bình phương.
Lỗi cài đặt thường gặp: Chỉ thử phần nguyên dưới của trung bình.