2225.md (13860B)
1 Source: https://codeforces.com/blog/entry/153154 2 3 [2225A - A Number Between Two Others](/contest/2225/problem/A "Educational Codeforces Round 189 (Rated for Div. 2)") 4 5 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution 1 (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 x, y = map(int, input().split()) 17 good = False 18 for z in range(x * 2, y, x): 19 if y % z != 0: 20 good = True 21 break 22 if good: 23 print('YES') 24 else: 25 print('NO') 26 ``` 27 28 **Solution 2 (BledDest)** 29 30 ``` 31 t = int(input()) 32 for i in range(t): 33 x, y = map(int, input().split()) 34 print('YES' if y > 2 * x else 'NO') 35 ``` 36 37 [2225B - Alternating String](/contest/2225/problem/B "Educational Codeforces Round 189 (Rated for Div. 2)") 38 39 Author: [FelixArg](/profile/FelixArg "Master FelixArg") 40 41 **Tutorial** 42 43 Tutorial is loading... 44 45 **Solution (FelixArg)** 46 47 ``` 48 #include <bits/stdc++.h> 49 50 using namespace std; 51 52 #define int long long 53 54 void solve() { 55 string s; 56 cin >> s; 57 int ans = 0; 58 for (int i = 0; i < (int)s.size() - 1; i++){ 59 ans += (s[i] == s[i + 1]); 60 } 61 cout << (ans <= 2 ? "YES\n" : "NO\n"); 62 } 63 64 signed main() 65 { 66 #ifdef FELIX 67 auto _clock_start = chrono::high_resolution_clock::now(); 68 #endif 69 ios_base::sync_with_stdio(false); 70 cin.tie(0); 71 cout.tie(0); 72 73 int tests = 1; 74 cin >> tests; 75 while(tests--){ 76 solve(); 77 } 78 79 #ifdef FELIX 80 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 81 chrono::high_resolution_clock::now() 82 - _clock_start).count() << "ms." << endl; 83 #endif 84 return 0; 85 } 86 ``` 87 88 [2225C - Red-Black Pairs](/contest/2225/problem/C "Educational Codeforces Round 189 (Rated for Div. 2)") 89 90 Author: [FelixArg](/profile/FelixArg "Master FelixArg") 91 92 **Tutorial** 93 94 Tutorial is loading... 95 96 **Solution (FelixArg)** 97 98 ``` 99 #include <bits/stdc++.h> 100 101 using namespace std; 102 103 #define int long long 104 105 const int INF = 1'000'000'007; 106 107 void solve(){ 108 int n; 109 cin >> n; 110 vector<string> d(2); 111 cin >> d[0] >> d[1]; 112 113 vector<int> dp(n + 1, INF); 114 dp[0] = 0; 115 for (int i = 0; i < n; i++){ 116 dp[i + 1] = min(dp[i + 1], dp[i] + (d[0][i] != d[1][i])); 117 if (i + 1 < n){ 118 dp[i + 2] = min(dp[i + 2], dp[i] + (d[0][i] != d[0][i + 1]) + (d[1][i] != d[1][i + 1])); 119 } 120 } 121 122 cout << dp[n] << '\n'; 123 } 124 125 signed main() 126 { 127 #ifdef FELIX 128 auto _clock_start = chrono::high_resolution_clock::now(); 129 #endif 130 ios_base::sync_with_stdio(false); 131 cin.tie(0); 132 cout.tie(0); 133 134 int t = 1; 135 cin >> t; 136 while(t--){ 137 solve(); 138 } 139 140 #ifdef FELIX 141 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 142 chrono::high_resolution_clock::now() 143 - _clock_start).count() << "ms." << endl; 144 #endif 145 return 0; 146 } 147 ``` 148 149 [2225D - Exceptional Segments](/contest/2225/problem/D "Educational Codeforces Round 189 (Rated for Div. 2)") 150 151 Author: [FelixArg](/profile/FelixArg "Master FelixArg") 152 153 **Tutorial** 154 155 Tutorial is loading... 156 157 **Solution (FelixArg)** 158 159 ``` 160 #include<bits/stdc++.h> 161 162 using namespace std; 163 164 #define int long long 165 166 const int MOD = 998'244'353; 167 168 int get0(int x){ 169 return 1ll + (x >= 3 ? (x - 3) / 4 + 1 : 0); 170 } 171 172 int get1(int x){ 173 return (x >= 1 ? (x - 1) / 4 + 1 : 0); 174 } 175 176 void solve(){ 177 int n, x; 178 cin >> n >> x; 179 180 int l0 = get0(x - 1) % MOD; 181 int r0 = (get0(n) - l0) % MOD; 182 int ans = l0 * r0; 183 184 int l1 = get1(x - 1) % MOD; 185 int r1 = (get1(n) - l1) % MOD; 186 ans += l1 * r1; 187 ans %= MOD; 188 189 cout << ans << '\n'; 190 } 191 192 signed main() 193 { 194 #ifdef FELIX 195 auto _clock_start = chrono::high_resolution_clock::now(); 196 #endif 197 ios_base::sync_with_stdio(false); 198 cin.tie(0); 199 cout.tie(0); 200 201 int tests = 1; 202 cin >> tests; 203 while(tests--){ 204 solve(); 205 } 206 207 #ifdef FELIX 208 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 209 chrono::high_resolution_clock::now() 210 - _clock_start).count() << "ms." << endl; 211 #endif 212 return 0; 213 } 214 ``` 215 216 [2225E - Covering Points with Circles](/contest/2225/problem/E "Educational Codeforces Round 189 (Rated for Div. 2)") 217 218 Author: [basalov_yurij](/profile/basalov_yurij "Expert basalov_yurij") 219 220 **Tutorial** 221 222 Tutorial is loading... 223 224 **Solution (FelixArg)** 225 226 ``` 227 #include <bits/stdc++.h> 228 229 using namespace std; 230 231 #define int long long 232 233 mt19937 rng(chrono::high_resolution_clock().now().time_since_epoch().count()); 234 235 void solve() { 236 int n, r; 237 cin >> n >> r; 238 vector<pair<int, int>> p(n); 239 for (int i = 0; i < n; i++){ 240 cin >> p[i].first >> p[i].second; 241 } 242 243 int w = 2 * r, h = ceil(sqrt(3) * r); 244 245 auto is_in_circle = [&](int x, int y, int ox, int oy, int r){ 246 return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r; 247 }; 248 249 int cov; 250 vector<pair<int, int>> ans; 251 252 do{ 253 ans.clear(); 254 cov = 0; 255 256 int x0 = rng() % 100'000, y0 = rng() % 100'000; 257 auto check_point = [&](int x, int y){ 258 int nearest_row = (y - y0) / h; 259 for (int row = nearest_row - 2; row <= nearest_row + 2; row++){ 260 int nearest_col = (x - (x0 + (row % 2) * r)) / w; 261 for (int col = nearest_col - 2; col <= nearest_col + 2; col++){ 262 int x_lat = x0 + col * w + (row % 2) * r; 263 int y_lat = y0 + row * h; 264 if (is_in_circle(x, y, x_lat, y_lat, r)){ 265 ans.emplace_back(x_lat, y_lat); 266 cov++; 267 return; 268 } 269 } 270 } 271 }; 272 273 for (int i = 0; i < n; i++){ 274 check_point(p[i].first, p[i].second); 275 } 276 } while(cov * 100 < 89 * n); 277 278 sort(ans.begin(), ans.end()); 279 ans.erase(unique(ans.begin(), ans.end()), ans.end()); 280 281 cout << ans.size() << '\n'; 282 for (auto [x, y] : ans){ 283 cout << x << ' ' << y << '\n'; 284 } 285 } 286 287 signed main() 288 { 289 #ifdef FELIX 290 auto _clock_start = chrono::high_resolution_clock::now(); 291 #endif 292 ios_base::sync_with_stdio(false); 293 cin.tie(0); 294 cout.tie(0); 295 296 int tests = 1; 297 //cin >> tests; 298 while(tests--){ 299 solve(); 300 } 301 302 #ifdef FELIX 303 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 304 chrono::high_resolution_clock::now() 305 - _clock_start).count() << "ms." << endl; 306 #endif 307 return 0; 308 } 309 ``` 310 311 [2225F - String Cutting](/contest/2225/problem/F "Educational Codeforces Round 189 (Rated for Div. 2)") 312 313 Author: [FelixArg](/profile/FelixArg "Master FelixArg") 314 315 **Tutorial** 316 317 Tutorial is loading... 318 319 **Solution 1 (FelixArg)** 320 321 ``` 322 #include<bits/stdc++.h> 323 324 using namespace std; 325 326 #define int long long 327 328 const int MODS[] = {some hidden number 1, some hidden number 2}; 329 const int P = some hidden number 3; 330 331 int powP[2][1'000'007]; 332 int inv_powP[2][1'000'007]; 333 334 int bpow(int x, int p, int mod){ 335 int res = 1; 336 while(p){ 337 if (p % 2 == 1){ 338 res = (res * x) % mod; 339 } 340 p >>= 1; 341 x = (x * x) % mod; 342 } 343 return res; 344 } 345 346 void solve(){ 347 int n, l, k; 348 cin >> n >> l >> k; 349 string s; 350 cin >> s; 351 352 if (l * k > n){ 353 cout << "NO\n"; 354 return; 355 } 356 357 if (k == 1){ 358 cout << "YES\n"; 359 cout << s << '\n'; 360 return; 361 } 362 363 vector<vector<int>> h(2, vector<int>(n + 1)); 364 for (int i = 0; i < 2; i++){ 365 for (int j = 0; j < n; j++){ 366 h[i][j + 1] = (h[i][j] + (s[j] - 'a' + 1) * powP[i][j]) % MODS[i]; 367 } 368 } 369 370 function<pair<int, int>(int, int)> get_h = [&](int l, int r){ 371 return make_pair((h[0][r + 1] - h[0][l] + MODS[0]) * inv_powP[0][l] % MODS[0], 372 (h[1][r + 1] - h[1][l] + MODS[1]) * inv_powP[1][l] % MODS[1]); 373 }; 374 375 function<int(int, int, int, int)> cmp_substring = [&](int l1, int r1, int l2, int r2){ 376 int len1 = r1 - l1 + 1; 377 int len2 = r2 - l2 + 1; 378 379 int l = 0, r = min(len1, len2) - 1; 380 while(l <= r){ 381 int m = l + (r - l) / 2; 382 if (get_h(l1, l1 + m) != get_h(l2, l2 + m)){ 383 r = m - 1; 384 } 385 else{ 386 l = m + 1; 387 } 388 } 389 390 char ch1 = (l < len1 ? s[l1 + l] : 'a' - 1); 391 char ch2 = (l < len2 ? s[l2 + l] : 'a' - 1); 392 393 if (ch1 < ch2){ 394 return -1; 395 } 396 if (ch1 > ch2){ 397 return 1; 398 } 399 return 0; 400 }; 401 402 int la = 0, ra = l - 1; 403 404 for (int i = 0; i < n; i++){ 405 int cnt = i / l; 406 if (i > 0 && cnt == 0){ 407 continue; 408 } 409 int len = i + max(0ll, (k - 1) - cnt) * l; 410 if (n - len >= l){ 411 if (cmp_substring(i, i + n - len - 1, la, ra) == 1){ 412 la = i; 413 ra = i + n - len - 1; 414 } 415 } 416 } 417 418 cout << "YES\n"; 419 cout << s.substr(la, ra - la + 1) << '\n'; 420 } 421 422 signed main() 423 { 424 #ifdef FELIX 425 auto _clock_start = chrono::high_resolution_clock::now(); 426 #endif 427 ios_base::sync_with_stdio(false); 428 cin.tie(0); 429 cout.tie(0); 430 431 powP[0][0] = powP[1][0] = 1; 432 inv_powP[0][0] = inv_powP[1][0] = 1; 433 int inv_p[] = {bpow(P, MODS[0] - 2, MODS[0]), bpow(P, MODS[1] - 2, MODS[1])}; 434 435 for (int i = 1; i < 1'000'001; i++){ 436 for (int j = 0; j < 2; j++){ 437 powP[j][i] = powP[j][i - 1] * P % MODS[j]; 438 inv_powP[j][i] = inv_powP[j][i - 1] * inv_p[j] % MODS[j]; 439 } 440 } 441 442 443 int tests = 1; 444 cin >> tests; 445 while(tests--){ 446 solve(); 447 } 448 449 #ifdef FELIX 450 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 451 chrono::high_resolution_clock::now() 452 - _clock_start).count() << "ms." << endl; 453 #endif 454 return 0; 455 } 456 ``` 457 458 **Solution 2 (BledDest)** 459 460 ``` 461 #include <bits/stdc++.h> 462 463 using namespace std; 464 465 int n, l, k; 466 string s; 467 string cur; 468 int zf[2000043]; 469 mt19937 rnd(421337); 470 471 void z_function(const string& s) 472 { 473 int n = s.size(); 474 for(int i = 0; i < n; i++) zf[i] = 0; 475 for (int i = 1, l = 0, r = 0; i < n; i++) 476 { 477 if (i <= r) 478 zf[i] = min(r - i, zf[i - l]); 479 while (i + zf[i] < n && s[zf[i]] == s[i + zf[i]]) 480 zf[i]++; 481 if (i + zf[i] > r) 482 { 483 l = i; 484 r = i + zf[i]; 485 } 486 } 487 } 488 489 bool read() 490 { 491 if (!(cin >> n >> l >> k)) 492 return false; 493 cin >> s; 494 return true; 495 } 496 497 string find_best(vector<pair<int, int>> cand) 498 { 499 while(true) 500 { 501 if(cand.size() == 1) 502 return s.substr(cand[0].first, cand[0].second); 503 int lf = cand[0].first; 504 int rg = cand[0].first + cand[0].second; 505 for(int i = 1; i < cand.size(); i++) 506 { 507 lf = min(lf, cand[i].first); 508 rg = max(rg, cand[i].first + cand[i].second); 509 } 510 auto p = cand[0]; 511 cur = s.substr(p.first, p.second) + "?" + s.substr(lf, rg - lf); 512 z_function(cur); 513 vector<pair<int, int>> better; 514 int len = p.second; 515 for(int i = 0; i < cand.size(); i++) 516 { 517 if(cand[i] == p) continue; 518 int L = cand[i].first - lf; 519 int cur_len = cand[i].second; 520 int lcp = zf[len + 1 + L]; 521 lcp = min(lcp, cur_len); 522 if(lcp == cur_len || (len > lcp && cur[L + len + 1 + lcp] <= cur[lcp])) 523 continue; 524 better.push_back(cand[i]); 525 } 526 if(better.empty()) 527 return s.substr(p.first, p.second); 528 else 529 cand = better; 530 } 531 return ""; 532 } 533 534 void solve() 535 { 536 if(k * 1ll * l > n) 537 { 538 cout << "NO\n"; 539 return; 540 } 541 if(k == 1) 542 { 543 cout << "YES\n" << s << "\n"; 544 return; 545 } 546 vector<pair<int, int>> cand; 547 for(int i = 0; i < n; i++) 548 { 549 if(i > 0 && i < l) continue; 550 int lf = i / l; 551 int rg = (n - i) / l; 552 if(lf + rg < k) continue; 553 int need_rg = max(0, k - lf - 1); 554 int len = (n - need_rg * l) - i; 555 if(len >= l) 556 cand.push_back(make_pair(i, len)); 557 } 558 shuffle(cand.begin(), cand.end(), rnd); 559 if(cand.empty()) 560 { 561 cout << "NO\n"; 562 } 563 else 564 { 565 cout << "YES\n" << find_best(cand) << "\n"; 566 } 567 } 568 569 int main() 570 { 571 cin.tie(0); 572 ios::sync_with_stdio(false); 573 574 int tc = 1; 575 cin >> tc; 576 while (tc--) 577 { 578 read(); 579 solve(); 580 } 581 } 582 ``` 583 584 [2225G - Simple Problem](/contest/2225/problem/G "Educational Codeforces Round 189 (Rated for Div. 2)") 585 586 Author: [basalov_yurij](/profile/basalov_yurij "Expert basalov_yurij") 587 588 **Tutorial** 589 590 Tutorial is loading... 591 592 **Solution (BledDest)** 593 594 ``` 595 #include<bits/stdc++.h> 596 597 using namespace std; 598 599 int n, m; 600 vector<int> k; 601 vector<int> g; 602 603 bool read() 604 { 605 if(!(cin >> n >> m)) return false; 606 k.resize(m); 607 for(int i = 0; i < m; i++) cin >> k[i]; 608 return true; 609 } 610 611 pair<vector<int>, vector<int>> get_chain(int start, int rank) 612 { 613 if(rank == 0) 614 return make_pair(vector<int>({start}), vector<int>()); 615 pair<vector<int>, vector<int>> p = get_chain(start, rank - 1); 616 int cnt = g[rank - 1] / g[rank]; 617 for(int i = 1; i < cnt; i++) 618 { 619 p.second.push_back(k[rank]); 620 int next_start = (p.first.back() + k[rank]) % k[0]; 621 pair<vector<int>, vector<int>> q = get_chain(next_start, rank - 1); 622 for(auto x : q.first) p.first.push_back(x); 623 for(auto x : q.second) p.second.push_back(x); 624 } 625 return p; 626 } 627 628 void solve() 629 { 630 g = k; 631 for(int i = 1; i < m; i++) 632 g[i] = gcd(g[i - 1], k[i]); 633 if(g.back() != 1) 634 { 635 cout << -1 << "\n"; 636 return; 637 } 638 if(k[0] == 1) 639 { 640 for(int i = 0; i < n; i++) 641 { 642 if(i) cout << " "; 643 cout << i; 644 } 645 cout << "\n"; 646 return; 647 } 648 pair<vector<int>, vector<int>> chain = get_chain(0, m - 1); 649 vector<int> classes = chain.first; 650 vector<int> add = chain.second; 651 vector<int> ans; 652 int new_begin = 0; 653 for(int i = 0; i < classes.size(); i++) 654 { 655 int new_end = -1; 656 for(int j = classes[i]; j < n; j += k[0]) 657 if(j != new_begin) 658 { 659 new_end = j; 660 break; 661 } 662 ans.push_back(new_begin); 663 for(int j = classes[i]; j < n; j += k[0]) 664 if(j != new_begin && j != new_end) 665 ans.push_back(j); 666 ans.push_back(new_end); 667 if(i + 1 < classes.size()) 668 new_begin = new_end + add[i]; 669 } 670 for(int i = 0; i < n; i++) 671 { 672 if(i) cout << " "; 673 cout << ans[i]; 674 } 675 cout << "\n"; 676 } 677 678 int main() 679 { 680 ios_base::sync_with_stdio(0); 681 cin.tie(0); 682 int t; 683 cin >> t; 684 while(t--) 685 { 686 read(); 687 solve(); 688 } 689 return 0; 690 } 691 ```