codeforces-scrape

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

1538.md (9242B)


      1 Source: https://codeforces.com/blog/entry/91637
      2 
      3 [1538A - Stone Game](/contest/1538/problem/A "Codeforces Round 725 (Div. 3)")
      4 
      5 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 #include "random"
     16 
     17 using namespace std;
     18 
     19 using ll = long long;
     20 using ld = long double;
     21 using pii = pair<int, int>;
     22 using cd = complex<ld>;
     23 
     24 void solve() {
     25     int n;
     26     cin >> n;
     27     vector<int> v(n);
     28     for (int &e : v) {
     29         cin >> e;
     30     }
     31     int maxPos = max_element(v.begin(), v.end()) - v.begin();
     32     int minPos = min_element(v.begin(), v.end()) - v.begin();
     33     cout << min({
     34             max(maxPos, minPos) + 1,
     35             (n - 1) - min(maxPos, minPos) + 1,
     36             (n - 1) - maxPos + minPos + 2,
     37             (n - 1) - minPos + maxPos + 2
     38     }) << "\n";
     39 }
     40 
     41 int main() {
     42     ios_base::sync_with_stdio(false);
     43     cin.tie(nullptr);
     44     int t;
     45     cin >> t;
     46     while (t--) {
     47         solve();
     48     }
     49 }
     50 ```
     51 
     52 [1538B - Friends and Candies](/contest/1538/problem/B "Codeforces Round 725 (Div. 3)")
     53 
     54 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     55 
     56 **Tutorial**
     57 
     58 Tutorial is loading...
     59 
     60 **Solution**
     61 
     62 ```
     63 #include <bits/stdc++.h>
     64 
     65 using namespace std;
     66 
     67 using ll = long long;
     68 using ld = long double;
     69 using pii = pair<int, int>;
     70 using cd = complex<ld>;
     71 
     72 void solve() {
     73   int n;
     74   cin >> n;
     75   vector<int> a(n);
     76   int s = 0;
     77   for (int i = 0; i < n; i++) {
     78     cin >> a[i];
     79     s += a[i];
     80   }
     81   if (s % n != 0) {
     82     cout << "-1" << endl;
     83     return;
     84   }
     85   s /= n;
     86   int res = 0;
     87   for (int i = 0; i < n; i++) {
     88     if (s < a[i]) {
     89       res++;
     90     }
     91   }
     92   cout << res << endl;
     93 }
     94 
     95 int main() {
     96   int t;
     97   cin >> t;
     98   while (t--) {
     99     solve();
    100   }
    101   return 0;
    102 }
    103 ```
    104 
    105 [1538C - Number of Pairs](/contest/1538/problem/C "Codeforces Round 725 (Div. 3)")
    106 
    107 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    108 
    109 **Tutorial**
    110 
    111 Tutorial is loading...
    112 
    113 **Solution**
    114 
    115 ```
    116 #include <bits/stdc++.h>
    117 #include "random"
    118 
    119 using namespace std;
    120 
    121 using ll = long long;
    122 using ld = long double;
    123 using pii = pair<int, int>;
    124 using cd = complex<ld>;
    125 
    126 void solve() {
    127     int n, l, r;
    128     cin >> n >> l >> r;
    129     vector<int> v(n);
    130     for (int &e : v) {
    131         cin >> e;
    132     }
    133     sort(v.begin(), v.end());
    134     ll ans = 0;
    135     for (int i = 0; i < n; i++) {
    136         ans += upper_bound(v.begin(), v.end(), r - v[i]) - v.begin();
    137         ans -= lower_bound(v.begin(), v.end(), l - v[i]) - v.begin();
    138         if (l <= 2 * v[i] && 2 * v[i] <= r) {
    139             ans--;
    140         }
    141     }
    142     cout << ans / 2 << "\n";
    143 }
    144 
    145 int main() {
    146     ios_base::sync_with_stdio(false);
    147     cin.tie(nullptr);
    148     int t;
    149     cin >> t;
    150     while (t--) {
    151         solve();
    152     }
    153 }
    154 ```
    155 
    156 [1538D - Another Problem About Dividing Numbers](/contest/1538/problem/D "Codeforces Round 725 (Div. 3)")
    157 
    158 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    159 
    160 **Tutorial**
    161 
    162 Tutorial is loading...
    163 
    164 **Solution**
    165 
    166 ```
    167 #include <bits/stdc++.h>
    168 
    169 using namespace std;
    170 
    171 using ll = long long;
    172 using ld = long double;
    173 using pii = pair<int, int>;
    174 using cd = complex<ld>;
    175 
    176 const int N = 50'000;
    177 
    178 bool isPrime[N];
    179 vector<int> primes;
    180 
    181 void precalc() {
    182   fill(isPrime + 2, isPrime + N, true);
    183   for (int i = 2; i * i < N; i++) {
    184     for (int j = i * i; j < N; j += i) {
    185       isPrime[j] = false;
    186     }
    187   }
    188   for (int i = 2; i < N; i++) {
    189     if (isPrime[i]) {
    190       primes.push_back(i);
    191     }
    192   }
    193 }
    194 
    195 int calcPrime(int n) {
    196   int res = 0;
    197   for (int i : primes) {
    198     if (i * i > n) {
    199       break;
    200     }
    201     while (n % i == 0) {
    202       n /= i;
    203       res++;
    204     }
    205   }
    206   if (n > 1) {
    207     res++;
    208   }
    209   return res;
    210 }
    211 
    212 map<int, int> decompose(int n) {
    213   map<int, int> a;
    214   for (int i : primes) {
    215     if (i * i > n) {
    216       break;
    217     }
    218     int p = 0;
    219     while (n % i == 0) {
    220       n /= i;
    221       p++;
    222     }
    223     if (p > 0) {
    224       a[i] = p;
    225     }
    226   }
    227   if (n > 1) {
    228     a[n] = 1;
    229   }
    230   return a;
    231 }
    232 
    233 bool check(const map<int, int> &divs,
    234            map<int, int>::const_iterator it,
    235            map<int, int> &divsA,
    236            map<int, int> &divsB,
    237            int low,
    238            int high,
    239            int k) {
    240   if (it == divs.end()) {
    241     return __builtin_popcount(low) <= k && k <= high;
    242   }
    243   for (int p = 0; p <= it->second; p++) {
    244     int pa = divsA[it->first];
    245     int pb = divsB[it->first];
    246     int nextLow = low;
    247     if (p != pa) {
    248       nextLow |= 1;
    249     }
    250     if (p != pb) {
    251       nextLow |= 2;
    252     }
    253     if (check(divs, next(it), divsA, divsB, nextLow, high + pa + pb - 2 * p, k)) {
    254       return true;
    255     }
    256   }
    257   return false;
    258 }
    259 
    260 void solve() {
    261   int a, b, k;
    262   cin >> a >> b >> k;
    263   int g = __gcd(a, b);
    264   int low = 0;
    265   int high = 0;
    266   {
    267     int t;
    268     int ta = 1;
    269     while ((t = __gcd(a, g)) != 1) {
    270       a /= t;
    271       ta *= t;
    272     }
    273     high += calcPrime(a);
    274     if (a != 1) {
    275       low |= 1;
    276     }
    277     a = ta;
    278   }
    279   {
    280     int t;
    281     int tb = 1;
    282     while ((t = __gcd(b, g)) != 1) {
    283       b /= t;
    284       tb *= t;
    285     }
    286     high += calcPrime(b);
    287     if (b != 1) {
    288       low |= 2;
    289     }
    290     b = tb;
    291   }
    292   auto divs = decompose(g);
    293   auto divsA = decompose(a);
    294   auto divsB = decompose(b);
    295   cout << (check(divs, divs.begin(), divsA, divsB, low, high, k) ? "YES" : "NO") << endl;
    296 }
    297 
    298 int main() {
    299   precalc();
    300 
    301   int t;
    302   cin >> t;
    303   while (t--) {
    304     solve();
    305   }
    306 
    307   return 0;
    308 }
    309 ```
    310 
    311 [1538E - Funny Substrings](/contest/1538/problem/E "Codeforces Round 725 (Div. 3)")
    312 
    313 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    314 
    315 **Tutorial**
    316 
    317 Tutorial is loading...
    318 
    319 **Solution**
    320 
    321 ```
    322 #include <bits/stdc++.h>
    323 #include "random"
    324 
    325 using namespace std;
    326 
    327 using ll = long long;
    328 using ld = long double;
    329 using pii = pair<int, int>;
    330 using cd = complex<ld>;
    331 
    332 vector<string> split(const string& s, char p) {
    333     vector<string> res(1);
    334     for (char c : s) {
    335         if (c == p) {
    336             res.emplace_back();
    337         } else {
    338             res.back() += c;
    339         }
    340     }
    341     return res;
    342 }
    343 
    344 struct Word {
    345     ll len;
    346     ll cnt;
    347     string s;
    348 };
    349 
    350 string getFirst(string s) {
    351     if (s.size() < 3) {
    352         return s;
    353     }
    354     return s.substr(0, 3);
    355 }
    356 
    357 string getLast(string s) {
    358     if (s.size() < 3) {
    359         return s;
    360     }
    361     return s.substr(s.size() - 3, 3);
    362 }
    363 
    364 int count(const string& s, const string& p) {
    365     int cnt = 0;
    366     for (int i = 0; i + p.size() <= s.size(); i++) {
    367         if (s.substr(i, p.size()) == p) {
    368             cnt++;
    369         }
    370     }
    371     return cnt;
    372 }
    373 
    374 Word merge(const Word& a, const Word& b) {
    375     Word c;
    376     c.len = a.len + b.len;
    377     c.s = a.s + b.s;
    378     c.cnt = a.cnt + b.cnt + count(getLast(a.s) + getFirst(b.s), "haha");
    379     if (c.s.size() >= 7) {
    380         c.s = getFirst(c.s) + "@" + getLast(c.s);
    381     }
    382     return c;
    383 }
    384 
    385 void solve() {
    386     int n;
    387     cin >> n;
    388     map<string, Word> vars;
    389     ll ans = 0;
    390     for (int i = 0; i < n; i++) {
    391         string var;
    392         cin >> var;
    393         string opr;
    394         cin >> opr;
    395         if (opr == "=") {
    396             string a, plus, b;
    397             cin >> a >> plus >> b;
    398             vars[var] = merge(vars[a], vars[b]);
    399         } else {
    400             string str;
    401             cin >> str;
    402             Word word;
    403             word.len = str.length();
    404             word.cnt = count(str, "haha");
    405             word.s = str;
    406             vars[var] = word;
    407         }
    408         ans = vars[var].cnt;
    409     }
    410     cout << ans << "\n";
    411 }
    412 
    413 int main() {
    414     ios_base::sync_with_stdio(false);
    415     cin.tie(nullptr);
    416     int t;
    417     cin >> t;
    418     while (t--) {
    419         solve();
    420     }
    421 }
    422 ```
    423 
    424 [1538F - Interesting Function](/contest/1538/problem/F "Codeforces Round 725 (Div. 3)")
    425 
    426 Author: [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz"), [Stepavly](/profile/Stepavly "Candidate Master Stepavly")
    427 
    428 **Tutorial**
    429 
    430 Tutorial is loading...
    431 
    432 **Solution**
    433 
    434 ```
    435 #include <iostream>
    436 
    437 using namespace std;
    438 
    439 void solve () {
    440   int L, R;
    441   cin >> L >> R;
    442 
    443   int ans = 0;
    444   while (L != 0 || R != 0) {
    445     ans += R - L;
    446     L /= 10;
    447     R /= 10;
    448   }
    449   cout << ans << '\n';
    450 }
    451 
    452 int main () {
    453   ios::sync_with_stdio(false);
    454   cin.tie(0);
    455   
    456   int testc;
    457   cin >> testc;
    458 
    459   for (int i = 0; i < testc; i++) {
    460     solve();
    461   }
    462 }
    463 ```
    464 
    465 [1538G - Gift Set](/contest/1538/problem/G "Codeforces Round 725 (Div. 3)")
    466 
    467 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    468 
    469 **Tutorial**
    470 
    471 Tutorial is loading...
    472 
    473 **Solution**
    474 
    475 ```
    476 #include <bits/stdc++.h>
    477 #include "random"
    478 
    479 using namespace std;
    480 
    481 using ll = long long;
    482 using ld = long double;
    483 using pii = pair<int, int>;
    484 using cd = complex<ld>;
    485 
    486 void solve() {
    487     ll x, y, a, b;
    488     cin >> x >> y >> a >> b;
    489     ll l = 0, r = 1e9 + 100;
    490     if (a == b) {
    491         cout << min(x, y) / a << "\n";
    492         return;
    493     }
    494     if (a < b) {
    495         swap(a, b);
    496     }
    497     while (r - l > 1) {
    498         ll m = (l + r) / 2;
    499         ll right = floorl((x - m * b) * 1.0l / (a - b));
    500         ll left = ceill((y - m * a) * 1.0l / (b - a));
    501         if (max(left, 0ll) <= min(right, m)) {
    502             l = m;
    503         } else {
    504             r = m;
    505         }
    506     }
    507     cout << l << "\n";
    508 }
    509 
    510 int main() {
    511     ios_base::sync_with_stdio(false);
    512     cin.tie(nullptr);
    513     int t;
    514     cin >> t;
    515     while (t--) {
    516         solve();
    517     }
    518 }
    519 ```