1954.md (8499B)
1 Source: https://codeforces.com/blog/entry/128421 2 3 [1954A - Painting the Ribbon](/contest/1954/problem/A "Educational Codeforces Round 164 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n, m, k = map(int, input().split()) 17 max_color = (n + m - 1) / m 18 if max_color + k >= n: 19 print('NO') 20 else: 21 print('YES') 22 ``` 23 24 [1954B - Make It Ugly](/contest/1954/problem/B "Educational Codeforces Round 164 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (awoo)** 33 34 ``` 35 for _ in range(int(input())): 36 n = int(input()) 37 a = list(map(int, input().split())) 38 lst = -1 39 ans = n 40 for i in range(n): 41 if a[i] != a[0]: 42 ans = min(ans, i - lst - 1) 43 lst = i 44 ans = min(ans, n - lst - 1) 45 if ans == n: 46 print(-1) 47 else: 48 print(ans) 49 ``` 50 51 [1954C - Long Multiplication](/contest/1954/problem/C "Educational Codeforces Round 164 (Rated for Div. 2)") 52 53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 54 55 **Tutorial** 56 57 Tutorial is loading... 58 59 **Solution (Neon)** 60 61 ``` 62 #include <bits/stdc++.h> 63 64 using namespace std; 65 66 int main() { 67 int t; 68 cin >> t; 69 while (t--) { 70 string x, y; 71 cin >> x >> y; 72 int n = x.size(); 73 bool f = false; 74 for (int i = 0; i < n; ++i) { 75 if ((x[i] > y[i]) == f) swap(x[i], y[i]); 76 f |= (x[i] != y[i]); 77 } 78 cout << x << '\n' << y << '\n'; 79 } 80 } 81 ``` 82 83 [1954D - Colored Balls](/contest/1954/problem/D "Educational Codeforces Round 164 (Rated for Div. 2)") 84 85 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 86 87 **Tutorial** 88 89 Tutorial is loading... 90 91 **Solution (Neon)** 92 93 ``` 94 #include <bits/stdc++.h> 95 96 using namespace std; 97 98 const int MOD = 998244353; 99 100 int add(int x, int y) { 101 x += y; 102 if (x >= MOD) x -= MOD; 103 return x; 104 } 105 106 int mul(int x, int y) { 107 return x * 1LL * y % MOD; 108 } 109 110 int main() { 111 int n; 112 cin >> n; 113 vector<int> a(n); 114 for (int i = 0; i < n; ++i) cin >> a[i]; 115 int s = accumulate(a.begin(), a.end(), 0); 116 vector<int> dp(s + 1); 117 dp[0] = 1; 118 for (int i = 0; i < n; ++i) 119 for (int j = s - a[i]; j >= 0; --j) 120 dp[j + a[i]] = add(dp[j + a[i]], dp[j]); 121 int ans = 0; 122 for (int j = 0; j <= s; ++j) 123 ans = add(ans, mul((j + 1) / 2, dp[j])); 124 for (int i = 0; i < n; ++i) 125 for (int j = 0; j < a[i]; ++j) 126 ans = add(ans, mul(a[i] - (a[i] + j + 1) / 2, dp[j])); 127 cout << ans << '\n'; 128 } 129 ``` 130 131 [1954E - Chain Reaction](/contest/1954/problem/E "Educational Codeforces Round 164 (Rated for Div. 2)") 132 133 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 134 135 **Tutorial** 136 137 Tutorial is loading... 138 139 **Solution 1 (awoo)** 140 141 ``` 142 #include <bits/stdc++.h> 143 144 #define forn(i, n) for (int i = 0; i < int(n); i++) 145 146 using namespace std; 147 148 int divup(int a, int b){ 149 return (a + b - 1) / b; 150 } 151 152 int main() { 153 cin.tie(0); 154 ios::sync_with_stdio(false); 155 int n; 156 cin >> n; 157 vector<int> a(n); 158 forn(i, n) cin >> a[i]; 159 int mx = *max_element(a.begin(), a.end()); 160 vector<long long> ans(mx + 1); 161 forn(i, n){ 162 int coef = 0; 163 if (i == 0 || a[i] > a[i - 1]) ++coef; 164 if (i + 1 < n && a[i] < a[i + 1]) --coef; 165 int r = a[i]; 166 ans[r] += coef; 167 while (r > 0){ 168 int val = divup(a[i], r); 169 int l = divup(a[i], val); 170 ans[l - 1] += coef * val; 171 ans[r] -= coef * val; 172 r = l - 1; 173 } 174 } 175 forn(i, mx) ans[i + 1] += ans[i]; 176 forn(i, mx) cout << ans[i] << ' '; 177 cout << '\n'; 178 return 0; 179 } 180 ``` 181 182 **Solution 2 (awoo)** 183 184 ``` 185 #include <bits/stdc++.h> 186 187 #define forn(i, n) for (int i = 0; i < int(n); i++) 188 189 using namespace std; 190 191 int main() { 192 cin.tie(0); 193 ios::sync_with_stdio(false); 194 int n; 195 cin >> n; 196 vector<int> a(n); 197 forn(i, n) cin >> a[i]; 198 int mx = *max_element(a.begin(), a.end()); 199 vector<long long> pr(mx + 1); 200 forn(i, n){ 201 int coef = 0; 202 if (i == 0 || a[i] > a[i - 1]) ++coef; 203 if (i + 1 < n && a[i] < a[i + 1]) --coef; 204 pr[a[i]] += coef; 205 } 206 forn(i, mx) pr[i + 1] += pr[i]; 207 for (int k = 1; k <= mx; ++k){ 208 long long ans = 0; 209 for (int l = 1, val = 1; l <= mx; l += k, ++val) 210 ans += val * 1ll * (pr[min(mx, l + k - 1)] - pr[l - 1]); 211 cout << ans << ' '; 212 } 213 cout << '\n'; 214 return 0; 215 } 216 ``` 217 218 [1954F - Unique Strings](/contest/1954/problem/F "Educational Codeforces Round 164 (Rated for Div. 2)") 219 220 Idea: [adedalic](/profile/adedalic "International Master adedalic") 221 222 **Tutorial** 223 224 Tutorial is loading... 225 226 **Solution (adedalic)** 227 228 ``` 229 #include<bits/stdc++.h> 230 231 using namespace std; 232 233 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 234 #define sz(a) int((a).size()) 235 236 typedef long long li; 237 typedef pair<int, int> pt; 238 239 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 240 return out << "(" << p.x << ", " << p.y << ")"; 241 } 242 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 243 fore(i, 0, sz(v)) { 244 if(i) out << " "; 245 out << v[i]; 246 } 247 return out; 248 } 249 250 const int MOD = int(1e9) + 7; 251 int add(int a, int b) { 252 a += b; 253 while (a >= MOD) 254 a -= MOD; 255 while (a < 0) 256 a += MOD; 257 return a; 258 } 259 void upd(int &ans, int val) { 260 ans = add(ans, val); 261 } 262 int mul(int a, int b) { 263 return int(a * 1ll * b % MOD); 264 } 265 int binPow(int a, int k) { 266 int ans = 1; 267 while (k > 0) { 268 if (k & 1) 269 ans = mul(ans, a); 270 a = mul(a, a); 271 k >>= 1; 272 } 273 return ans; 274 } 275 276 const int N = 3055; 277 int f[N], invf[N]; 278 279 void precalcFact() { 280 f[0] = invf[0] = 1; 281 fore (i, 1, N) { 282 f[i] = mul(f[i - 1], i); 283 invf[i] = binPow(f[i], MOD - 2); 284 } 285 } 286 int C(int n, int k) { 287 if (k < 0 || k > n) 288 return 0; 289 return mul(f[n], mul(invf[k], invf[n - k])); 290 } 291 292 int n, c, k; 293 294 inline bool read() { 295 if(!(cin >> n >> c >> k)) 296 return false; 297 return true; 298 } 299 300 int d[N][N], sum[N][N]; 301 302 // d[z][l] - number of strings of length l, with z zeroes and blocks of 1-s shorter than mx 303 void precalcShort(int mx) { 304 memset(d, 0, sizeof d); 305 d[0][0] = 1; 306 fore (z, 0, n) { 307 fore (l, 0, n) { 308 if (d[z][l] == 0) 309 continue; 310 upd(d[z + 1][l + 1], +d[z][l]); 311 upd(d[z + 1][min(n, l + mx) + 1], -d[z][l]); 312 } 313 fore (l, 0, n + 1) 314 upd(d[z + 1][l + 1], d[z + 1][l]); 315 } 316 317 memset(sum, 0, sizeof sum); 318 fore (z, 0, n + 1) fore (l, 0, n + 1) 319 sum[z][l + 1] = add(sum[z][l], d[z][l]); 320 321 } 322 323 //[lf, rg) 324 int getSum(int z, int lf, int rg) { 325 if (z < 0 || z > n || lf >= rg) 326 return 0; 327 return add(sum[z][rg], -sum[z][lf]); 328 } 329 330 // cnt[g] is a number of x <= n with gcd(x, n) = g 331 vector<int> precalcCnt(int n) { 332 vector<int> cnt(n + 1, 0); 333 fore (x, 1, n + 1) 334 cnt[gcd(x, n)]++; 335 return cnt; 336 } 337 338 int calcFixedPoints(int g) { 339 if (c >= g) 340 return c + k >= n; 341 342 int cntOnes = (c + k) / (n / g); 343 int cntZeros = g - cntOnes; 344 345 int all = 0; 346 fore (ones, 0, cntOnes + 1) 347 upd(all, C(g, ones)); 348 349 int bad = 0; 350 fore (pref, 0, c) { 351 int minZeros = max(0, cntZeros - 1); 352 int minMid = g - c; 353 int sufLen = g - pref - 1; 354 fore (z, minZeros, sufLen + 1) 355 upd(bad, getSum(z, minMid, sufLen + 1)); 356 } 357 return add(all, -bad); 358 } 359 360 inline void solve() { 361 precalcFact(); 362 precalcShort(c); 363 auto cnt = precalcCnt(n); 364 365 int ans = 0; 366 fore (g, 1, n + 1) { 367 if (n % g != 0) 368 continue; 369 370 int cntFP = calcFixedPoints(g); 371 // cerr << "g = " << g << " += " << cnt[g] << " * " << cntFP << endl; 372 upd(ans, mul(cnt[g], cntFP)); 373 } 374 375 // cerr << "ans/n = " << ans << " " << n << endl; 376 cout << mul(ans, binPow(n, MOD - 2)) << endl; 377 } 378 379 int main() { 380 #ifdef _DEBUG 381 freopen("input.txt", "r", stdin); 382 int tt = clock(); 383 #endif 384 ios_base::sync_with_stdio(false); 385 cin.tie(0), cout.tie(0); 386 cout << fixed << setprecision(15); 387 388 if(read()) { 389 solve(); 390 391 #ifdef _DEBUG 392 cerr << "TIME = " << clock() - tt << endl; 393 tt = clock(); 394 #endif 395 } 396 return 0; 397 } 398 ```