2276.md (10597B)
1 Source: https://codeforces.com/blog/entry/157752 2 3 [2276A - Perfect Sandwiches](/contest/2276/problem/A "Educational Codeforces Round 195 (Rated for Div. 2)") 4 5 Author: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for _ in range(t): 16 a, b = map(int, input().split()) 17 if b >= a: 18 print(-1) 19 else: 20 print(min(b, a - b)) 21 ``` 22 23 [2276B - Replace and Compress](/contest/2276/problem/B "Educational Codeforces Round 195 (Rated for Div. 2)") 24 25 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest") 26 27 **Tutorial** 28 29 Tutorial is loading... 30 31 **Solution (BledDest)** 32 33 ``` 34 t = int(input()) 35 for _ in range(t): 36 s = input() 37 ans = 1 38 if "010" in s or "101" in s: 39 ans += 1 40 if "000" in s or "111" in s: 41 ans += 1 42 print(ans) 43 ``` 44 45 [2276C - Subarrays](/contest/2276/problem/C "Educational Codeforces Round 195 (Rated for Div. 2)") 46 47 Author: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 48 49 **Tutorial** 50 51 Tutorial is loading... 52 53 **Solution (BledDest)** 54 55 ``` 56 t = int(input()) 57 for _ in range(t): 58 n, k = map(int, input().split()) 59 a = list(map(int, input().split())) 60 61 p = [0 for i in range(n+1)] 62 for i in range(n): 63 p[i+1] = (p[i]+a[i]) % k 64 65 ans = 0 66 cnt = [0 for i in range(k)] 67 for i in range(k+1, n+1): 68 cnt[p[i-k-1]] += 1 69 ans += cnt[p[i]] 70 71 print(ans) 72 ``` 73 74 [2276D - Caveman](/contest/2276/problem/D "Educational Codeforces Round 195 (Rated for Div. 2)") 75 76 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest") 77 78 **Tutorial** 79 80 Tutorial is loading... 81 82 **Solution (BledDest)** 83 84 ``` 85 #include<bits/stdc++.h> 86 87 using namespace std; 88 89 void solve() 90 { 91 int n, m; 92 cin >> n >> m; 93 vector<int> d(n); 94 for(int i = 0; i < m; i++) 95 { 96 int x, y; 97 cin >> x >> y; 98 x--; 99 y--; 100 d[x]++; 101 d[y]++; 102 } 103 sort(d.begin(), d.end()); 104 if(d[0] == 0) 105 cout << "Brain Melt\n"; 106 else if(d[n - 1] == n - 1 && d[n - 2] == 1) 107 cout << 2 << "\n"; 108 else 109 cout << "Many\n"; 110 } 111 112 int main() 113 { 114 ios_base::sync_with_stdio(0); 115 cin.tie(0); 116 int t; 117 cin >> t; 118 for(int i = 0; i < t; i++) 119 solve(); 120 } 121 ``` 122 123 [2276E - Good Substrings](/contest/2276/problem/E "Educational Codeforces Round 195 (Rated for Div. 2)") 124 125 Author: [Roms](/profile/Roms "Master Roms") 126 127 **Tutorial** 128 129 Tutorial is loading... 130 131 **Solution (Roms)** 132 133 ``` 134 #include <bits/stdc++.h> 135 136 using namespace std; 137 138 int t; 139 140 int main() { 141 const string s25 = "2025", s26 = "2026"; 142 143 cin >> t; 144 for (int tc = 0; tc < t; ++tc) { 145 int n; 146 string s; 147 cin >> n >> s; 148 149 vector <vector <int>> nxt(n, vector <int> (10)); 150 vector <int> cur(10, n); 151 152 for (int i = n - 1; i >= 0; --i) { 153 cur[s[i] - '0'] = i; 154 for (int j = 0; j < 10; ++j) 155 nxt[i][j] = cur[j]; 156 } 157 158 vector <int> d(n + 1); 159 vector <int> dd(n + 1); 160 161 for (int l = 0; l < n; ++l) { 162 int r25 = l, r26 = l; 163 int i25 = 0, i26 = 0; 164 165 while(i25 < s25.size() && r25 < n) { 166 int x = s25[i25++] - '0'; 167 r25 = nxt[r25][x]; 168 } 169 170 while(i26 < s26.size() && r26 < n) { 171 int x = s26[i26++] - '0'; 172 r26 = nxt[r26][x]; 173 } 174 175 int cnt = n - l; 176 d[l] += cnt; 177 --dd[l + 1]; 178 179 if (r25 < r26) { 180 // bad == [r25..r26-1] 181 cnt = r26 - r25; 182 d[l] -= cnt; 183 ++dd[r25 + 1]; 184 //--dd[r26]; 185 if(r26 < n) 186 --dd[r26 + 1]; 187 } 188 } 189 190 vector <int> ans(n); 191 long long sum = 0, add = 0; 192 for (int i = 0; i < n; ++i) { 193 sum += d[i]; 194 add += dd[i]; 195 sum += add; 196 cout << sum << ' '; 197 } 198 cout << endl; 199 } 200 return 0; 201 } 202 ``` 203 204 [2276F - Permutation Coloring Game](/contest/2276/problem/F "Educational Codeforces Round 195 (Rated for Div. 2)") 205 206 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest") 207 208 **Tutorial** 209 210 Tutorial is loading... 211 212 **Solution (BledDest)** 213 214 ``` 215 #include<bits/stdc++.h> 216 217 using namespace std; 218 219 const int INF = 1e9; 220 221 void upd(int& x, int y) 222 { 223 if(x > y) x = y; 224 } 225 226 void solve() 227 { 228 int n, k; 229 cin >> n >> k; 230 vector<int> p(n); 231 for(int i = 0; i < n; i++) 232 { 233 cin >> p[i]; 234 p[i]--; 235 } 236 237 vector<bool> used(n); 238 vector<int> len; 239 for(int i = 0; i < n; i++) 240 { 241 if(!used[i]) 242 { 243 used[i] = true; 244 int cur_len = 1; 245 int j = p[i]; 246 while(!used[j]) 247 { 248 used[j] = true; 249 cur_len++; 250 j = p[j]; 251 } 252 len.push_back(cur_len); 253 } 254 } 255 sort(len.begin(), len.end()); 256 reverse(len.begin(), len.end()); 257 258 if(k == 1) 259 { 260 if(len[0] >= 3) 261 cout << "Bob\n"; 262 else if(len[0] == 1 || n % 2 == 1) 263 cout << "Alice\n"; 264 else 265 cout << "Bob\n"; 266 } 267 else if(len[0] > k + 1) 268 { 269 cout << "Bob\n"; 270 } 271 else if(len[0] == k + 1) 272 { 273 if(len.size() > 1 && len[1] == k + 1) 274 { 275 cout << "Bob\n"; 276 } 277 else 278 { 279 int must_remove = 0; 280 int cnt1 = 0; 281 for(int i = 1; i < len.size(); i++) 282 { 283 if(len[i] > 1) 284 must_remove += len[i]; 285 else cnt1++; 286 } 287 int alice_move = must_remove + cnt1 % (k + 1); 288 if(alice_move > k || alice_move == 0) 289 cout << "Bob\n"; 290 else 291 cout << "Alice\n"; 292 } 293 } 294 else 295 { 296 int m = len.size(); 297 m = min(m, 2 * k); 298 vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(k+1, vector<int>(k + 1, INF))); 299 dp[0][0][0] = 0; 300 for(int i = 0; i < m; i++) 301 for(int j = 0; j <= k; j++) 302 for(int c = 0; c <= k; c++) 303 { 304 if(dp[i][j][c] == INF) continue; 305 bool alice_can = (j + len[i] <= k); 306 bool bob_can = (i - c < k); 307 if(alice_can) 308 upd(dp[i+1][j + len[i]][c + 1], dp[i][j][c]); 309 upd(dp[i+1][j][c], dp[i][j][c] + (bob_can ? len[i] - 1 : 0)); 310 } 311 bool alice_win = false; 312 for(int j = 0; j <= k; j++) 313 for(int c = 0; c <= k; c++) 314 if(dp[m][j][c] <= k) 315 alice_win = true; 316 317 if(alice_win) 318 cout << "Alice\n"; 319 else 320 cout << "Bob\n"; 321 } 322 } 323 324 int main() 325 { 326 ios_base::sync_with_stdio(0); 327 cin.tie(0); 328 int t; 329 cin >> t; 330 for(int i = 0; i < t; i++) 331 solve(); 332 } 333 ``` 334 335 [2276G - Elimination of Players](/contest/2276/problem/G "Educational Codeforces Round 195 (Rated for Div. 2)") 336 337 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest") 338 339 **Tutorial** 340 341 Tutorial is loading... 342 343 **Solution (BledDest)** 344 345 ``` 346 #include<bits/stdc++.h> 347 348 using namespace std; 349 350 const int MOD = 998244353; 351 const int N = 5005; 352 353 int add(int x, int y) 354 { 355 x += y; 356 while(x >= MOD) x -= MOD; 357 while(x < 0) x += MOD; 358 return x; 359 } 360 361 int mul(int x, int y) 362 { 363 return (x * 1ll * y) % MOD; 364 } 365 366 int sub(int x, int y) 367 { 368 return add(x, -y); 369 } 370 371 int binpow(int x, int y) 372 { 373 int z = 1; 374 while(y) 375 { 376 if(y & 1) z = mul(z, x); 377 x = mul(x, x); 378 y >>= 1; 379 } 380 return z; 381 } 382 383 int fact[N]; 384 int inv[N]; 385 386 void precalc() 387 { 388 fact[0] = 1; 389 for(int i = 1; i < N; i++) 390 fact[i] = mul(i, fact[i - 1]); 391 for(int i = 0; i < N; i++) 392 inv[i] = binpow(i, MOD - 2); 393 } 394 395 struct Blocks 396 { 397 int n; 398 vector<int> cutoff_pos; 399 vector<int> pref; 400 vector<int> pref_G; 401 vector<pair<int, int>> a; 402 403 void rebuild() 404 { 405 pref = { 0 }; 406 pref_G = { 0 }; 407 vector<bool> used(n); 408 vector<pair<int, int>> b; 409 cutoff_pos = vector<int>(n, -1); 410 int sign = 1; 411 int cnt = n - 1; 412 for(int i = 0; i < a.size(); i++) 413 { 414 int x = a[i].first; 415 int len = a[i].second; 416 if(used[x]) 417 break; 418 used[x] = true; 419 b.push_back(make_pair(x, len)); 420 cutoff_pos[x] = i; 421 int c = mul(sign, mul(len, fact[cnt])); 422 int c_G = mul(sign, mul(len, fact[cnt - 1])); 423 --cnt; 424 sign = sub(0, sign); 425 pref.push_back(add(pref.back(), c)); 426 pref_G.push_back(add(pref_G.back(), c_G)); 427 } 428 429 a = b; 430 } 431 432 int getF() 433 { 434 return pref.back(); 435 } 436 437 int getG(int x) 438 { 439 if(cutoff_pos[x] == -1) return pref_G.back(); 440 else return pref_G[cutoff_pos[x]]; 441 } 442 443 void append(int x) 444 { 445 if(a.empty() || a[0].first != x) 446 a.insert(a.begin(), make_pair(x, 0)); 447 a[0].second++; 448 rebuild(); 449 } 450 451 Blocks(int n = 0) : n(n) {}; 452 }; 453 454 void solve() 455 { 456 int n; 457 cin >> n; 458 vector<int> a(n - 1); 459 for(int i = 0; i < n - 1; i++) 460 { 461 cin >> a[i]; 462 a[i]--; 463 } 464 Blocks b(n); 465 vector<vector<int>> ans(n - 1, vector<int>(n)); 466 vector<vector<int>> G(n - 1, vector<int>(n)); 467 vector<int> F(n - 1); 468 for(int i = 0; i < n - 1; i++) 469 { 470 int x = a[i]; 471 b.append(x); 472 F[i] = b.getF(); 473 for(int j = 0; j < n; j++) 474 G[i][j] = b.getG(j); 475 for(int j = 0; j < n; j++) 476 { 477 if(a[i] == j) continue; 478 int s = add(fact[n - 1], G[i][j]); 479 if(i > 0) 480 { 481 s = sub(s, G[i - 1][j]); 482 if(a[i - 1] == j) 483 s = add(s, F[i - 1]); 484 } 485 ans[i][j] = s; 486 } 487 } 488 489 long long res = 0; 490 for(int i = 0; i < n - 1; i++) 491 for(int j = 0; j < n; j++) 492 res ^= ans[i][j] * 1ll * (i + 1) * 1ll * (j + 1); 493 cout << res << endl; 494 } 495 496 int main() 497 { 498 precalc(); 499 ios_base::sync_with_stdio(0); 500 cin.tie(0); 501 int t; 502 cin >> t; 503 for(int i = 0; i < t; i++) 504 solve(); 505 } 506 ```