2200.md (11167B)
1 Source: https://codeforces.com/blog/entry/151625 2 3 Thanks to everyone who participated in this round! I hope you enjoyed the contest. 4 5 **Rate the contest!** 6 7 * Horrible contest 8 * Bad contest 9 * Average contest 10 * Good contest 11 * Peak contest 12 13 **Rate the difficulty!** 14 15 * Extreme contest 16 * Hard contest 17 * Normal contest 18 * Easy contest 19 * Trivial contest 20 21 #### [2200A - Eating Game](/contest/2200/problem/A "Codeforces Round 1084 (Div. 3)") 22 23 **Rate the problem!** 24 25 * Horrible problem 26 * Bad problem 27 * Average problem 28 * Good problem 29 * Peak problem 30 * Did not solve 31 32 **Tutorial** 33 34 Tutorial is loading... 35 36 **Code (C++)** 37 38 ``` 39 #include <bits/stdc++.h> 40 using namespace std; 41 42 void solve() { 43 int n; 44 cin >> n; 45 vector<int> a(n); 46 for (auto &i: a) cin >> i; 47 48 int mx = 0, ans = 0; 49 for (int i : a) mx = max(i, mx); 50 for (int i : a) ans += i == mx; 51 cout << ans << '\n'; 52 } 53 54 signed main() { 55 int t = 1; 56 cin >> t; 57 while (t--) solve(); 58 } 59 ``` 60 61 #### [2200B - Deletion Sort](/contest/2200/problem/B "Codeforces Round 1084 (Div. 3)") 62 63 **Rate the problem!** 64 65 * Horrible problem 66 * Bad problem 67 * Average problem 68 * Good problem 69 * Peak problem 70 * Did not solve 71 72 **Tutorial** 73 74 Tutorial is loading... 75 76 **Code (C++)** 77 78 ``` 79 #include <bits/stdc++.h> 80 using namespace std; 81 82 void solve() { 83 int n; 84 cin >> n; 85 vector<int> a(n); 86 for (auto &i: a) cin >> i; 87 88 if (is_sorted(a.begin(), a.end())) cout << n << '\n'; 89 else cout << "1\n"; 90 } 91 92 signed main() { 93 cin.tie(0)->sync_with_stdio(0); 94 int t = 1; 95 cin >> t; 96 while (t--) solve(); 97 } 98 ``` 99 100 #### [2200C - Specialty String](/contest/2200/problem/C "Codeforces Round 1084 (Div. 3)") 101 102 **Rate the problem!** 103 104 * Horrible problem 105 * Bad problem 106 * Average problem 107 * Good problem 108 * Peak problem 109 * Did not solve 110 111 **Hint** 112 113 What if you delete characters instead of replacing them with $*$? 114 115 **Tutorial** 116 117 Tutorial is loading... 118 119 **Code 1 (C++)** 120 121 ``` 122 #include <bits/stdc++.h> 123 using namespace std; 124 125 void solve() { 126 int n; 127 string s; 128 cin >> n >> s; 129 for (int i = 0; 2*i < n; i++) { 130 for (int j = 1; j < size(s); j++) { 131 if (s[j] == s[j-1]) { 132 s.erase(j-1, 2); 133 } 134 } 135 } 136 cout << (s.empty() ? "YES\n" : "NO\n"); 137 } 138 139 signed main() { 140 int t = 1; 141 cin >> t; 142 while (t--) solve(); 143 } 144 ``` 145 146 **Code 2 (C++)** 147 148 ``` 149 #include <bits/stdc++.h> 150 using namespace std; 151 152 void solve() { 153 int n; 154 string s; 155 cin >> n >> s; 156 stack<int> st; 157 for (char c : s) { 158 if (st.size() && c == st.top()) st.pop(); 159 else st.push(c); 160 } 161 cout << (st.empty() ? "YES\n" : "NO\n"); 162 } 163 164 signed main() { 165 int t = 1; 166 cin >> t; 167 while (t--) solve(); 168 } 169 ``` 170 171 #### [2200D - Portal](/contest/2200/problem/D "Codeforces Round 1084 (Div. 3)") 172 173 **Rate the problem!** 174 175 * Horrible problem 176 * Bad problem 177 * Average problem 178 * Good problem 179 * Peak problem 180 * Did not solve 181 182 **Hint 1** 183 184 What invariants does $p$ have? 185 186 **Hint 2** 187 188 Consider the elements in between the portals and the elements outside of them. 189 190 **Hint 3** 191 192 What invariant does each of these two regions have? 193 194 **Tutorial** 195 196 Tutorial is loading... 197 198 **Code (C++)** 199 200 ``` 201 #include <bits/stdc++.h> 202 using namespace std; 203 204 void solve() { 205 int n, x, y; 206 cin >> n >> x >> y; 207 x--, y--; 208 vector<int> a, b; 209 for (int i = 0; i < n; i++) { 210 int j; 211 cin >> j; 212 if (i <= x || i > y) a.push_back(j); 213 else b.push_back(j); 214 } 215 216 // solve 217 if (!b.empty()) rotate(b.begin(), min_element(b.begin(), b.end()), b.end()); 218 int m = b.empty() ? -1 : b[0]; 219 auto it = a.begin(); 220 while (it != a.end() && *it < m) it++; 221 a.insert(it, b.begin(), b.end()); 222 for (int i = 0; i < n; i++) { 223 cout << a[i] << " \n"[i == n-1]; 224 } 225 } 226 227 signed main() { 228 int t = 1; 229 cin >> t; 230 while (t--) solve(); 231 } 232 ``` 233 234 #### [2200E - Divisive Battle](/contest/2200/problem/E "Codeforces Round 1084 (Div. 3)") 235 236 **Rate the problem!** 237 238 * Horrible problem 239 * Bad problem 240 * Average problem 241 * Good problem 242 * Peak problem 243 * Did not solve 244 245 **Hint 1** 246 247 What elements can the operation not be used on? 248 249 **Answer** 250 251 $1$ and prime numbers. 252 253 **Hint 2** 254 255 What first moves ensure that Alice will win? 256 257 **Answer** 258 259 Making a small prime number appear in the array after a number with a larger prime factor. 260 261 **Hint 3** 262 263 If Alice can win, then she can ensure victory on her first move. 264 265 **Tutorial** 266 267 Tutorial is loading... 268 269 **Code (C++)** 270 271 ``` 272 #include <bits/stdc++.h> 273 using namespace std; 274 275 #define all(x) begin(x), end(x) 276 277 int primebase(int x) { 278 set<int> s; 279 for (int i = 2; i*i <= x; i++) { 280 while (x % i == 0) { 281 s.insert(i); 282 x /= i; 283 } 284 } 285 if (x > 1) s.insert(x); 286 if (s.size() > 1) return -1; 287 if (s.size() == 0) return 1; 288 return *s.begin(); 289 } 290 291 void solve() { 292 int n; 293 cin >> n; 294 vector<int> a(n); 295 for (auto &i: a) cin >> i; 296 297 // solve 298 vector<int> b(n); 299 for (int i = 0; i < n; i++) b[i] = primebase(a[i]); 300 if (is_sorted(all(a))) { 301 cout << "Bob\n"; 302 } else if (*min_element(all(b)) == -1) { 303 cout << "Alice\n"; 304 } else if (is_sorted(all(b))) { 305 cout << "Bob\n"; 306 } else { 307 cout << "Alice\n"; 308 } 309 } 310 311 signed main() { 312 int t = 1; 313 cin >> t; 314 while (t--) solve(); 315 } 316 ``` 317 318 #### [2200F - Mooclear Reactor 2](/contest/2200/problem/F "Codeforces Round 1084 (Div. 3)") 319 320 **Rate the problem!** 321 322 * Horrible problem 323 * Bad problem 324 * Average problem 325 * Good problem 326 * Peak problem 327 * Did not solve 328 329 **Hint 1** 330 331 Try to solve the problem without shop particles. 332 333 **Hint 1.1** 334 335 Fix the number of energy-generating particles $k$. Which particles can Bessie use? 336 337 **Answer** 338 339 She can use all particles with $y\geq k-1$. 340 341 **Hint 1.2** 342 343 Of the particles she can use for some $k$, which should Bessie use? 344 345 **Answer** 346 347 The $k$ particles with the largest $x$ values. 348 349 **Hint 1.3** 350 351 Process $k$ in decreasing order. 352 353 **Hint 2** 354 355 If Bessie has to use a shop particle, which of her own particles should she replace with it? 356 357 **Answer** 358 359 The energy-generating particle with smallest $x$. 360 361 **Tutorial** 362 363 Tutorial is loading... 364 365 **Code (C++)** 366 367 ``` 368 #include <bits/stdc++.h> 369 using namespace std; 370 using ll = long long; 371 372 template<class T> bool smin(T &a, const T b) { return b < a ? a = b, 1 : 0;} 373 template<class T> bool smax(T &a, const T b) { return a < b ? a = b, 1 : 0;} 374 375 void solve() { 376 int n, q; 377 cin >> n >> q; 378 vector<array<int, 2>> a(n); 379 for (auto &i : a) cin >> i[1] >> i[0]; 380 381 // solve 382 sort(a.rbegin(), a.rend()); 383 int ptr = 0; 384 multiset<int> s; 385 ll mx = 0, cur = 0; 386 vector<ll> pref(n+1); 387 for (int k = n; k >= 0; k--) { 388 while (ptr < n && a[ptr][0] >= k) { 389 cur += a[ptr][1]; 390 s.insert(a[ptr][1]); 391 ptr++; 392 } 393 while (s.size() > k + 1) { 394 cur -= *s.begin(); 395 s.erase(s.begin()); 396 } 397 smax(mx, cur); 398 pref[k] = (s.size() <= k) ? cur : cur - *s.begin(); 399 } 400 for (int k = 1; k <= n; k++) smax(pref[k], pref[k-1]); 401 402 // queries 403 while (q--) { 404 int x, y; 405 cin >> x >> y; 406 cout << max(mx, pref[y] + x) << '\n'; 407 } 408 } 409 410 signed main() { 411 int t = 1; 412 cin >> t; 413 while (t--) solve(); 414 } 415 ``` 416 417 #### [2200G - Operation Permutation](/contest/2200/problem/G "Codeforces Round 1084 (Div. 3)") 418 419 **Rate the problem!** 420 421 * Horrible problem 422 * Bad problem 423 * Average problem 424 * Good problem 425 * Peak problem 426 * Did not solve 427 428 **Hint 1** 429 430 Convert each `-` operation to `+` and `/` operation to `x`. 431 432 **Hint 2** 433 434 Fix the permutation. For each `+y` operation, by how much would the answer change if it was removed? 435 436 **Answer** 437 438 The answer would reduce by the product of $y$ and the `x` operations that come after it in the permutation. 439 440 **Hint 3** 441 442 How can you calculate the expected value of the product `x` operations that come after `+y` over all permutations? 443 444 **Tutorial** 445 446 Tutorial is loading... 447 448 **Code (C++)** 449 450 ``` 451 #include <bits/stdc++.h> 452 using namespace std; 453 using ll = long long; 454 455 const int mod = 1e9+7; 456 457 ll mpow(ll a, ll b) { 458 ll r = 1; 459 while (b) { 460 if (b & 1) { 461 r *= a; 462 r %= mod; 463 } 464 b >>= 1; 465 a *= a; 466 a %= mod; 467 } 468 return r; 469 } 470 471 ll inv(ll a) { 472 return mpow(a, mod-2); 473 } 474 475 const int maxn = 5000; 476 ll facts[maxn+1] = {1}; 477 478 void precomp() { 479 for (int i = 1; i <= maxn; i++) { 480 facts[i] = facts[i-1] * i % mod; 481 } 482 } 483 484 void solve() { 485 int n; 486 ll x; 487 cin >> n >> x; 488 489 vector<ll> mults; 490 ll adds = 0; 491 for (int i = 0; i < n; i++) { 492 char c; 493 ll v; 494 cin >> c >> v; 495 if (c == '-') adds += mod - v; 496 else if (c == '+') adds += v; 497 else if (c == '/') mults.push_back(inv(v)); 498 else mults.push_back(v); 499 } 500 adds %= mod; 501 502 // solve 503 int m = mults.size(); 504 vector<ll> dp(m+1); 505 dp[0] = 1; 506 for (auto &b : mults) { 507 x *= b; 508 x %= mod; 509 for (int i = m; i >= 1; i--) { 510 dp[i] += dp[i-1] * b; 511 dp[i] %= mod; 512 } 513 } 514 515 ll S = 0; 516 for (int i = 0; i <= m; i++) { 517 S += dp[i] * facts[i] % mod * facts[m-i] % mod * inv(facts[m]) % mod; 518 S %= mod; 519 } 520 S *= inv(m+1); 521 S %= mod; 522 523 // answer 524 ll ans = x + adds * S; 525 ans %= mod; 526 cout << ans << "\n"; 527 } 528 529 signed main() { 530 precomp(); 531 int t = 1; 532 cin >> t; 533 while (t--) solve(); 534 } 535 ``` 536 537 **Bonus from Proof_by_QED** 538 539 Solve for $n \leq 2\cdot 10^5$. 540 541 #### [2200H - Six Seven](/contest/2200/problem/H "Codeforces Round 1084 (Div. 3)") 542 543 **Rate the problem!** 544 545 * Horrible problem 546 * Bad problem 547 * Average problem 548 * Good problem 549 * Peak problem 550 * Did not solve 551 552 **Hint 1** 553 554 Find a recursive definition for *special* numbers. 555 556 **Hint 2** 557 558 When can $x \bmod{42}$ tell us if $x$ is special? 559 560 **Answer** 561 562 Whenever $42\nmid x$. 563 564 **Hint 3** 565 566 If $42\mid x$, how can we determine if $x$ is *special*? 567 568 **Answer** 569 570 $x$ will be *special* if and only if $\frac{x}{42}$ is *special*. 571 572 **Hint 4** 573 574 Iterate on the number of operations $\bmod{42}$. 575 576 **Tutorial** 577 578 Tutorial is loading... 579 580 **Code (C++)** 581 582 ``` 583 #include <bits/stdc++.h> 584 using namespace std; 585 586 using ll = long long; 587 const ll inf = LLONG_MAX / 2; 588 589 ll f(const vector<ll>& a) { 590 if (a.empty()) return 0; 591 if (a.back() == 1) return 5; 592 int n = a.size(); 593 int mod6 = a[0] % 6; 594 vector<ll> groups[7]; 595 for (ll x : a) { 596 if (x % 6 != mod6) return inf; 597 groups[(x - mod6) / 6 % 7].push_back(x); 598 } 599 ll ans = inf; 600 for (int r = 0; r < 7; r++) { 601 ll k = (42 - 6*r - mod6) % 42; 602 vector<ll> next; 603 for (ll x : groups[r]) next.push_back((x + k) / 42); 604 ll rec = f(next); 605 if (rec >= inf) continue; 606 ans = min(ans, k + 42 * rec); 607 } 608 return ans; 609 } 610 611 void solve() { 612 int n; 613 cin >> n; 614 vector<ll> a(n); 615 for (auto &x : a) cin >> x; 616 sort(a.begin(), a.end()); 617 ll res = f(a); 618 if (res >= inf) cout << "-1\n"; 619 else cout << res << '\n'; 620 } 621 signed main() { 622 cin.tie(0)->sync_with_stdio(0); 623 int t = 1; 624 cin >> t; 625 while (t--) solve(); 626 } 627 ```