codeforces-scrape

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

1027.md (14006B)


      1 Source: https://codeforces.com/blog/entry/61311
      2 
      3 [1027A - Palindromic Twist](/contest/1027/problem/A "Educational Codeforces Round 49 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (PikMike)**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 
     14 #define forn(i, n) for (int i = 0; i < int(n); i++)
     15 
     16 using namespace std;
     17 
     18 int main() {
     19     int T;
     20     cin >> T;
     21     
     22     int n;
     23     string s;
     24     forn(_, T){
     25         cin >> n >> s;
     26         bool ok = true;
     27         forn(i, n){
     28             int k = abs(s[i] - s[n - i - 1]);
     29             if (k > 2 || k % 2 == 1){
     30                 ok = false;
     31                 break;
     32             }
     33         }
     34         cout << (ok ? "YES" : "NO") << endl;
     35     }
     36     return 0;
     37 }
     38 ```
     39 
     40 [1027B - Numbers on the Chessboard](/contest/1027/problem/B "Educational Codeforces Round 49 (Rated for Div. 2)")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution (Vovuh)**
     47 
     48 ```
     49 import sys
     50 
     51 lst = sys.stdin.readlines()
     52 n, q = map(int, lst[0].split())
     53 
     54 for i in range(q):
     55     x, y = map(int, lst[i + 1].split())
     56     cnt = (x - 1) * n + y
     57     ans = (cnt + 1) // 2
     58     if ((x + y) % 2 == 1): ans += (n * n + 1) // 2
     59     sys.stdout.write(str(ans) + '\n')
     60 ```
     61 
     62 [1027C - Minimum Value Rectangle](/contest/1027/problem/C "Educational Codeforces Round 49 (Rated for Div. 2)")
     63 
     64 **Tutorial**
     65 
     66 Tutorial is loading...
     67 
     68 **Solution (PikMike)**
     69 
     70 ```
     71 #include <bits/stdc++.h>
     72 
     73 #define forn(i, n) for (int i = 0; i < int(n); i++)
     74 
     75 typedef long long li;
     76 
     77 using namespace std;
     78 
     79 const int N = 1000 * 1000 + 13;
     80 
     81 int n, m;
     82 int a[N];
     83 int b[N];
     84 
     85 int main() {
     86     int T;
     87     scanf("%d", &T);
     88     forn(_, T){
     89         scanf("%d", &n);
     90         forn(i, n)
     91             scanf("%d", &a[i]);
     92         sort(a, a + n);
     93     
     94         m = 0;
     95         forn(i, n - 1){
     96             if (a[i] == a[i + 1]){
     97                 b[m++] = a[i];
     98                 ++i;
     99             }
    100         }
    101     
    102         int A = b[0], B = b[1];
    103         li P2 = (A + B) * li(A + B);
    104         li S = A * li(B);
    105     
    106         forn(i, m - 1){
    107             li p2 = (b[i] + b[i + 1]) * li(b[i] + b[i + 1]);
    108             li s = b[i] * li(b[i + 1]);
    109             if (s * P2 > S * p2){
    110                 A = b[i];
    111                 B = b[i + 1];
    112                 S = s;
    113                 P2 = p2;
    114             }
    115         }
    116     
    117         printf("%d %d %d %d\n", A, A, B, B);
    118     }
    119 }
    120 ```
    121 
    122 [1027D - Mouse Hunt](/contest/1027/problem/D "Educational Codeforces Round 49 (Rated for Div. 2)")
    123 
    124 **Tutorial**
    125 
    126 Tutorial is loading...
    127 
    128 **Solution (adedalic)**
    129 
    130 ```
    131 #include<bits/stdc++.h>
    132 
    133 using namespace std;
    134 
    135 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    136 #define forn(i, n) fore(i, 0, n)
    137 
    138 #define mp make_pair
    139 #define pb push_back
    140 
    141 #define sz(a) int((a).size())
    142 #define all(a) (a).begin(), (a).end()
    143 #define sqr(a) ((a) * (a))
    144 
    145 #define x first
    146 #define y second
    147 
    148 typedef long long li;
    149 typedef long double ld;
    150 typedef pair<li, li> pt;
    151 
    152 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    153     return out << "(" << p.x << ", " << p.y << ")";
    154 }
    155 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    156     out << "[";
    157     forn(i, sz(v)) {
    158         if(i) out << ", ";
    159         out << v[i];
    160     }
    161     return out << "]";
    162 }
    163 
    164 const int INF = int(1e9);
    165 const li INF64 = li(1e18);
    166 const ld EPS = 1e-9;
    167 
    168 int n;
    169 vector<int> a, c;
    170 
    171 inline bool read() {
    172     if(!(cin >> n))
    173         return false;
    174     c.assign(n, 0);
    175     a.assign(n, 0);
    176 
    177     forn(i, n)
    178         assert(scanf("%d", &c[i]) == 1);
    179     forn(i, n) {
    180         assert(scanf("%d", &a[i]) == 1);
    181         a[i]--;
    182     }
    183     return true;
    184 }
    185 
    186 vector< vector<int> > cycles;
    187 
    188 vector<char> used;
    189 vector<int> path;
    190 
    191 void dfs(int v) {
    192     path.push_back(v);
    193     used[v] = 1;
    194 
    195     int to = a[v];
    196     if(used[to] != 2) {
    197         if(used[to] == 1) {
    198             cycles.emplace_back();
    199 
    200             int id = sz(path) - 1;
    201             while(path[id] != to)
    202                 cycles.back().push_back(path[id--]);
    203             cycles.back().push_back(to);
    204         } else
    205             dfs(to);
    206     }
    207     path.pop_back();
    208     used[v] = 2;
    209 }
    210 
    211 inline void solve() {
    212     used.assign(n, 0);
    213 
    214     forn(i, n) {
    215         if (!used[i])
    216             dfs(i);
    217     }
    218 
    219     li ans = 0;
    220     for(auto &cur : cycles) {
    221         int mn = c[cur[0]];
    222         for(int v : cur)
    223             mn = min(mn, c[v]);
    224         ans += mn;
    225     }
    226     cout << ans << endl;
    227 }
    228 
    229 int main() {
    230 #ifdef _DEBUG
    231     freopen("input.txt", "r", stdin);
    232     int tt = clock();
    233 #endif
    234     cout << fixed << setprecision(15);
    235 
    236     if(read()) {
    237         solve();
    238 
    239 #ifdef _DEBUG
    240         cerr << "TIME = " << clock() - tt << endl;
    241         tt = clock();
    242 #endif
    243     }
    244     return 0;
    245 }
    246 ```
    247 
    248 [1027E - Inverse Coloring](/contest/1027/problem/E "Educational Codeforces Round 49 (Rated for Div. 2)")
    249 
    250 **Tutorial**
    251 
    252 Tutorial is loading...
    253 
    254 **Solution (PikMike) O(n^3)**
    255 
    256 ```
    257 #include <bits/stdc++.h>
    258 
    259 #define forn(i, n) for (int i = 0; i < int(n); i++)
    260 
    261 using namespace std;
    262 
    263 const int N = 500 + 7;
    264 const int MOD = 998244353;
    265 
    266 int n, k;
    267 int dp[2][N][N];
    268 int cnt[N];
    269 int pr[N];
    270 
    271 void add(int &a, int b){
    272     a += b;
    273     if (a >= MOD)
    274         a -= MOD;
    275 }
    276 
    277 int main() {
    278     scanf("%d%d", &n, &k);
    279     
    280     dp[0][0][0] = 1;
    281     forn(ii, n){
    282         int i = ii & 1;
    283         int ni = i ^ 1;
    284         memset(dp[ni], 0, sizeof(dp[ni]));
    285         forn(j, n + 1){
    286             forn(k, n + 1){
    287                 add(dp[ni][j + 1][max(j + 1, k)], dp[i][j][k]);
    288                 add(dp[ni][1][max(1, k)], dp[i][j][k]);
    289             }
    290         }
    291     }
    292     
    293     forn(i, n + 1)
    294         forn(j, n + 1)
    295             add(cnt[i], dp[n & 1][j][i]);
    296     
    297     forn(i, n + 1){
    298         add(pr[i + 1], pr[i]);
    299         add(pr[i + 1], cnt[i]);
    300     }
    301     
    302     int ans = 0;
    303     for (int i = 1; i <= n; ++i)
    304         add(ans, cnt[i] * (long long)(pr[min(n + 1, (k - 1) / i + 1)]) % MOD);
    305     
    306     ans = (ans * (long long)((MOD + 1) / 2)) % MOD;
    307     printf("%d\n", ans);
    308     
    309     return 0;
    310 }
    311 ```
    312 
    313 **Solution (BledDest) O(n^2)**
    314 
    315 ```
    316 def norm(x):
    317     return (x % 998244353 + 998244353) % 998244353
    318 
    319 n, k = map(int, input().split())
    320 
    321 dp1 = [0]
    322 dp2 = [0]
    323 
    324 for i in range(n):
    325     l = [1]
    326     cur = 0
    327     for j in range(n + 1):
    328         cur += l[j]
    329         if(j > i):
    330             cur -= l[j - i - 1]
    331         cur = norm(cur)
    332         l.append(cur)
    333     dp1.append(l[n])
    334     dp2.append(norm(dp1[i + 1] - dp1[i]))
    335 
    336 ans = 0
    337 for i in range(n + 1):
    338     for j in range(n + 1):
    339         if(i * j < k):
    340             ans = norm(ans + dp2[i] * dp2[j])
    341 
    342 ans = norm(ans * 2)
    343 
    344 print(ans)
    345 ```
    346 
    347 [1027F - Session in BSU](/contest/1027/problem/F "Educational Codeforces Round 49 (Rated for Div. 2)")
    348 
    349 **Tutorial**
    350 
    351 Tutorial is loading...
    352 
    353 **Solution (Vovuh)**
    354 
    355 ```
    356 #include <bits/stdc++.h>
    357 
    358 using namespace std;
    359 
    360 #define forn(i, n) for (int i = 0; i < int(n); ++i)
    361 
    362 const int N = 2 * 1000 * 1000 + 11;
    363 const int INF = 1e9 + 1;
    364 
    365 int n;
    366 int a[N][2];
    367 vector<int> s;
    368 bool used[N];
    369 bool exam[N];
    370 vector<pair<int, int>> g[N];
    371 
    372 bool deny(int v) {
    373     if (used[v]) return false;
    374     used[v] = true;
    375     for (auto it : g[v]) {
    376         int to = it.first;
    377         int ex = it.second;
    378         if (exam[ex]) continue;
    379         if (used[to])
    380             return false;
    381         exam[ex] = true;
    382         if (!deny(to))
    383             return false;
    384     }
    385     return true;
    386 }
    387 
    388 int cntv, cnte;
    389 
    390 void dfs(int v) {
    391     ++cntv;
    392     used[v] = true;
    393     for (auto it : g[v]) {
    394         int to = it.first;
    395         int ex = it.second;
    396         if (exam[ex]) continue;
    397         exam[ex] = true;
    398         ++cnte;
    399         if (!used[to])
    400             dfs(to);
    401     }
    402 }
    403 
    404 bool check(int day) {
    405     memset(used, false, sizeof(used));
    406     memset(exam, false, sizeof(exam));
    407     forn(i, s.size()) if (i > day) {
    408         if (!deny(i)) {
    409             return false;
    410         }
    411     }
    412     
    413     forn(i, s.size()) {
    414         if (!used[i]) {
    415             cntv = 0;
    416             cnte = 0;
    417             dfs(i);
    418             if (cntv < cnte)
    419                 return false;
    420         }
    421     }
    422     
    423     return true;
    424 }
    425 
    426 int main() {
    427     scanf("%d", &n);
    428     forn(i, n) forn(j, 2) {
    429         scanf("%d", &a[i][j]);
    430         s.push_back(a[i][j]);
    431     }
    432     
    433     sort(s.begin(), s.end());
    434     s.resize(unique(s.begin(), s.end()) - s.begin());
    435     
    436     forn(i, n) {
    437         forn(j, 2) {
    438             a[i][j] = lower_bound(s.begin(), s.end(), a[i][j]) - s.begin();
    439         }
    440         g[a[i][0]].push_back(make_pair(a[i][1], i));
    441         g[a[i][1]].push_back(make_pair(a[i][0], i));
    442     }
    443         
    444     int l = 0, r = int(s.size()) - 1;
    445     while (r - l > 1) {
    446         int mid = (l + r) >> 1;
    447         if (check(mid))
    448             r = mid;
    449         else
    450             l = mid;
    451     }
    452     for (int i = l; i <= r; ++i) {
    453         if (check(i)) {
    454             printf("%d\n", s[i]);
    455             return 0;
    456         }
    457     }
    458     puts("-1");
    459 }
    460 ```
    461 
    462 **Solution (Vovuh) Kuhn's Algorithm**
    463 
    464 ```
    465 #include <bits/stdc++.h>
    466 
    467 using namespace std;
    468 
    469 mt19937 rnd(time(NULL));
    470 
    471 const int N = 2 * 1000 * 1000 + 11;
    472 const int INF = 1e9;
    473 
    474 int n;
    475 int a[N][2];
    476 
    477 vector<int> nums;
    478 int m;
    479 
    480 vector<int> g[N];
    481 int mt[N];
    482 int used[N];
    483 int T = 1;
    484 
    485 bool try_kuhn(int v) {
    486     if (used[v] == T)
    487         return false;
    488     used[v] = T;
    489     
    490     for (auto to : g[v]) {
    491         if (mt[to] == -1) {
    492             mt[to] = v;
    493             return true;
    494         }
    495     }
    496     
    497     for (auto to : g[v]) {
    498         if (try_kuhn(mt[to])) {
    499             mt[to] = v;
    500             return true;
    501         }
    502     }
    503     
    504     return false;
    505 }
    506 
    507 int main() {
    508 #ifdef _DEBUG
    509     freopen("input.txt", "r", stdin);
    510 //  freopen("output.txt", "w", stdout);
    511 #endif
    512 
    513     scanf("%d", &n);
    514     for (int i = 0; i < n; ++i) {
    515         for (int j = 0; j < 2; ++j) {
    516             scanf("%d", &a[i][j]);
    517             nums.push_back(a[i][j]);
    518         }
    519     }
    520     
    521     sort(nums.begin(), nums.end());
    522     nums.resize(unique(nums.begin(), nums.end()) - nums.begin());
    523     m = nums.size();
    524     
    525     for (int i = 0; i < n; ++i) {
    526         for (int j = 0; j < 2; ++j) {
    527             a[i][j] = lower_bound(nums.begin(), nums.end(), a[i][j]) - nums.begin();
    528         }
    529     }
    530     
    531     for (int i = 0; i < n; ++i) {
    532         g[a[i][0]].push_back(i);
    533         g[a[i][1]].push_back(i);
    534     }
    535 
    536     memset(mt, -1, sizeof(mt)); 
    537     int match = 0;
    538     for (int i = 0; i < m; ++i) {
    539         if (try_kuhn(i)) {
    540             ++T;
    541             ++match;
    542             if (match == n) {
    543                 printf("%d\n", nums[i]);
    544                 return 0;
    545             }
    546         }
    547     }
    548     
    549     puts("-1");
    550     
    551     return 0;
    552 }
    553 ```
    554 
    555 [1027G - X-mouse in the Campus](/contest/1027/problem/G "Educational Codeforces Round 49 (Rated for Div. 2)")
    556 
    557 **Tutorial**
    558 
    559 Tutorial is loading...
    560 
    561 **Solution (adedalic)**
    562 
    563 ```
    564 #include<bits/stdc++.h>
    565 
    566 using namespace std;
    567 
    568 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    569 #define sz(a) int((a).size())
    570 
    571 #define x first
    572 #define y second
    573 
    574 typedef long long li;
    575 typedef long double ld;
    576 typedef pair<li, li> pt;
    577 
    578 const int INF = int(1e9);
    579 const li INF64 = li(1e18);
    580 const ld EPS = 1e-9;
    581 
    582 li m, x;
    583 
    584 inline bool read() {
    585     if(!(cin >> m >> x))
    586         return false;
    587     return true;
    588 }
    589 
    590 map< li, vector<pt> > dFact;
    591 vector<pt> fact(li v) {
    592     if(dFact.count(v))
    593         return dFact[v];
    594     
    595     li oldv = v;
    596     vector<pt> fs;
    597     for(li d = 2; d * d <= v; d++) {
    598         int cnt = 0;
    599         while(v % d == 0)
    600             v /= d, cnt++;
    601         
    602         if(cnt > 0)
    603             fs.emplace_back(d, cnt);
    604     }
    605     if(v > 1)
    606         fs.emplace_back(v, 1), v = 1;
    607     return dFact[oldv] = fs;
    608 }
    609 
    610 vector<pt> merge(const vector<pt> &a, const vector<pt> &b) {
    611     vector<pt> ans;
    612     int u = 0, v = 0;
    613     while(u < sz(a) && v < sz(b)) {
    614         if(a[u].x < b[v].x)
    615             ans.push_back(a[u++]);
    616         else if(a[u].x > b[v].x)
    617             ans.push_back(b[v++]);
    618         else {
    619             ans.emplace_back(a[u].x, a[u].y + b[v].y);
    620             u++, v++;
    621         }
    622     }
    623     while(u < sz(a))
    624         ans.push_back(a[u++]);
    625     while(v < sz(b))
    626         ans.push_back(b[v++]);
    627     return ans;
    628 }
    629 
    630 li getPw(li a, li b) {
    631     li ans = 1;
    632     fore(i, 0, b)
    633         ans *= a;
    634     return ans;
    635 }
    636 
    637 li mul(li a, li b, li mod) {
    638     li m = li(ld(a) * b / mod);
    639     li rem = a * b - m * mod;
    640     while(rem < 0)
    641         rem += mod;
    642     while(rem >= mod)
    643         rem -= mod;
    644     return rem;
    645 }
    646 
    647 li binPow(li a, li k, li mod) {
    648     li ans = 1 % mod;
    649     while(k > 0) {
    650         if(k & 1)
    651             ans = mul(ans, a, mod);
    652         a = mul(a, a, mod);
    653         k >>= 1;
    654     }
    655     return ans;
    656 }
    657 
    658 li findOrder(li x, li mod, const vector<pt> &f) {
    659     li phi = 1;
    660     fore(i, 0, sz(f)) fore(k, 0, f[i].y)
    661         phi *= f[i].x;
    662         
    663     if(phi == 1 || x == 0)
    664         return 1;
    665     
    666     li ord = 1;
    667     fore(i, 0, sz(f)) {
    668         li basePw = phi;
    669         fore(k, 0, f[i].y)
    670             basePw /= f[i].x;
    671         
    672         li curV = binPow(x, basePw, mod);
    673         
    674         int curPw = -1;
    675         fore(k, 0, f[i].y + 1) {
    676             if(curV != 1)
    677                 curPw = k;
    678             curV = binPow(curV, f[i].x, mod);
    679         }
    680         
    681         ord *= getPw(f[i].x, curPw + 1);
    682     }
    683     return ord;
    684 }
    685 
    686 vector<pt> fm;
    687 vector<int> pw;
    688 
    689 li calc(int pos, li dv) {
    690     if(pos >= sz(fm)) {
    691         vector<pt> cf = fm;
    692         fore(i, 0, sz(fm))
    693             cf[i].y = max(pw[i] - 1, 0);
    694         
    695         li phi = dv;
    696         fore(i, 0, sz(fm)) {
    697             if(pw[i] > 0) {
    698                 cf = merge(cf, fact(fm[i].x - 1));
    699                 phi -= phi / fm[i].x;
    700             }
    701         }
    702         li k = findOrder(x % dv, dv, cf);
    703         return phi / k;
    704     }
    705     
    706     li ans = 0;
    707     fore(i, 0, fm[pos].y + 1) {
    708         pw[pos] = i;
    709         ans += calc(pos + 1, dv);
    710         dv *= fm[pos].x;
    711     }
    712     return ans;
    713 }
    714 
    715 inline void solve() {
    716     fm = fact(m);
    717     
    718     pw.assign(sz(fm), 0);
    719     li ans = calc(0, 1);
    720     
    721     cout << ans << endl;
    722 }
    723 
    724 int main() {
    725 #ifdef _DEBUG
    726     freopen("input.txt", "r", stdin);
    727     int tt = clock();
    728 #endif
    729     cout << fixed << setprecision(15);
    730     
    731     if(read()) {
    732         solve();
    733         
    734 #ifdef _DEBUG
    735         cerr << "TIME = " << clock() - tt << endl;
    736         tt = clock();
    737 #endif
    738     }
    739     return 0;
    740 }
    741 ```