2086.md (13535B)
1 Source: https://codeforces.com/blog/entry/141425 2 3 Thank you for participating! I hope you enjoyed the problems. 4 5 [2086A - Cloudberry Jam](/contest/2086/problem/A "Educational Codeforces Round 177 (Rated for Div. 2)") 6 7 Idea: [Galina_Basalova](/profile/Galina_Basalova "Newbie Galina_Basalova") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution (Galina_Basalova)** 14 15 ``` 16 #include<bits/stdc++.h> 17 using namespace std; 18 19 int main(){ 20 int t; 21 cin >> t; 22 while (t--) { 23 int n; 24 cin >> n; 25 cout << n * 2 << "\n"; 26 } 27 return 0; 28 } 29 ``` 30 31 [2086B - Large Array and Segments](/contest/2086/problem/B "Educational Codeforces Round 177 (Rated for Div. 2)") 32 33 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 34 35 **Tutorial** 36 37 Tutorial is loading... 38 39 **Solution (FelixArg)** 40 41 ``` 42 #include<bits/stdc++.h> 43 using namespace std; 44 #define int long long 45 46 void solve(){ 47 int n, k, x; 48 cin >> n >> k >> x; 49 vector<int> a(n); 50 for (int i = 0; i < n; i++){ 51 cin >> a[i]; 52 } 53 54 if (accumulate(a.begin(), a.end(), 0ll) * k < x){ 55 cout << 0 << '\n'; 56 return; 57 } 58 59 int l = 1, r = n * k; 60 while(l <= r){ 61 int m = l + (r - l) / 2; 62 int cnt_a = (n * k - m + 1) / n; 63 int suff = (n * k - m + 1) % n; 64 int sum = cnt_a * accumulate(a.begin(), a.end(), 0ll); 65 for (int i = n - suff; i < n; i++){ 66 sum += a[i]; 67 } 68 if (sum < x){ 69 r = m - 1; 70 } 71 else{ 72 l = m + 1; 73 } 74 } 75 76 cout << r << '\n'; 77 } 78 79 signed main() 80 { 81 ios_base::sync_with_stdio(false); 82 cin.tie(0); 83 cout.tie(0); 84 85 int t; 86 cin >> t; 87 while(t--){ 88 solve(); 89 } 90 } 91 ``` 92 93 [2086C - Disappearing Permutation](/contest/2086/problem/C "Educational Codeforces Round 177 (Rated for Div. 2)") 94 95 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 96 97 **Tutorial** 98 99 Tutorial is loading... 100 101 **Solution (FelixArg)** 102 103 ``` 104 #include<bits/stdc++.h> 105 using namespace std; 106 #define int long long 107 108 void solve(){ 109 int n; 110 cin >> n; 111 vector<int> p(n); 112 for (int i = 0; i < n; i++){ 113 cin >> p[i]; 114 p[i]--; 115 } 116 117 set<int> X; 118 for (int i = 0; i < n; i++){ 119 int d; 120 cin >> d; 121 d--; 122 while(!X.contains(d)){ 123 X.insert(d); 124 d = p[d]; 125 } 126 cout << X.size() << ' '; 127 } 128 cout << endl; 129 } 130 131 signed main() 132 { 133 ios_base::sync_with_stdio(false); 134 cin.tie(0); 135 cout.tie(0); 136 137 int t; 138 cin >> t; 139 while(t--){ 140 solve(); 141 } 142 } 143 ``` 144 145 [2086D - Even String](/contest/2086/problem/D "Educational Codeforces Round 177 (Rated for Div. 2)") 146 147 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 148 149 **Tutorial** 150 151 Tutorial is loading... 152 153 **Solution (FelixArg)** 154 155 ``` 156 #include<bits/stdc++.h> 157 using namespace std; 158 #define int long long 159 160 const int MOD = 998'244'353; 161 162 int bpow(int x, int p){ 163 int res = 1; 164 while(p){ 165 if (p % 2){ 166 res = (res * x) % MOD; 167 } 168 p >>= 1; 169 x = (x * x) % MOD; 170 } 171 return res; 172 } 173 174 int fact(int x){ 175 int res = 1; 176 for (int i = 1; i <= x; i++){ 177 res = (res * i) % MOD; 178 } 179 return res; 180 } 181 182 void solve(){ 183 vector<int> c(26); 184 for (int i = 0; i < 26; i++){ 185 cin >> c[i]; 186 } 187 188 int s = accumulate(c.begin(), c.end(), 0ll); 189 190 vector<int> dp(s + 1); 191 dp[0] = 1; 192 193 for (int i = 0; i < 26; i++){ 194 if (c[i] == 0){ 195 continue; 196 } 197 for (int j = s; j >= 0; j--){ 198 if (j + c[i] <= s){ 199 dp[j + c[i]] = (dp[j + c[i]] + dp[j]) % MOD; 200 } 201 } 202 } 203 204 int ans = dp[s / 2] * fact(s / 2) % MOD * fact((s + 1) / 2) % MOD; 205 for (int i = 0; i < 26; i++){ 206 ans = (ans * bpow(fact(c[i]), MOD - 2)) % MOD; 207 } 208 209 cout << ans << '\n'; 210 } 211 212 signed main(){ 213 ios_base::sync_with_stdio(false); 214 cin.tie(0); 215 cout.tie(0); 216 217 int t; 218 cin >> t; 219 while(t--){ 220 solve(); 221 } 222 } 223 ``` 224 225 [2086E - Zebra-like Numbers](/contest/2086/problem/E "Educational Codeforces Round 177 (Rated for Div. 2)") 226 227 Idea: [FelixArg](/profile/FelixArg "International Master FelixArg") 228 229 **Tutorial** 230 231 Tutorial is loading... 232 233 **Solution (FelixArg)** 234 235 ``` 236 #include<bits/stdc++.h> 237 using namespace std; 238 239 long long dp[40][120][2][2]; 240 241 void count(vector<int>& num){ 242 int m = num.size(); 243 memset(dp, 0, sizeof(dp)); 244 245 dp[0][0][1][0] = 1; 246 for (int i = 0; i < m; i++){ 247 for (int j = 0; j < 3 * m + 2; j++){ 248 for (int k = 0; k < 4; k++){ 249 if (j + k >= 3 * m + 2){ 250 break; 251 } 252 if (num[i] == k){ 253 dp[i + 1][j + k][1][0] += dp[i][j][1][0]; 254 dp[i + 1][j + k][0][0] += dp[i][j][0][0]; 255 if (k == 0){ 256 dp[i + 1][j + k][1][1] += dp[i][j][1][1]; 257 dp[i + 1][j + k][0][1] += dp[i][j][0][1]; 258 } 259 } 260 else if (num[i] > k){ 261 dp[i + 1][j + k][0][0] += dp[i][j][0][0]; 262 dp[i + 1][j + k][0][0] += dp[i][j][1][0]; 263 if (k == 0){ 264 dp[i + 1][j + k][0][1] += dp[i][j][0][1]; 265 dp[i + 1][j + k][0][1] += dp[i][j][1][1]; 266 } 267 } 268 else{ 269 dp[i + 1][j + k][0][0] += dp[i][j][0][0]; 270 if (k == 0){ 271 dp[i + 1][j + k][0][1] += dp[i][j][0][1]; 272 } 273 } 274 } 275 if (j + 4 < 3 * m + 2){ 276 if (num[i] == 4){ 277 dp[i + 1][j + 4][1][1] += dp[i][j][1][0]; 278 dp[i + 1][j + 4][0][1] += dp[i][j][0][0]; 279 } 280 else{ 281 dp[i + 1][j + 4][0][1] += dp[i][j][0][0]; 282 } 283 } 284 } 285 } 286 } 287 288 void solve(){ 289 long long l, r, k; 290 cin >> l >> r >> k; 291 l--; 292 if (k >= 90){ 293 cout << 0 << '\n'; 294 return; 295 } 296 297 vector<long long> zeb; 298 long long cur = 0; 299 for (int i = 0; i < 60; i += 2){ 300 cur ^= (1ll << i); 301 zeb.emplace_back(cur); 302 } 303 int m = zeb.size(); 304 305 vector<int> num_l; 306 for (int i = m - 1; i >= 0; i--){ 307 int cnt = 0; 308 while(l >= zeb[i]){ 309 cnt++; 310 l -= zeb[i]; 311 } 312 num_l.emplace_back(cnt); 313 } 314 315 vector<int> num_r; 316 for (int i = m - 1; i >= 0; i--){ 317 int cnt = 0; 318 while(r >= zeb[i]){ 319 cnt++; 320 r -= zeb[i]; 321 } 322 num_r.emplace_back(cnt); 323 } 324 325 count(num_r); 326 long long ans = dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1]; 327 count(num_l); 328 ans -= dp[m][k][0][0] + dp[m][k][0][1] + dp[m][k][1][0] + dp[m][k][1][1]; 329 cout << ans << '\n'; 330 } 331 332 signed main() 333 { 334 ios_base::sync_with_stdio(false); 335 cin.tie(0); 336 cout.tie(0); 337 338 int t; 339 cin >> t; 340 while(t--){ 341 solve(); 342 } 343 } 344 ``` 345 346 **Solution (BledDest)** 347 348 ``` 349 #include <bits/stdc++.h> 350 using namespace std; 351 352 vector<long long> z; 353 354 void precalc() 355 { 356 z = {1ll}; 357 while(z.back() < 1e18) 358 z.push_back(4 * z.back() + 1); 359 } 360 361 map<pair<long long, long long>, long long> dp; 362 363 long long get(long long r, long long x) 364 { 365 if(dp.count(make_pair(r, x))) return dp[make_pair(r, x)]; 366 long long& d = dp[make_pair(r, x)]; 367 if(x > 4 * z.size()) return d = 0; 368 if(x < 0) return d = 0; 369 if(r == 0) return d = 0; 370 if(r == 1) 371 { 372 if(x == 0) return d = 1; 373 return d = 0; 374 } 375 auto it = lower_bound(z.begin(), z.end(), r); 376 --it; 377 long long y = *it; 378 return d = get(y, x) + get(r - y, x - 1); 379 } 380 381 int main() 382 { 383 precalc(); 384 int t; 385 cin >> t; 386 for(int i = 0; i < t; i++) 387 { 388 long long l, r, x; 389 cin >> l >> r >> x; 390 cout << get(r + 1, x) - get(l, x) << endl; 391 } 392 } 393 ``` 394 395 [2086F - Online Palindrome](/contest/2086/problem/F "Educational Codeforces Round 177 (Rated for Div. 2)") 396 397 Idea: [Valentin_E](/profile/Valentin_E "Master Valentin_E") 398 399 **Tutorial** 400 401 Tutorial is loading... 402 403 **Solution (FelixArg)** 404 405 ``` 406 #include<bits/stdc++.h> 407 using namespace std; 408 #define int long long 409 410 bool is_palindrom(const string& s){ 411 int n = s.size(); 412 for (int i = 0; i < n / 2; i++){ 413 if (s[i] != s[n - i - 1]){ 414 return false; 415 } 416 } 417 return true; 418 } 419 420 bool check_pattern(const string& s){ 421 int n = s.size(); 422 char a = 'a', b = 'b'; 423 int cnt_a = 0, cnt_b = 0; 424 for (int i = 0; i < n; i++){ 425 if (s[i] == a){ 426 cnt_a++; 427 } 428 else{ 429 cnt_b++; 430 } 431 } 432 if (cnt_a % 2 == 1){ 433 swap(cnt_a, cnt_b); 434 swap(a, b); 435 } 436 if (s[n / 2] != b){ 437 return false; 438 } 439 if (!is_palindrom(s)){ 440 return false; 441 } 442 443 cnt_b--; 444 cnt_a /= 2; 445 cnt_b /= 2; 446 447 if (cnt_a > cnt_b){ 448 swap(cnt_a, cnt_b); 449 swap(a, b); 450 } 451 452 if (s[0] == a){ 453 cnt_a--; 454 } 455 else{ 456 cnt_b--; 457 } 458 459 for (int i = 1; i < n / 2; i++){ 460 if (s[i] == s[i - 1]){ 461 if (cnt_a == 0){ 462 return true; 463 } 464 return false; 465 } 466 if (s[i] == a){ 467 cnt_a--; 468 } 469 else{ 470 cnt_b--; 471 } 472 } 473 474 return true; 475 } 476 477 pair<int, int> find_valid_move_odd(string s){ 478 int n = s.size(); 479 for (int i = 0; i < n; i++){ 480 for (int j = i; j < n; j++){ 481 swap(s[i], s[j]); 482 if (check_pattern(s)){ 483 return {i, j}; 484 } 485 swap(s[i], s[j]); 486 } 487 } 488 return {-1, -1}; 489 } 490 491 pair<int, int> find_valid_move_even(string s){ 492 int n = s.size(); 493 for (int i = n - 1; i >= 0; i--){ 494 for (int j = 0; j <= i; j++){ 495 if (s[i] == s[j] && i != j){ 496 continue; 497 } 498 if (i == j && i != n - 1){ 499 continue; 500 } 501 swap(s[i], s[j]); 502 int cnt = 0; 503 s += 'a'; 504 for (int k = n; k >= 0; k--){ 505 for (int l = 0; l <= k; l++){ 506 if (s[k] == s[l] && k != l){ 507 continue; 508 } 509 if (k == l && k != n){ 510 continue; 511 } 512 swap(s[k], s[l]); 513 if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){ 514 cnt++; 515 swap(s[k], s[l]); 516 break; 517 } 518 swap(s[k], s[l]); 519 } 520 if (cnt == 1){ 521 break; 522 } 523 } 524 s.pop_back(); 525 if (cnt == 1){ 526 s += 'b'; 527 for (int k = n; k >= 0; k--){ 528 for (int l = 0; l <= k; l++){ 529 if (s[k] == s[l] && k != l){ 530 continue; 531 } 532 if (k == l && k != n){ 533 continue; 534 } 535 swap(s[k], s[l]); 536 if (s[k] == s[n - k] && s[l] == s[n - l] && s[i] == s[n - i] && s[j] == s[n - j] && check_pattern(s)){ 537 return {i, j}; 538 } 539 swap(s[k], s[l]); 540 } 541 } 542 s.pop_back(); 543 } 544 swap(s[i], s[j]); 545 } 546 } 547 return {-1, -1}; 548 } 549 550 void solve(){ 551 string t = ""; 552 while(1){ 553 char ch; 554 cin >> ch; 555 if (ch == '0'){ 556 break; 557 } 558 559 t += ch; 560 561 if (t.size() % 2 == 1){ 562 auto [l, r] = find_valid_move_odd(t); 563 swap(t[l], t[r]); 564 cout << l + 1 << ' ' << r + 1 << endl; 565 } 566 else{ 567 auto [l, r] = find_valid_move_even(t); 568 swap(t[l], t[r]); 569 cout << l + 1 << ' ' << r + 1 << endl; 570 } 571 } 572 } 573 574 signed main() 575 { 576 ios_base::sync_with_stdio(false); 577 cin.tie(0); 578 cout.tie(0); 579 solve(); 580 } 581 ``` 582 583 **Solution (awoo)** 584 585 ``` 586 #include <bits/stdc++.h> 587 using namespace std; 588 589 #define forn(i, n) for(int i = 0; i < int(n); i++) 590 const int N = 100; 591 592 bool dp[N][N]; 593 pair<int, int> nxt[N][N][2]; 594 bitset<N> cur; 595 bitset<N> form[N][N]; 596 597 int main(){ 598 forn(i, N) forn(j, N) dp[i][j] = (i + j) % 2; 599 for (int len = 1; len < N; len += 2){ 600 forn(x, len + 1){ 601 int y = len - x; 602 int nx = x, ny = y; 603 int i = 0; 604 while (nx > 1 || ny > 1){ 605 if (nx > 1){ 606 nx -= 2; 607 ++i; 608 } 609 if (ny > 1){ 610 form[x][y][i] = form[x][y][len - i - 1] = 1; 611 ny -= 2; 612 ++i; 613 } 614 } 615 if (ny > 0){ 616 form[x][y][i] = 1; 617 } 618 } 619 } 620 for (int len = N - 3; len >= 1; len -= 2){ 621 forn(x, len + 1){ 622 int y = len - x; 623 cur = form[x][y]; 624 forn(c, 2){ 625 cur[len] = c; 626 bool found = false; 627 forn(l, len + 1){ 628 forn(r, l + 1){ 629 if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip(); 630 bool ok = true; 631 forn(d, 2){ 632 cur[len + 1] = d; 633 int nx = x + (c == 0) + (d == 0); 634 int ny = y + (c == 1) + (d == 1); 635 if ((cur ^ form[nx][ny]).count() > 2){ 636 ok = false; 637 break; 638 } 639 } 640 if (ok){ 641 found = true; 642 nxt[x][y][c] = {l, r}; 643 } 644 if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip(); 645 if (found) break; 646 } 647 if (found) break; 648 } 649 if (!found){ 650 dp[x][y] = false; 651 break; 652 } 653 } 654 } 655 } 656 string s; 657 cur.reset(); 658 for (int i = 0;; ++i){ 659 cin >> s; 660 if (s == "0") break; 661 int c = s[0] - 'a'; 662 int py = cur.count(), px = i - py; 663 cur[i] = c; 664 int nx = px + (c == 0), ny = py + (c == 1); 665 int l = -1, r = -1; 666 if (i % 2 == 1){ 667 auto res = nxt[px][py][c]; 668 if (res.first != res.second){ 669 l = res.first; 670 r = res.second; 671 } 672 } 673 else{ 674 assert(dp[nx][ny]); 675 bitset<N> dif = cur ^ form[nx][ny]; 676 assert(dif.count() <= 2); 677 if (dif.count() == 2){ 678 l = dif._Find_first(); 679 r = dif._Find_next(l); 680 } 681 } 682 if (l == -1){ 683 cout << 0 << " " << 0 << endl; 684 } 685 else{ 686 cout << l + 1 << " " << r + 1 << endl; 687 if (cur[l] != cur[r]) cur[l].flip(), cur[r].flip(); 688 } 689 } 690 } 691 ```