codeforces-scrape

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

1264.md (14101B)


      1 Source: https://codeforces.com/blog/entry/71995
      2 
      3 Tutorial is loading...
      4 
      5 **Python Solution**
      6 
      7 ```
      8 T = int(input())
      9 for tc in range(T):
     10     s = [c for c in input()]
     11     n = len(s)
     12     i = 0
     13     while (i < n):
     14         if (s[i] == '?'):
     15             prv = 'd' if i == 0 else s[i - 1]
     16             nxt = 'e' if i + 1 >= n else s[i + 1]
     17             for x in ['a', 'b', 'c']:
     18                 if (x != prv) and (x != nxt):
     19                     s[i] = x
     20                     break
     21         else:
     22             i += 1
     23            
     24     ok = True 
     25     for i in range(n - 1):
     26         if (s[i] == s[i + 1]):
     27             print("-1")
     28             ok = False
     29             break
     30     if (ok == True):  
     31         print("".join(s))
     32 ```
     33 
     34 Author: [isaf27](/profile/isaf27 "International Grandmaster isaf27"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen")
     35 
     36 Tutorial is loading...
     37 
     38 **C++ solution**
     39 
     40 ```
     41 #include <bits/stdc++.h>
     42 
     43 using namespace std;
     44 
     45 const int M = 2e5 + 239;
     46 
     47 int n, p[M], x;
     48 
     49 void solve()
     50 {
     51     cin >> n;
     52     for (int i = 0; i < n; i++)
     53     {
     54         cin >> x;
     55         p[x - 1] = i;
     56     }
     57     int l = n;
     58     int r = 0;
     59     string ans = "";
     60     for (int i = 0; i < n; i++)
     61     {
     62         l = min(l, p[i]);
     63         r = max(r, p[i]);
     64         if (r - l == i)
     65             ans += '1';
     66         else
     67             ans += '0';
     68     }
     69     cout << ans << "\n";
     70 }
     71 
     72 int main()
     73 {
     74     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     75     int t;
     76     cin >> t;
     77     while (t--)
     78         solve();
     79     return 0;
     80 }
     81 ```
     82 
     83 Author: [isaf27](/profile/isaf27 "International Grandmaster isaf27"), prepare [isaf27](/profile/isaf27 "International Grandmaster isaf27")
     84 
     85 Tutorial is loading...
     86 
     87 **C++ solution**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 
     92 using namespace std;
     93 
     94 #define forn(i, n) for (int i = 0; i < int(n); i++)
     95 
     96 int main() {
     97     int t;
     98     cin >> t;
     99     forn(tt, t) {
    100         int n;
    101         cin >> n;
    102         map<int,int> c;
    103         forn(i, n) {
    104             int pi;
    105             cin >> pi;
    106             c[-pi]++;
    107         }
    108         vector<int> pp;
    109         for (auto p: c)
    110             pp.push_back(p.second);
    111         bool ok = false;
    112         int g = pp[0];
    113         int i = 1;
    114         int s = 0;
    115         while (s <= g && i < pp.size())
    116             s += pp[i++];
    117         if (g < s) {
    118            int b = 0;
    119            while (b <= g && i < pp.size())
    120                b += pp[i++];
    121            while (i < pp.size() && g + s + b + pp[i] <= n / 2)
    122                b += pp[i++];
    123            if (g < b && g + s + b <= n / 2) {
    124                ok = true;
    125                cout << g << " " << s << " " << b << endl;
    126            }
    127         }
    128         if (!ok)
    129             cout << 0 << " " << 0 << " " << 0 << endl;
    130     }
    131 }
    132 ```
    133 
    134 Author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), prepare [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    135 
    136 Tutorial is loading...
    137 
    138 **C++ Solution**
    139 
    140 ```
    141 #include <bits/stdc++.h>
    142 using namespace std;
    143 
    144 int main() {
    145     map<int, int> hs;
    146     cin >> hs[0] >> hs[1] >> hs[2] >> hs[3];
    147     int total = hs[0] + hs[1] + hs[2] + hs[3];
    148     for (int st = 0; st < 4; st++) if (hs[st]) {
    149         vector<int> res;
    150         auto ths = hs;
    151         ths[st]--;
    152         res.push_back(st);
    153         int last = st;
    154         for (int i = 0; i < total - 1; i++) {
    155             if (ths[last - 1]) {
    156                 ths[last - 1]--;
    157                 res.push_back(last - 1);
    158                 last--;
    159             }
    160             else if (ths[last + 1]) {
    161                 ths[last + 1]--;
    162                 res.push_back(last + 1);
    163                 last++;
    164             }
    165             else {
    166                 break;
    167             }
    168         }
    169         if ((int) res.size() == total) {
    170             cout << "YES\n";
    171             for (int i = 0; i < (int) res.size(); i++) {
    172                 cout << res[i] << " \n"[i == (int) res.size() - 1];
    173             }
    174             return 0;
    175         }
    176     }
    177     cout << "NO\n";
    178     return 0;
    179 }
    180 ```
    181 
    182 Author: [laoriu](/profile/laoriu "Master laoriu"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen")
    183 
    184 Tutorial is loading...
    185 
    186 **C++ Solution**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 using namespace std;
    191 
    192 const int MOD = 119 << 23 | 1;
    193 
    194 int inv(int a) {
    195     int r = 1, t = a, k = MOD - 2;
    196     while (k) {
    197         if (k & 1) r = (long long) r * t % MOD;
    198         t = (long long) t * t % MOD;
    199         k >>= 1;
    200     }
    201     return r;
    202 }
    203 
    204 int main() {
    205     int n; cin >> n;
    206     vector<int> p(n);
    207     for (int i = 0; i < n; i++) cin >> p[i], p[i] = (long long) p[i] * inv(100) % MOD;
    208     int a = 1, b = 0;
    209     for (int i = 0; i < n; i++) {
    210         a = (long long) a * inv(p[i]) % MOD;
    211         b = (long long) b * inv(p[i]) % MOD;
    212         a = (a + (long long) (p[i] - 1) * inv(p[i])) % MOD;
    213         b = (b - inv(p[i]) + MOD) % MOD;
    214     }
    215     cout <<  (long long) (MOD - b) * inv(a) % MOD << "\n";
    216     return 0;
    217 }
    218 ```
    219 
    220 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen")
    221 
    222 Tutorial is loading...
    223 
    224 **C++ Solution**
    225 
    226 ```
    227 #include <bits/stdc++.h>
    228 using namespace std;
    229 
    230 const int MOD = 119 << 23 | 1;
    231 
    232 int fpow(int a, int k) {
    233     int r = 1, t = a;
    234     while (k) {
    235         if (k & 1) r = (long long) r * t % MOD;
    236         t = (long long) t * t % MOD;
    237         k >>= 1;
    238     }
    239     return r;
    240 }
    241 
    242 int main() {
    243     string s; cin >> s;
    244     int n = s.size();
    245     vector<vector<int>> dp(n, vector<int>(n));
    246     vector<int> f(n + 1);
    247     for (int i = 0; i < n; i++) {
    248         f[i + 1] = f[i];
    249         f[i + 1] += s[i] == '?';
    250     }
    251     for (int len = 2; len <= n; len++) {
    252         for (int i = 0; i < n - len + 1; i++) {
    253             int j = i + len - 1;
    254             if (s[i] != '(') {
    255                 dp[i][j] += dp[i + 1][j];
    256                 dp[i][j] %= MOD;
    257             }
    258             if (s[j] != ')') {
    259                 dp[i][j] += dp[i][j - 1];
    260                 dp[i][j] %= MOD;
    261             }
    262             if (s[i] != '(' && s[j] != ')') {
    263                 dp[i][j] -= dp[i + 1][j - 1];
    264                 dp[i][j] += MOD;
    265                 dp[i][j] %= MOD;
    266             }
    267             if (s[i] != ')' && s[j] != '(') {
    268                 dp[i][j] += dp[i + 1][j - 1];
    269                 dp[i][j] %= MOD;
    270                 dp[i][j] += fpow(2, f[j] - f[i + 1]);
    271                 dp[i][j] %= MOD;
    272             }
    273         }
    274     }
    275     cout << dp[0][n - 1] << "\n";
    276     return 0;
    277 }
    278 ```
    279 
    280 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen")
    281 
    282 Tutorial is loading...
    283 
    284 **C++ Solution**
    285 
    286 ```
    287 #include <bits/stdc++.h>
    288 using namespace std;
    289 
    290 const int MOD = 119 << 23 | 1;
    291 
    292 struct node_t {
    293     int prd;
    294     int val;
    295     node_t() {
    296         prd = val = 0;
    297     }
    298 };
    299 
    300 node_t operator + (node_t a, node_t b) {
    301     if (!a.prd) return b;
    302     if (!b.prd) return a;
    303     node_t c;
    304     c.prd = (long long) a.prd * b.prd % MOD;
    305     c.val = (long long) a.val * b.prd % MOD;
    306     c.val = (c.val + b.val) % MOD;
    307     return c;
    308 }
    309 
    310 int inv(int a) {
    311     int r = 1, t = a, k = MOD - 2;
    312     while (k) {
    313         if (k & 1) r = (long long) r * t % MOD;
    314         t = (long long) t * t % MOD;
    315         k >>= 1;
    316     }
    317     return r;
    318 }
    319 
    320 int main() {
    321     int n, q; cin >> n >> q;
    322     vector<int> p(n);
    323     for (int i = 0; i < n; i++) cin >> p[i], p[i] = (long long) p[i] * inv(100) % MOD;
    324     vector<node_t> st(n << 2);
    325     auto upd = [&] (int p, node_t val) {
    326         for (st[p += n] = val; 1 < p; ) p >>= 1, st[p] = st[p << 1] + st[p << 1 | 1];
    327     };
    328     auto query = [&] (int l, int r) {
    329         node_t lres, rres;
    330         for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
    331             if (l & 1) {
    332                 lres = lres + st[l++];
    333             }
    334             if (r & 1) {
    335                 rres = st[--r] + rres;
    336             }
    337         }
    338         return (lres + rres).val;
    339     };
    340     for (int i = 0; i < n; i++) {
    341         node_t c;
    342         c.val = c.prd = inv(p[i]);
    343         upd(i, c);
    344     }
    345     set<int> ss;
    346     ss.insert(0);
    347     int res = query(0, n - 1);
    348     for (int i = 0; i < q; i++) {
    349         string op; int u; cin >> u; u--;
    350         auto it = ss.lower_bound(u);
    351         if (it == ss.end() || *it != u) {
    352             it = ss.insert(u).first;
    353             int lo = *(--it);
    354             it++;
    355             int hi = n;
    356             if (++it != ss.end()) {
    357                 hi = *it;
    358             }
    359             res -= query(lo, hi - 1);
    360             res += MOD;
    361             res %= MOD;
    362             res += query(lo, u - 1);
    363             res %= MOD;
    364             res += query(u, hi - 1);
    365             res %= MOD;
    366         }
    367         else {
    368             int lo = *(--it);
    369             it++;
    370             int hi = n;
    371             if (++it != ss.end()) {
    372                 hi = *it;
    373             }
    374             res += query(lo, hi - 1);
    375             res %= MOD;
    376             res -= query(lo, u - 1);
    377             res += MOD;
    378             res %= MOD;
    379             res -= query(u, hi - 1);
    380             res += MOD;
    381             res %= MOD;
    382             ss.erase(u);
    383         }
    384         cout << res << "\n";
    385     }
    386     return 0;
    387 }
    388 ```
    389 
    390 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen")
    391 
    392 Tutorial is loading...
    393 
    394 **C++ Solution**
    395 
    396 ```
    397 #include <bits/stdc++.h>
    398 using namespace std;
    399 
    400 const int MOD = 119 << 23 | 1;
    401 
    402 int inv(int a) {
    403     int r = 1, t = a, k = MOD - 2;
    404     while (k) {
    405         if (k & 1) r = (long long) r * t % MOD;
    406         t = (long long) t * t % MOD;
    407         k >>= 1;
    408     }
    409     return r;
    410 }
    411 
    412 int main() {
    413     string s; cin >> s;
    414     int k = s.size() + 1;
    415     int a = 0, b = 0, c = 0, d = 0;
    416     for (char e : s) {
    417         if (e == ')') {
    418             b++;
    419         }
    420         if (e == '?') {
    421             d++;
    422         }
    423     }
    424     map<int, vector<int>> dps;
    425     auto calc = [&] (int a, int b, int c, int d) {
    426         int x = b + d - a;
    427         if (x < 0) return 0;
    428         int k = c + d;
    429         if (k < x) x = k;
    430         if (dps.count(k)) return dps[k][x];
    431         auto& dp = dps[k];
    432         dp.resize(k + 1);
    433         int t = 0, w = 1;
    434         for (int i = 0; i <= k; i++) {
    435             t += w;
    436             t %= MOD;
    437             dp[i] = t;
    438             w = (long long) w * (c + d - i) % MOD;
    439             w = (long long) w * inv(i + 1) % MOD;
    440         }
    441         return dp[x];
    442     };
    443     int res = 0;
    444     for (int i = 0; i < (int) s.size(); i++) {
    445         char e = s[i];
    446         if (e == '(') {
    447             a++;
    448         }
    449         if (e == ')') {
    450             b--;
    451         }
    452         if (e == '?') {
    453             c++;
    454             d--;
    455         }
    456         if (e == '(') {
    457             res += calc(a, b, c, d);
    458             res %= MOD;
    459         }
    460         else if (e == '?') {
    461             a++, c--;
    462             res += calc(a, b, c, d);
    463             res %= MOD;
    464             a--, c++;
    465         }
    466     }
    467     cout << res << "\n";
    468     return 0;
    469 }
    470 ```
    471 
    472 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen")
    473 
    474 Tutorial is loading...
    475 
    476 **C++ Solution**
    477 
    478 ```
    479 #include <bits/stdc++.h>
    480 using namespace std;
    481 
    482 int main() {
    483     int n, m; cin >> n >> m;
    484     vector<int> d(n);
    485     vector<vector<int>> g(n, vector<int>(n));
    486     vector<vector<int>> f(n, vector<int>(n, 1));
    487     for (int i = 0; i < m; i++) {
    488         int u, v; cin >> u >> v; u--, v--;
    489         d[u]++;
    490         g[u][v] = 1, g[v][u] = 2;
    491         f[u][v] = f[v][u] = 0;
    492     }
    493     priority_queue<pair<int, int>> heap;
    494     for (int i = 0; i < n; i++) {
    495         if (d[i] < n - 1) {
    496             heap.push({-d[i], i});
    497         }
    498     }
    499     while (!heap.empty()) {
    500         int u = heap.top().second;
    501         heap.pop();
    502         queue<int> que;
    503         vector<int> vis(n), from(n);
    504         que.push(u), vis[u] = 1;
    505         int id = -1;
    506         while (!que.empty()) {
    507             int v = que.front(); que.pop();
    508             int found = 0;
    509             for (int w = 0; w < n; w++) if (w != v && !g[v][w]) {
    510                 found = 1;
    511                 break;
    512             }
    513             if (found) {
    514                 id = v;
    515                 break;
    516             }
    517             for (int w = 0; w < n; w++) if (!vis[w] && g[v][w] == 2 && f[v][w] == 1) {
    518                 que.push(w), vis[w] = 1;
    519                 from[w] = v;
    520             }
    521         }
    522         if (id == -1) {
    523             continue;
    524         }
    525         for (int v = 0; v < n; v++) if (v != id && !g[id][v]) {
    526             g[id][v] = 1, g[v][id] = 2;
    527             break;
    528         }
    529         while (id != u) {
    530             int nid = from[id];
    531             swap(g[id][nid], g[nid][id]);
    532             id = nid;
    533         }
    534         d[u]++;
    535         if (d[u] < n - 1) {
    536             heap.push({-d[u], u});
    537         }
    538     }
    539     for (int i = 0; i < n; i++) {
    540         for (int j = 0; j < n; j++) {
    541             if (i == j) {
    542                 cout << 0;
    543             }
    544             else {
    545                 cout << 2 - g[i][j];
    546             }
    547         }
    548         cout << "\n";
    549     }
    550     return 0;
    551 }
    552 ```
    553 
    554 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen")
    555 
    556 Another cool problem: [WEICOM](https://www.codechef.com/LTIME53/problems/WEICOM).
    557 
    558 Tutorial is loading...
    559 
    560 **Python Solution**
    561 
    562 ```
    563 n,a,d=map(int,input().split())
    564 print(368131125*a%10**9*12*10**9+1,368131125*d%10**9*12*10**9)
    565 ```
    566 
    567 Author: [chemthan](/profile/chemthan "International Grandmaster chemthan"), prepare [laoriu](/profile/laoriu "Master laoriu"), [I_love_Hoang_Yen](/profile/I_love_Hoang_Yen "International Master I_love_Hoang_Yen")
    568 
    569 Bonus: [another beautiful problem](https://www.hackerearth.com/problem/algorithm/lucky-sequence-1-77a76688/).