// 想定解法(改良版) #include #define MAX_N 100000 #define MAX_L 10000 #define MAX_X 5000 int n, l, x[MAX_N]; int abs(int a) { return 0 < a ? a : -a; } int main(void) { int i; scanf("%d%d", &n, &l); if( ! ( 1 <= n && n <= MAX_N ) ) { return 0; } // assert if( ! ( 1 <= l && l <= MAX_L ) ) { return 0; } // assert // 色々と面倒なので, x[i] には上から i 番目を入れる x[n - 1] = 0; for(i = n - 2; 0 <= i; i--) { scanf("%d", &x[i]); if( ! ( abs( x[i] ) <= MAX_X ) ) { return 0; } // assert } // sum は i より上の座標の和, i より上の重心座標は sum/i int counter = 0, sum = 0; for(i = 1; i < n; i++) { sum += x[i - 1]; if( l <= abs(x[i - 1] - x[i]) ) { counter = -1; break; } if( // l/2 <= abs( sum/i - x[i] ) の両辺に 2i を掛けた i * l <= abs( 2 * sum - 2 * i * x[i] ) || i * l <= abs( 2 * sum - 2 * i * x[i - 1] ) ) { counter++; } } printf("%d\n", counter); return 0; }