#include #include #include #include #include #include #include #include #include // require sort next_permutation count __gcd reverse etc. #include // require abs exit atof atoi #include // require scanf printf #include #include // require accumulate #include // require fabs #include #include #include #include // require setw #include // require stringstream #include // require memset #include // require tolower, toupper #include // require freopen #include // require srand #define rep(i,n) for(int i=0;i<(n);i++) #define ALL(A) A.begin(), A.end() /* No.33 アメーバがたくさん N 個のうち 2個のアメーバ間の距離を格納。N*(N-1)/2 個 このうち |xi - xj | % d != 0 なら xi と xj のアメーバは重ならないから 時間 t まで増え続ける |xi - xj| % d == 0 なら xi と xj のアメーバは |xi - xj|/(2d) 秒後に 重なる。 重なる前までの増え方と重なった後での増え方がちがうので場合分け。 計算量:O(N^2) */ using namespace std; typedef long long ll; typedef pair P; int main() { ios_base::sync_with_stdio(0); int N, D, T; cin >> N >> D >> T; vector X(N, 0 ); rep (i, N ) cin >> X[i]; sort (ALL (X ) ); vector diff (N*(N-1)/2, 0 ); int k = 0; rep (i, N ) for (int j = i+1; j < N; j++ ) diff[k++] = (X[j] - X[i] ); ll res = (ll)N; rep (k, N*(N-1)/2 ){ if (diff[k] % D != 0 ){ res += 2LL*2LL*(ll)T; }else{ ll ct = (ll)diff[k]/(2LL*D ); // 衝突時間 res += 2LL*2LL*ct; if (T >= ct ){ res--; // 衝突した res += 2LL*((ll)T-ct); // 衝突後の増え方 } // end if } // end if } // end rep cout << res << endl; return 0; }