On THDZ Conference
Xem PDFMột cái hồ có chu vi \(M\). Ta định nghĩa "điểm \(x\)" là vị trí cách một túp lều (ở mốc 0) một khoảng \(x\) theo chiều kim đồng hồ (\(0 \le x < M\)).
Có \(N\) người, người thứ \(i\) đang đứng ở điểm \(A_i\). Lưu ý: Nhiều người có thể đứng cùng một điểm.
Cho một số nguyên \(C\) (với \(1 \le C \le N\)).
Với mỗi \(i\) từ \(0\) đến \(M-1\), ta định nghĩa giá trị \(X_i\) như sau:
- H bắt đầu ở điểm \((i + 0.5)\) và di chuyển theo chiều kim đồng hồ.
- H tiếp tục di chuyển chừng nào tổng số người anh ấy đã gặp (tính từ lúc bắt đầu) vẫn còn nhỏ hơn \(C\).
- Anh ấy sẽ dừng lại ngay khi tổng số người đã gặp lớn hơn hoặc bằng \(C\). Phép "gặp" một người tại điểm \(y\) nghĩa là H đến chính xác điểm \(y\).
- \(X_i\) là tổng số người Takahashi đã gặp tính đến thời điểm anh ấy dừng lại. (Lưu ý: Nếu anh ấy dừng tại một điểm có nhiều người, \(X_i\) có thể lớn hơn \(C\)).
Yêu cầu: Tính tổng của tất cả các giá trị \(X_i\), tức là \(\sum_{i=0}^{M-1} X_i\).
Input
- Dòng đầu tiên chứa ba số nguyên \(N, M, C\) (\(1 \le N \le 5 \times 10^5\), \(1 \le M \le 10^{12}\), \(1 \le C \le N\)).
- Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(0 \le A_i \le M-1\)), là vị trí của \(N\) người.
Output
- In ra một dòng duy nhất chứa tổng \(\sum_{i=0}^{M-1} X_i\).
Examples
Test 1
Input
5 3 2
1 2 1 0 1Output
9Explanation
Ta có \(N=5\) người, chu vi \(M=3\), và điều kiện dừng \(C=2\).
Các vị trí người: ba người ở điểm 1, một người ở điểm 2, một người ở điểm 0.
Vì \(M=3\), ta cần tính \(X_0, X_1, X_2\).
- Với \(i=0\): Bắt đầu ở 0.5. Di chuyển theo chiều kim đồng hồ.
- Gặp 3 người ở điểm 1. Tổng số người đã gặp = 3.
- Vì \(3 \ge C=2\), anh ấy dừng lại.
- \(X_0 = 3\).
- Với \(i=1\): Bắt đầu ở 1.5. Di chuyển theo chiều kim đồng hồ.
- Gặp 1 người ở điểm 2. Tổng số người đã gặp = 1.
- Vì \(1 < C=2\), anh ấy đi tiếp.
- Gặp 1 người ở điểm 0 (sau khi qua mốc 2). Tổng số người đã gặp = \(1 + 1 = 2\).
- Vì \(2 \ge C=2\), anh ấy dừng lại.
- \(X_1 = 2\).
- Với \(i=2\): Bắt đầu ở 2.5. Di chuyển theo chiều kim đồng hồ.
- Gặp 1 người ở điểm 0. Tổng số người đã gặp = 1.
- Vì \(1 < C=2\), anh ấy đi tiếp.
- Gặp 3 người ở điểm 1. Tổng số người đã gặp = \(1 + 3 = 4\).
- Vì \(4 \ge C=2\), anh ấy dừng lại.
- \(X_2 = 4\).
Tổng cần tìm là \(X_0 + X_1 + X_2 = 3 + 2 + 4 = 9\).
Test 2
Input
1 1000000000000 1
1Output
1000000000000Explanation
Ta có \(N=1\) người, chu vi \(M=10^{12}\), và điều kiện dừng \(C=1\). Có một người duy nhất ở điểm 1.
Ta cần tính \(X_i\) cho \(i = 0\) đến \(M-1\).
Với mọi vị trí bắt đầu \(i\) (từ \(0\) đến \(M-1\)), Takahashi sẽ luôn di chuyển cho đến khi gặp người duy nhất ở điểm 1.
Khi gặp người đó, tổng số người đã gặp là 1. Vì \(1 \ge C=1\), anh ấy dừng lại.
Do đó, \(X_i = 1\) với mọi \(i\).
Tổng cần tìm là \(\sum_{i=0}^{M-1} X_i = \underbrace{1 + 1 + \dots + 1}_{M \text{ lần}} = M = 10^{12}\).
Bình luận