Vào tháng 11 năm 2025, Hoa Kỳ đã đúc những đồng xu một xu (penny) cuối cùng. Canada đã ngừng đúc tiền xu từ năm 2012.
Hàng tỷ đồng xu vẫn đang lưu thông, nhưng chúng dự kiến sẽ dần biến mất theo thời gian. Các cửa hàng vẫn tiếp tục định giá sản phẩm theo đơn vị xu, vì các giao dịch thẻ tín dụng được xử lý chính xác đến từng xu. Tuy nhiên, đối với các giao dịch tiền mặt, các cửa hàng dự kiến sẽ làm tròn đến đơn vị nickel (năm xu) gần nhất. Cụ thể, nếu chữ số cuối cùng của tổng hóa đơn là 3, 4, 8 hoặc 9 xu, tổng số tiền sẽ được làm tròn lên; nếu là 1, 2, 6 hoặc 7 xu, tổng số tiền sẽ được làm tròn xuống. Các giao dịch có tổng tiền kết thúc bằng 0 hoặc 5 xu sẽ không bị làm tròn.
Bạn nhận ra rằng điều này tạo ra một cơ hội. Nếu bạn thanh toán bằng tiền mặt và sắp xếp, nhóm các món hàng của mình một cách hợp lý, bạn có thể trả ít hơn một chút cho mọi thứ mình mua! Cho biết giá của từng món hàng bạn muốn mua tính bằng xu, hãy xác định số tiền tối đa bạn có thể tiết kiệm được bằng cách chỉ thanh toán bằng tiền mặt và sắp xếp, nhóm các món hàng một cách tối ưu, so với tổng giá tiền không làm tròn nếu bạn mua tất cả các món hàng bằng thẻ tín dụng.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên duy nhất $N$ ($1 \le N \le 3 \cdot 10^5$), số lượng món hàng bạn dự định mua.
Dòng tiếp theo chứa $N$ số nguyên cách nhau bởi dấu cách $p_i$ ($1 \le p_i \le 3000$), giá của các món hàng tính bằng xu.
Dữ liệu ra
In ra một số nguyên duy nhất: sự chênh lệch giữa tổng giá tiền khi thanh toán bằng thẻ tín dụng (không làm tròn) và tổng chi phí thấp nhất có thể đạt được bằng cách thanh toán tiền mặt và nhóm các món hàng một cách tối ưu.
Ghi chú
Đối với ví dụ đầu tiên, một cách nhóm các món hàng tối ưu là: $\{78, 999, 350\}, \{59, 173, 2995, 350\}, \{882, 298\}, \{1096\}, \{497\}$.
Giá của mỗi nhóm lần lượt là 1427, 3577, 1180, 1096, 497 và do đó tổng chênh lệch là: $(1427 + 3577 + 1180 + 1096 + 497) - (1425 + 3575 + 1180 + 1095 + 495) = 7$.
Bạn tiết kiệm được 7 xu bằng cách nhóm các món hàng một cách tối ưu thành nhiều giao dịch tiền mặt thay vì thanh toán tất cả bằng thẻ tín dụng.
Ví dụ
Ví dụ 1
11 78 59 90 999 173 882 1096 2995 298 497 350
7
Ví dụ 2
2 199 299
-2