1945.md (11756B)
1 Source: https://codeforces.com/blog/entry/127377 2 3 [1945A - Setting up Camp](/contest/1945/problem/A "Codeforces Round 935 (Div. 3)") 4 5 Idea: [Kirill_Maglysh](/profile/Kirill_Maglysh "Expert Kirill_Maglysh") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <iostream> 15 16 using namespace std; 17 using ll = long long; 18 19 void solve() { 20 ll single, poly, uni; 21 cin >> single >> poly >> uni; 22 ll needPoly = (3 - poly % 3) % 3; 23 if (poly > 0 && needPoly > uni) { 24 cout << "-1\n"; 25 return; 26 } 27 28 uni -= needPoly; 29 poly += needPoly; 30 31 ll mn = single + uni / 3 + (uni % 3 + 1) / 2 + poly / 3; 32 cout << mn << '\n'; 33 } 34 35 int32_t main() { 36 ll T; 37 cin >> T; 38 while(T--){ 39 solve(); 40 } 41 return 0; 42 } 43 ``` 44 45 [1945B - Fireworks](/contest/1945/problem/B "Codeforces Round 935 (Div. 3)") 46 47 Idea: [NToneE](/profile/NToneE "Master NToneE"), [Gadget](/profile/Gadget "Pupil Gadget") 48 49 **Tutorial** 50 51 Tutorial is loading... 52 53 **Solution** 54 55 ``` 56 t = int(input()) 57 for qi in range(t): 58 a, b, m = [int(x) for x in input().split()] 59 ans = m // a + m // b + 2 60 print(ans) 61 ``` 62 63 [1945C - Left and Right Houses](/contest/1945/problem/C "Codeforces Round 935 (Div. 3)") 64 65 Idea: [Gadget](/profile/Gadget "Pupil Gadget"), [NToneE](/profile/NToneE "Master NToneE") 66 67 **Tutorial** 68 69 Tutorial is loading... 70 71 **Solution** 72 73 ``` 74 for case in range(int(input())): 75 n = int(input()) 76 a = input() 77 suf_cnt = [0] * (n + 1) 78 for i in range(n - 1, -1, -1): 79 suf_cnt[i] = suf_cnt[i + 1] + (a[i] == '1') 80 pref_cnt = 0 81 82 opt_ans = -1 83 opt_dist = n * 2 84 threshold = (n + 1) // 2 85 86 for i in range(n + 1): 87 if pref_cnt >= (i + 1) // 2 and suf_cnt[i] >= (n - i + 1) // 2 and abs(n - 2 * i) < opt_dist: 88 opt_dist = abs(n - 2 * i) 89 opt_ans = i 90 if i != n: 91 pref_cnt += (a[i] == '0') 92 93 print(opt_ans) 94 ``` 95 96 [1945D - Seraphim the Owl](/contest/1945/problem/D "Codeforces Round 935 (Div. 3)") 97 98 Idea: [Kirill_Maglysh](/profile/Kirill_Maglysh "Expert Kirill_Maglysh") 99 100 **Tutorial** 101 102 Tutorial is loading... 103 104 **Solution** 105 106 ``` 107 #include <iostream> 108 #include <vector> 109 #include <algorithm> 110 111 using namespace std; 112 using ll = long long; 113 114 void solve() { 115 ll n, k; 116 cin >> n >> k; 117 vector<ll> A(n); 118 for (auto& item : A) { 119 cin >> item; 120 } 121 reverse(A.begin(), A.end()); 122 123 vector<ll> B(n); 124 for (auto& item : B) { 125 cin >> item; 126 } 127 reverse(B.begin(), B.end()); 128 129 ll bSum = 0; 130 ll pref = 0; 131 for (ll i = 0; i < n - k; ++i) { 132 if (A[i] < B[i]) { 133 pref += bSum; 134 pref += A[i]; 135 bSum = 0; 136 } else { 137 bSum += B[i]; 138 } 139 } 140 141 ll res = 1e18; 142 for (ll i = n - k; i < n; ++i) { 143 res = min(res, pref + bSum + A[i]); 144 bSum += B[i]; 145 } 146 147 cout << res << '\n'; 148 } 149 150 int32_t main() { 151 ll testN; 152 cin >> testN; 153 while (testN--) { 154 solve(); 155 } 156 return 0; 157 } 158 ``` 159 160 [1945E - Binary Search](/contest/1945/problem/E "Codeforces Round 935 (Div. 3)") 161 162 Idea: [Kirill_Maglysh](/profile/Kirill_Maglysh "Expert Kirill_Maglysh") 163 164 **Tutorial** 165 166 Tutorial is loading... 167 168 **Solution** 169 170 ``` 171 #include <iostream> 172 #include <vector> 173 174 using namespace std; 175 176 void solve() { 177 int n, x; 178 cin >> n >> x; 179 vector<int> src(n); 180 int P = 0; 181 for (int i = 0; i < n; ++i) { 182 cin >> src[i]; 183 if (src[i] == x) { 184 P = i; 185 } 186 } 187 188 int l = 0; 189 int r = n; 190 while (r - l > 1) { 191 int m = (l + r) / 2; 192 193 if (src[m] <= x) { 194 l = m; 195 } else { 196 r = m; 197 } 198 } 199 200 cout << "1\n"; 201 cout << P + 1 << ' ' << l + 1 << '\n'; 202 } 203 204 int main() { 205 ios_base::sync_with_stdio(false); 206 cin.tie(nullptr); 207 cout.tie(nullptr); 208 int T; 209 cin >> T; 210 while (T--) { 211 solve(); 212 } 213 214 return 0; 215 } 216 ``` 217 218 [1945F - Kirill and Mushrooms](/contest/1945/problem/F "Codeforces Round 935 (Div. 3)") 219 220 Idea: [Kirill_Maglysh](/profile/Kirill_Maglysh "Expert Kirill_Maglysh") 221 222 **Tutorial** 223 224 Tutorial is loading... 225 226 **Solution** 227 228 ``` 229 #include <iostream> 230 #include <vector> 231 #include <set> 232 #include <algorithm> 233 234 using namespace std; 235 using ll = long long; 236 237 void solve() { 238 ll n; 239 cin >> n; 240 vector<ll> src(n); 241 vector<pair<ll, ll>> can(n); 242 for (ll i = 0; i < n; ++i) { 243 cin >> src[i]; 244 can[i] = {src[i], i}; 245 } 246 247 vector<ll> ord(n); 248 for (auto& item : ord) { 249 cin >> item; 250 --item; 251 } 252 253 sort(can.rbegin(), can.rend()); 254 ll best = can[0].first; 255 ll take = 1; 256 257 ll cur; 258 ll P = 1; 259 vector<bool> burn(n); 260 vector<bool> used(n); 261 used[can[0].second] = true; 262 for (ll k = 0; k + 1 < n && P < n; ++k) { 263 while (P < n && burn[can[P].second]) { 264 ++P; 265 } 266 267 if (P == n) { 268 break; 269 } 270 271 used[can[P].second] = true; 272 cur = can[P].first; 273 ++P; 274 275 burn[ord[k]] = true; 276 if (used[ord[k]]) { 277 while (P < n && burn[can[P].second]) { 278 ++P; 279 } 280 281 if (P == n) { 282 break; 283 } 284 285 used[can[P].second] = true; 286 cur = can[P].first; 287 ++P; 288 } 289 290 if (best < cur * (k + 2)) { 291 take = k + 2; 292 best = cur * (k + 2); 293 } 294 } 295 296 cout << best << ' ' << take << '\n'; 297 } 298 299 int32_t main() { 300 ll testN; 301 cin >> testN; 302 while (testN--) { 303 solve(); 304 } 305 return 0; 306 } 307 ``` 308 309 [1945G - Cook and Porridge](/contest/1945/problem/G "Codeforces Round 935 (Div. 3)") 310 311 Idea: [Kirill_Maglysh](/profile/Kirill_Maglysh "Expert Kirill_Maglysh") 312 313 **Tutorial** 314 315 Tutorial is loading... 316 317 **Solution** 318 319 ``` 320 #include <iostream> 321 #include <vector> 322 #include <queue> 323 324 using namespace std; 325 using ll = long long; 326 327 const int MAX_N = 2e5; 328 const int MAX_D = 3e5; 329 330 struct Student { 331 int k; 332 int s; 333 int tin = 0; 334 335 bool operator<(const Student& other) const { 336 if (k == other.k) { 337 if (tin == other.tin) { 338 return s > other.s; 339 } 340 return tin > other.tin; 341 } 342 return k < other.k; 343 } 344 }; 345 346 int n, D, x; 347 Student qu1[MAX_N]; 348 int sufMax[MAX_N]; 349 vector<Student> eat[MAX_D]; 350 351 int check() { 352 int origPos = 0; 353 priority_queue<Student> qu2; 354 for (int i = 0; i < D && origPos < n; ++i) { 355 if (qu2.empty() || qu2.top().k <= sufMax[origPos]) { 356 ll nxtTime = ll(i) + ll(x) * ll(qu1[origPos].s); 357 if (nxtTime < D) { 358 eat[nxtTime].push_back(qu1[origPos]); 359 } 360 361 ++origPos; 362 if (origPos == n) { 363 for (int tm = 0; tm < D; ++tm) { 364 eat[tm].clear(); 365 } 366 367 return i + 1; 368 } 369 } else { 370 ll nxtTime = ll(i) + ll(x) * ll(qu2.top().s); 371 if (nxtTime < D) { 372 eat[nxtTime].push_back(qu2.top()); 373 } 374 qu2.pop(); 375 } 376 377 for (const auto& student : eat[i]) { 378 qu2.push({student.k, student.s, i}); 379 } 380 } 381 382 for (int i = 0; i < D; ++i) { 383 eat[i].clear(); 384 } 385 386 return -1; 387 } 388 389 void solve() { 390 cin >> n >> D; 391 x = 1; 392 for (int i = 0; i < n; ++i) { 393 cin >> qu1[i].k >> qu1[i].s; 394 } 395 396 sufMax[n - 1] = qu1[n - 1].k; 397 for (int i = n - 2; i >= 0; --i) { 398 sufMax[i] = max(qu1[i].k, sufMax[i + 1]); 399 } 400 401 cout << check() << '\n'; 402 } 403 404 int32_t main() { 405 ll testN; 406 cin >> testN; 407 while (testN--) { 408 solve(); 409 } 410 return 0; 411 } 412 ``` 413 414 [1945H - GCD is Greater](/contest/1945/problem/H "Codeforces Round 935 (Div. 3)") 415 416 Idea: [Kirill_Maglysh](/profile/Kirill_Maglysh "Expert Kirill_Maglysh") 417 418 **Tutorial** 419 420 Tutorial is loading... 421 422 **Solution** 423 424 ``` 425 #include <iostream> 426 #include <vector> 427 #include <algorithm> 428 429 using namespace std; 430 431 const int BITS = 20; 432 const int MAX_N = 4e5 + 10; 433 int n; 434 int x; 435 436 int src[MAX_N]; 437 438 void coutYES(int fId, int sId) { 439 cout << "YES\n"; 440 cout << "2 " << src[fId] << ' ' << src[sId] << '\n'; 441 cout << n - 2 << ' '; 442 for (int i = 0; i < n; i++) { 443 if (i == fId || i == sId) { 444 continue; 445 } 446 cout << src[i] << ' '; 447 } 448 cout << '\n'; 449 } 450 451 void solve() { 452 cin >> n >> x; 453 vector<int> bitCnt[BITS]; 454 455 int maxA = 1; 456 for (int i = 0; i < n; i++) { 457 cin >> src[i]; 458 maxA = max(maxA, src[i] + 1); 459 for (int bit = 0; bit < BITS; bit++) { 460 if ((1 << bit) & src[i]) { 461 continue; 462 } 463 464 bitCnt[bit].push_back(i); 465 } 466 } 467 468 bool incr[n]; 469 int cnt[maxA]; 470 int divBy[maxA]; 471 for (int i = 0; i < maxA; ++i) { 472 cnt[i] = 0; 473 divBy[i] = 0; 474 } 475 476 int pref[n]; 477 int suf[n]; 478 for (int i = 0; i < n; i++) { 479 incr[i] = false; 480 pref[i] = src[i]; 481 if (i) { 482 pref[i] = pref[i - 1] & src[i]; 483 } 484 } 485 486 for (int i = n - 2; i >= 0; i--) { 487 suf[n - 1] = src[n - 1]; 488 if (i < n - 1) { 489 suf[i] = suf[i + 1] & src[i]; 490 } 491 } 492 493 for (const auto& item : bitCnt) { 494 if (item.size() <= 2) { 495 for (const int& id : item) { 496 incr[id] = true; 497 int myAnd = -1; 498 for (int j = id + 1; j < n; j++) { 499 int curAND = (1 << BITS) - 1; 500 if (j + 1 < n) curAND &= suf[j + 1]; 501 if (id - 1 >= 0) curAND &= pref[id - 1]; 502 if (myAnd != -1) curAND &= myAnd; 503 504 if (curAND + x < __gcd(src[id], src[j])) { 505 coutYES(id, j); 506 return; 507 } 508 509 if (myAnd == -1) { 510 myAnd = src[j]; 511 } else { 512 myAnd &= src[j]; 513 } 514 } 515 516 myAnd = -1; 517 for (int j = id - 1; j >= 0; j--) { 518 int curAND = (1 << BITS) - 1; 519 520 if (j - 1 >= 0) curAND &= pref[j - 1]; 521 if (id + 1 < n) curAND &= suf[id + 1]; 522 if (myAnd != -1) curAND &= myAnd; 523 524 if (curAND + x < __gcd(src[id], src[j])) { 525 coutYES(id, j); 526 return; 527 } 528 529 if (myAnd == -1) { 530 myAnd = src[j]; 531 } else { 532 myAnd &= src[j]; 533 } 534 } 535 } 536 } 537 } 538 539 int AND = (1 << BITS) - 1; 540 for (int i = 0; i < BITS; i++) { 541 if (!bitCnt[i].empty()) { 542 AND ^= (1 << i); 543 } 544 } 545 546 for (int i = 0; i < n; i++) { 547 if (!incr[i]) { 548 ++cnt[src[i]]; 549 } 550 } 551 552 for (int i = 1; i < maxA; i++) { 553 for (int j = i; j < maxA; j += i) { 554 divBy[i] += cnt[j]; 555 } 556 } 557 558 for (int g = maxA - 1; g > AND + x; g--) { 559 if (divBy[g] < 2) { 560 continue; 561 } 562 563 int fId = -1; 564 int sId = -1; 565 for (int i = 0; i < n; i++) { 566 if (!incr[i]) { 567 if (src[i] % g == 0) { 568 if (fId == -1) { 569 fId = i; 570 } else { 571 sId = i; 572 } 573 } 574 } 575 } 576 coutYES(fId, sId); 577 return; 578 } 579 580 cout << "NO\n"; 581 } 582 583 int main() { 584 ios_base::sync_with_stdio(false); 585 cin.tie(nullptr); 586 cout.tie(nullptr); 587 588 int testN; 589 cin >> testN; 590 while (testN--) { 591 solve(); 592 } 593 return 0; 594 } 595 ```