LQDOJ Contest #8 - Bài 2 - Tất Niên

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
shiba
Dạng bài
Điểm: 800 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Phường LQDOJ Có \(N\) gia đình sinh sống. Nhà thứ \(i\) có tọa độ là \(x_i\).

Chủ tịch UBND phường quyết định tổ chức lễ tất niên cuối năm và tất cả các gia đình đều phải tham gia lễ tất niên này. Lễ tất niên này có thể tổ chức tại một ngôi nhà \(m\) bất kì (\(m\) phải là số nguyên), nhà thứ \(i\) cần phải trả \((x_i - m)^2\) đồng.

Yêu cầu: Bạn hãy lập trình tính tổng số tiền ít nhất có thể mà tất cả các nhà phải trả.

Input

  • Dòng đầu tiên chứa số nguyên dương \(N\) \((1 \le N \le 10^6)\).
  • Dòng tiếp theo chứa \(N\) số nguyên dương \(x_1,x_2,...,x_N\) \((1 \le x_i \le 10^6)\).

Output

  • In ra kết quả bài toán sau khi thực hiện yêu cầu đề bài.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): Có \(N \le 5000\).

  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
3
1 2 3
Output 
2
Note
  • Nếu ta chọn ngôi nhà có tọa độ \(m = 2\) thì nhà thứ \(1\) cần phải trả \((1-2)^2 = 1\) đồng, nhà thứ hai cần phải trả \((2-2)^2 = 0\) đồng, nhà thứ ba phải trả \((3-2)^2 = 1\) đồng. Vậy số tiền tối thiểu cần phải trả của tất cả các nhà là \(1+0+1 = 2\) đồng.

Bình luận


  • 0
    quan215833    8:58 p.m. 11 Tháng 3, 2024

    đọc kĩ đề đi lừa đảo :))


    • 0
      nd24052009    3:23 p.m. 27 Tháng 6, 2024 ← đã chỉnh sửa

      chỉ mik chỗ lừa với ạ =)) chứ ko hiểu sao for trâu mà dược có mỗi 2/100 =( hay là nhà thứ m không phải là a[m] mà là m nhỉ?


      • 5
        Rayokad    8:54 p.m. 27 Tháng 6, 2024 ← chỉnh sửa 3

        Gợi ý: m là làm tròn của sum/n (trung bình cộng) của dãy số, để dễ hiểu hơn thì trong python sẽ là round(sum(ds)/n)
        m là vậy nhưng kq ko phải vậy
        kq là tổng của \((X[i]-m)^2\) với X[i] là các phần tử của dãy


        • 0
          nd24052009    10:19 p.m. 27 Tháng 6, 2024

          Ủa mà bạn là ai vậy?? =))

    1 bình luận nữa