codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```