1027.md (14006B)
1 Source: https://codeforces.com/blog/entry/61311 2 3 [1027A - Palindromic Twist](/contest/1027/problem/A "Educational Codeforces Round 49 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (PikMike)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 #define forn(i, n) for (int i = 0; i < int(n); i++) 15 16 using namespace std; 17 18 int main() { 19 int T; 20 cin >> T; 21 22 int n; 23 string s; 24 forn(_, T){ 25 cin >> n >> s; 26 bool ok = true; 27 forn(i, n){ 28 int k = abs(s[i] - s[n - i - 1]); 29 if (k > 2 || k % 2 == 1){ 30 ok = false; 31 break; 32 } 33 } 34 cout << (ok ? "YES" : "NO") << endl; 35 } 36 return 0; 37 } 38 ``` 39 40 [1027B - Numbers on the Chessboard](/contest/1027/problem/B "Educational Codeforces Round 49 (Rated for Div. 2)") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution (Vovuh)** 47 48 ``` 49 import sys 50 51 lst = sys.stdin.readlines() 52 n, q = map(int, lst[0].split()) 53 54 for i in range(q): 55 x, y = map(int, lst[i + 1].split()) 56 cnt = (x - 1) * n + y 57 ans = (cnt + 1) // 2 58 if ((x + y) % 2 == 1): ans += (n * n + 1) // 2 59 sys.stdout.write(str(ans) + '\n') 60 ``` 61 62 [1027C - Minimum Value Rectangle](/contest/1027/problem/C "Educational Codeforces Round 49 (Rated for Div. 2)") 63 64 **Tutorial** 65 66 Tutorial is loading... 67 68 **Solution (PikMike)** 69 70 ``` 71 #include <bits/stdc++.h> 72 73 #define forn(i, n) for (int i = 0; i < int(n); i++) 74 75 typedef long long li; 76 77 using namespace std; 78 79 const int N = 1000 * 1000 + 13; 80 81 int n, m; 82 int a[N]; 83 int b[N]; 84 85 int main() { 86 int T; 87 scanf("%d", &T); 88 forn(_, T){ 89 scanf("%d", &n); 90 forn(i, n) 91 scanf("%d", &a[i]); 92 sort(a, a + n); 93 94 m = 0; 95 forn(i, n - 1){ 96 if (a[i] == a[i + 1]){ 97 b[m++] = a[i]; 98 ++i; 99 } 100 } 101 102 int A = b[0], B = b[1]; 103 li P2 = (A + B) * li(A + B); 104 li S = A * li(B); 105 106 forn(i, m - 1){ 107 li p2 = (b[i] + b[i + 1]) * li(b[i] + b[i + 1]); 108 li s = b[i] * li(b[i + 1]); 109 if (s * P2 > S * p2){ 110 A = b[i]; 111 B = b[i + 1]; 112 S = s; 113 P2 = p2; 114 } 115 } 116 117 printf("%d %d %d %d\n", A, A, B, B); 118 } 119 } 120 ``` 121 122 [1027D - Mouse Hunt](/contest/1027/problem/D "Educational Codeforces Round 49 (Rated for Div. 2)") 123 124 **Tutorial** 125 126 Tutorial is loading... 127 128 **Solution (adedalic)** 129 130 ``` 131 #include<bits/stdc++.h> 132 133 using namespace std; 134 135 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 136 #define forn(i, n) fore(i, 0, n) 137 138 #define mp make_pair 139 #define pb push_back 140 141 #define sz(a) int((a).size()) 142 #define all(a) (a).begin(), (a).end() 143 #define sqr(a) ((a) * (a)) 144 145 #define x first 146 #define y second 147 148 typedef long long li; 149 typedef long double ld; 150 typedef pair<li, li> pt; 151 152 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 153 return out << "(" << p.x << ", " << p.y << ")"; 154 } 155 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 156 out << "["; 157 forn(i, sz(v)) { 158 if(i) out << ", "; 159 out << v[i]; 160 } 161 return out << "]"; 162 } 163 164 const int INF = int(1e9); 165 const li INF64 = li(1e18); 166 const ld EPS = 1e-9; 167 168 int n; 169 vector<int> a, c; 170 171 inline bool read() { 172 if(!(cin >> n)) 173 return false; 174 c.assign(n, 0); 175 a.assign(n, 0); 176 177 forn(i, n) 178 assert(scanf("%d", &c[i]) == 1); 179 forn(i, n) { 180 assert(scanf("%d", &a[i]) == 1); 181 a[i]--; 182 } 183 return true; 184 } 185 186 vector< vector<int> > cycles; 187 188 vector<char> used; 189 vector<int> path; 190 191 void dfs(int v) { 192 path.push_back(v); 193 used[v] = 1; 194 195 int to = a[v]; 196 if(used[to] != 2) { 197 if(used[to] == 1) { 198 cycles.emplace_back(); 199 200 int id = sz(path) - 1; 201 while(path[id] != to) 202 cycles.back().push_back(path[id--]); 203 cycles.back().push_back(to); 204 } else 205 dfs(to); 206 } 207 path.pop_back(); 208 used[v] = 2; 209 } 210 211 inline void solve() { 212 used.assign(n, 0); 213 214 forn(i, n) { 215 if (!used[i]) 216 dfs(i); 217 } 218 219 li ans = 0; 220 for(auto &cur : cycles) { 221 int mn = c[cur[0]]; 222 for(int v : cur) 223 mn = min(mn, c[v]); 224 ans += mn; 225 } 226 cout << ans << endl; 227 } 228 229 int main() { 230 #ifdef _DEBUG 231 freopen("input.txt", "r", stdin); 232 int tt = clock(); 233 #endif 234 cout << fixed << setprecision(15); 235 236 if(read()) { 237 solve(); 238 239 #ifdef _DEBUG 240 cerr << "TIME = " << clock() - tt << endl; 241 tt = clock(); 242 #endif 243 } 244 return 0; 245 } 246 ``` 247 248 [1027E - Inverse Coloring](/contest/1027/problem/E "Educational Codeforces Round 49 (Rated for Div. 2)") 249 250 **Tutorial** 251 252 Tutorial is loading... 253 254 **Solution (PikMike) O(n^3)** 255 256 ``` 257 #include <bits/stdc++.h> 258 259 #define forn(i, n) for (int i = 0; i < int(n); i++) 260 261 using namespace std; 262 263 const int N = 500 + 7; 264 const int MOD = 998244353; 265 266 int n, k; 267 int dp[2][N][N]; 268 int cnt[N]; 269 int pr[N]; 270 271 void add(int &a, int b){ 272 a += b; 273 if (a >= MOD) 274 a -= MOD; 275 } 276 277 int main() { 278 scanf("%d%d", &n, &k); 279 280 dp[0][0][0] = 1; 281 forn(ii, n){ 282 int i = ii & 1; 283 int ni = i ^ 1; 284 memset(dp[ni], 0, sizeof(dp[ni])); 285 forn(j, n + 1){ 286 forn(k, n + 1){ 287 add(dp[ni][j + 1][max(j + 1, k)], dp[i][j][k]); 288 add(dp[ni][1][max(1, k)], dp[i][j][k]); 289 } 290 } 291 } 292 293 forn(i, n + 1) 294 forn(j, n + 1) 295 add(cnt[i], dp[n & 1][j][i]); 296 297 forn(i, n + 1){ 298 add(pr[i + 1], pr[i]); 299 add(pr[i + 1], cnt[i]); 300 } 301 302 int ans = 0; 303 for (int i = 1; i <= n; ++i) 304 add(ans, cnt[i] * (long long)(pr[min(n + 1, (k - 1) / i + 1)]) % MOD); 305 306 ans = (ans * (long long)((MOD + 1) / 2)) % MOD; 307 printf("%d\n", ans); 308 309 return 0; 310 } 311 ``` 312 313 **Solution (BledDest) O(n^2)** 314 315 ``` 316 def norm(x): 317 return (x % 998244353 + 998244353) % 998244353 318 319 n, k = map(int, input().split()) 320 321 dp1 = [0] 322 dp2 = [0] 323 324 for i in range(n): 325 l = [1] 326 cur = 0 327 for j in range(n + 1): 328 cur += l[j] 329 if(j > i): 330 cur -= l[j - i - 1] 331 cur = norm(cur) 332 l.append(cur) 333 dp1.append(l[n]) 334 dp2.append(norm(dp1[i + 1] - dp1[i])) 335 336 ans = 0 337 for i in range(n + 1): 338 for j in range(n + 1): 339 if(i * j < k): 340 ans = norm(ans + dp2[i] * dp2[j]) 341 342 ans = norm(ans * 2) 343 344 print(ans) 345 ``` 346 347 [1027F - Session in BSU](/contest/1027/problem/F "Educational Codeforces Round 49 (Rated for Div. 2)") 348 349 **Tutorial** 350 351 Tutorial is loading... 352 353 **Solution (Vovuh)** 354 355 ``` 356 #include <bits/stdc++.h> 357 358 using namespace std; 359 360 #define forn(i, n) for (int i = 0; i < int(n); ++i) 361 362 const int N = 2 * 1000 * 1000 + 11; 363 const int INF = 1e9 + 1; 364 365 int n; 366 int a[N][2]; 367 vector<int> s; 368 bool used[N]; 369 bool exam[N]; 370 vector<pair<int, int>> g[N]; 371 372 bool deny(int v) { 373 if (used[v]) return false; 374 used[v] = true; 375 for (auto it : g[v]) { 376 int to = it.first; 377 int ex = it.second; 378 if (exam[ex]) continue; 379 if (used[to]) 380 return false; 381 exam[ex] = true; 382 if (!deny(to)) 383 return false; 384 } 385 return true; 386 } 387 388 int cntv, cnte; 389 390 void dfs(int v) { 391 ++cntv; 392 used[v] = true; 393 for (auto it : g[v]) { 394 int to = it.first; 395 int ex = it.second; 396 if (exam[ex]) continue; 397 exam[ex] = true; 398 ++cnte; 399 if (!used[to]) 400 dfs(to); 401 } 402 } 403 404 bool check(int day) { 405 memset(used, false, sizeof(used)); 406 memset(exam, false, sizeof(exam)); 407 forn(i, s.size()) if (i > day) { 408 if (!deny(i)) { 409 return false; 410 } 411 } 412 413 forn(i, s.size()) { 414 if (!used[i]) { 415 cntv = 0; 416 cnte = 0; 417 dfs(i); 418 if (cntv < cnte) 419 return false; 420 } 421 } 422 423 return true; 424 } 425 426 int main() { 427 scanf("%d", &n); 428 forn(i, n) forn(j, 2) { 429 scanf("%d", &a[i][j]); 430 s.push_back(a[i][j]); 431 } 432 433 sort(s.begin(), s.end()); 434 s.resize(unique(s.begin(), s.end()) - s.begin()); 435 436 forn(i, n) { 437 forn(j, 2) { 438 a[i][j] = lower_bound(s.begin(), s.end(), a[i][j]) - s.begin(); 439 } 440 g[a[i][0]].push_back(make_pair(a[i][1], i)); 441 g[a[i][1]].push_back(make_pair(a[i][0], i)); 442 } 443 444 int l = 0, r = int(s.size()) - 1; 445 while (r - l > 1) { 446 int mid = (l + r) >> 1; 447 if (check(mid)) 448 r = mid; 449 else 450 l = mid; 451 } 452 for (int i = l; i <= r; ++i) { 453 if (check(i)) { 454 printf("%d\n", s[i]); 455 return 0; 456 } 457 } 458 puts("-1"); 459 } 460 ``` 461 462 **Solution (Vovuh) Kuhn's Algorithm** 463 464 ``` 465 #include <bits/stdc++.h> 466 467 using namespace std; 468 469 mt19937 rnd(time(NULL)); 470 471 const int N = 2 * 1000 * 1000 + 11; 472 const int INF = 1e9; 473 474 int n; 475 int a[N][2]; 476 477 vector<int> nums; 478 int m; 479 480 vector<int> g[N]; 481 int mt[N]; 482 int used[N]; 483 int T = 1; 484 485 bool try_kuhn(int v) { 486 if (used[v] == T) 487 return false; 488 used[v] = T; 489 490 for (auto to : g[v]) { 491 if (mt[to] == -1) { 492 mt[to] = v; 493 return true; 494 } 495 } 496 497 for (auto to : g[v]) { 498 if (try_kuhn(mt[to])) { 499 mt[to] = v; 500 return true; 501 } 502 } 503 504 return false; 505 } 506 507 int main() { 508 #ifdef _DEBUG 509 freopen("input.txt", "r", stdin); 510 // freopen("output.txt", "w", stdout); 511 #endif 512 513 scanf("%d", &n); 514 for (int i = 0; i < n; ++i) { 515 for (int j = 0; j < 2; ++j) { 516 scanf("%d", &a[i][j]); 517 nums.push_back(a[i][j]); 518 } 519 } 520 521 sort(nums.begin(), nums.end()); 522 nums.resize(unique(nums.begin(), nums.end()) - nums.begin()); 523 m = nums.size(); 524 525 for (int i = 0; i < n; ++i) { 526 for (int j = 0; j < 2; ++j) { 527 a[i][j] = lower_bound(nums.begin(), nums.end(), a[i][j]) - nums.begin(); 528 } 529 } 530 531 for (int i = 0; i < n; ++i) { 532 g[a[i][0]].push_back(i); 533 g[a[i][1]].push_back(i); 534 } 535 536 memset(mt, -1, sizeof(mt)); 537 int match = 0; 538 for (int i = 0; i < m; ++i) { 539 if (try_kuhn(i)) { 540 ++T; 541 ++match; 542 if (match == n) { 543 printf("%d\n", nums[i]); 544 return 0; 545 } 546 } 547 } 548 549 puts("-1"); 550 551 return 0; 552 } 553 ``` 554 555 [1027G - X-mouse in the Campus](/contest/1027/problem/G "Educational Codeforces Round 49 (Rated for Div. 2)") 556 557 **Tutorial** 558 559 Tutorial is loading... 560 561 **Solution (adedalic)** 562 563 ``` 564 #include<bits/stdc++.h> 565 566 using namespace std; 567 568 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 569 #define sz(a) int((a).size()) 570 571 #define x first 572 #define y second 573 574 typedef long long li; 575 typedef long double ld; 576 typedef pair<li, li> pt; 577 578 const int INF = int(1e9); 579 const li INF64 = li(1e18); 580 const ld EPS = 1e-9; 581 582 li m, x; 583 584 inline bool read() { 585 if(!(cin >> m >> x)) 586 return false; 587 return true; 588 } 589 590 map< li, vector<pt> > dFact; 591 vector<pt> fact(li v) { 592 if(dFact.count(v)) 593 return dFact[v]; 594 595 li oldv = v; 596 vector<pt> fs; 597 for(li d = 2; d * d <= v; d++) { 598 int cnt = 0; 599 while(v % d == 0) 600 v /= d, cnt++; 601 602 if(cnt > 0) 603 fs.emplace_back(d, cnt); 604 } 605 if(v > 1) 606 fs.emplace_back(v, 1), v = 1; 607 return dFact[oldv] = fs; 608 } 609 610 vector<pt> merge(const vector<pt> &a, const vector<pt> &b) { 611 vector<pt> ans; 612 int u = 0, v = 0; 613 while(u < sz(a) && v < sz(b)) { 614 if(a[u].x < b[v].x) 615 ans.push_back(a[u++]); 616 else if(a[u].x > b[v].x) 617 ans.push_back(b[v++]); 618 else { 619 ans.emplace_back(a[u].x, a[u].y + b[v].y); 620 u++, v++; 621 } 622 } 623 while(u < sz(a)) 624 ans.push_back(a[u++]); 625 while(v < sz(b)) 626 ans.push_back(b[v++]); 627 return ans; 628 } 629 630 li getPw(li a, li b) { 631 li ans = 1; 632 fore(i, 0, b) 633 ans *= a; 634 return ans; 635 } 636 637 li mul(li a, li b, li mod) { 638 li m = li(ld(a) * b / mod); 639 li rem = a * b - m * mod; 640 while(rem < 0) 641 rem += mod; 642 while(rem >= mod) 643 rem -= mod; 644 return rem; 645 } 646 647 li binPow(li a, li k, li mod) { 648 li ans = 1 % mod; 649 while(k > 0) { 650 if(k & 1) 651 ans = mul(ans, a, mod); 652 a = mul(a, a, mod); 653 k >>= 1; 654 } 655 return ans; 656 } 657 658 li findOrder(li x, li mod, const vector<pt> &f) { 659 li phi = 1; 660 fore(i, 0, sz(f)) fore(k, 0, f[i].y) 661 phi *= f[i].x; 662 663 if(phi == 1 || x == 0) 664 return 1; 665 666 li ord = 1; 667 fore(i, 0, sz(f)) { 668 li basePw = phi; 669 fore(k, 0, f[i].y) 670 basePw /= f[i].x; 671 672 li curV = binPow(x, basePw, mod); 673 674 int curPw = -1; 675 fore(k, 0, f[i].y + 1) { 676 if(curV != 1) 677 curPw = k; 678 curV = binPow(curV, f[i].x, mod); 679 } 680 681 ord *= getPw(f[i].x, curPw + 1); 682 } 683 return ord; 684 } 685 686 vector<pt> fm; 687 vector<int> pw; 688 689 li calc(int pos, li dv) { 690 if(pos >= sz(fm)) { 691 vector<pt> cf = fm; 692 fore(i, 0, sz(fm)) 693 cf[i].y = max(pw[i] - 1, 0); 694 695 li phi = dv; 696 fore(i, 0, sz(fm)) { 697 if(pw[i] > 0) { 698 cf = merge(cf, fact(fm[i].x - 1)); 699 phi -= phi / fm[i].x; 700 } 701 } 702 li k = findOrder(x % dv, dv, cf); 703 return phi / k; 704 } 705 706 li ans = 0; 707 fore(i, 0, fm[pos].y + 1) { 708 pw[pos] = i; 709 ans += calc(pos + 1, dv); 710 dv *= fm[pos].x; 711 } 712 return ans; 713 } 714 715 inline void solve() { 716 fm = fact(m); 717 718 pw.assign(sz(fm), 0); 719 li ans = calc(0, 1); 720 721 cout << ans << endl; 722 } 723 724 int main() { 725 #ifdef _DEBUG 726 freopen("input.txt", "r", stdin); 727 int tt = clock(); 728 #endif 729 cout << fixed << setprecision(15); 730 731 if(read()) { 732 solve(); 733 734 #ifdef _DEBUG 735 cerr << "TIME = " << clock() - tt << endl; 736 tt = clock(); 737 #endif 738 } 739 return 0; 740 } 741 ```