codeforces-scrape

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

2145.md (10470B)


      1 Source: https://codeforces.com/blog/entry/147164
      2 
      3 [2145A - Candies for Nephews](/contest/2145/problem/A "Educational Codeforces Round 183 (Rated for Div. 2)")
      4 
      5 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (fcspartakm)**
     12 
     13 ```
     14 #include <iostream>
     15  
     16 using namespace std;
     17  
     18 int main() {
     19     int t;
     20     cin >> t;
     21     for(int i = 0; i < t; i++)
     22     {
     23         int n;
     24         cin >> n;
     25         cout << (3 - n % 3) % 3 << endl;
     26     }
     27 }
     28 ```
     29 
     30 [2145B - Deck of Cards](/contest/2145/problem/B "Educational Codeforces Round 183 (Rated for Div. 2)")
     31 
     32 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     33 
     34 **Tutorial**
     35 
     36 Tutorial is loading...
     37 
     38 **Solution (Neon)**
     39 
     40 ```
     41 #include <bits/stdc++.h>
     42  
     43 using namespace std;
     44  
     45 int main() {
     46   int t;
     47   cin >> t;
     48   while (t--) {
     49     int n, k;
     50     string s;
     51     cin >> n >> k >> s;
     52     int a = count(s.begin(), s.end(), '0');
     53     int b = count(s.begin(), s.end(), '1');
     54     int c = count(s.begin(), s.end(), '2');
     55     string ans(n, '+');
     56     for (int i = 0; i < n; ++i) {
     57       if (i < a + c || i >= n - b - c) ans[i] = '?';
     58       if (i < a || i >= n - b || k == n) ans[i] = '-';
     59     }
     60     cout << ans << '\n';
     61   }
     62 }
     63 ```
     64 
     65 [2145C - Monocarp's String](/contest/2145/problem/C "Educational Codeforces Round 183 (Rated for Div. 2)")
     66 
     67 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     68 
     69 **Tutorial**
     70 
     71 Tutorial is loading...
     72 
     73 **Solution (BledDest)**
     74 
     75 ```
     76 #include <bits/stdc++.h>
     77  
     78 using namespace std;
     79  
     80 #define forn(i, n) for(int i = 0; i < int(n); i++) 
     81  
     82 void solve() {                    
     83     int n;
     84     string s;
     85     cin >> n >> s;
     86     int cur = count(s.begin(), s.end(), 'a') - count(s.begin(), s.end(), 'b');
     87     map<int, int> lst;
     88     int pr = 0;
     89     lst[pr] = -1;
     90     int ans = n;
     91     forn(i, n){
     92         pr += s[i] == 'a' ? 1 : -1;
     93         lst[pr] = i;
     94         if (lst.count(pr - cur))
     95             ans = min(ans, i - lst[pr - cur]);
     96     }
     97     cout << (ans == n ? -1 : ans) << '\n';
     98 }
     99  
    100 int main() {
    101     ios_base::sync_with_stdio(0);
    102     cin.tie(0);
    103     int t;
    104     cin >> t;
    105     forn(i, t) solve();
    106 }
    107 ```
    108 
    109 [2145D - Inversion Value of a Permutation](/contest/2145/problem/D "Educational Codeforces Round 183 (Rated for Div. 2)")
    110 
    111 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    112 
    113 **Tutorial**
    114 
    115 Tutorial is loading...
    116 
    117 **Solution (BledDest)**
    118 
    119 ```
    120 t = int(input())
    121 for i in range(t):
    122     n, k = map(int, input().split())
    123     maxk = n * (n - 1) // 2
    124     dp = [[False for i in range(maxk + 1)] for j in range(n + 1)]
    125     p = [[-1 for i in range(maxk + 1)] for j in range(n + 1)]
    126     dp[0][0] = True
    127     for j in range(n):
    128         for x in range(maxk + 1):
    129             for y in range(1, n - j + 1):
    130                 if not dp[j][x]:
    131                     continue
    132                 add = y * (y - 1) // 2
    133                 dp[j + y][x + add] = True
    134                 p[j + y][x + add] = y
    135     k = maxk - k
    136     if dp[n][k]:
    137         ans = []
    138         cur = n
    139         curk = k
    140         while cur != 0:
    141             y = p[cur][curk]
    142             ans.append(y)
    143             curk -= y * (y - 1) // 2
    144             cur -= y
    145         res = []
    146         cur = n + 1
    147         for y in ans:
    148             for x in range(cur - y, cur):
    149                 res.append(x)
    150             cur -= y
    151         print(*res)
    152     else:
    153         print(0)
    154 ```
    155 
    156 [2145E - Predicting Popularity](/contest/2145/problem/E "Educational Codeforces Round 183 (Rated for Div. 2)")
    157 
    158 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    159 
    160 **Tutorial**
    161 
    162 Tutorial is loading...
    163 
    164 **Solution (adedalic)**
    165 
    166 ```
    167 #include<bits/stdc++.h>
    168  
    169 using namespace std;
    170  
    171 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    172 #define sz(a) int((a).size())
    173  
    174 #define x first
    175 #define y second
    176  
    177 typedef long long li;
    178 typedef long double ld;
    179 typedef pair<int, int> pt;
    180  
    181 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    182     return out << "(" << p.x << ", " << p.y << ")";
    183 }
    184 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    185     fore(i, 0, sz(v)) {
    186         if(i) out << " ";
    187         out << v[i];
    188     }
    189     return out;
    190 }
    191  
    192 const int INF = int(1e9);
    193 const li INF64 = li(1e18);
    194 const ld EPS = 1e-9;
    195  
    196 int ac, dr;
    197 int n;
    198 vector<int> a, d;
    199  
    200 inline bool read() {
    201     if(!(cin >> ac >> dr))
    202         return false;
    203     cin >> n;
    204     a.resize(n);
    205     fore (i, 0, n)
    206         cin >> a[i];
    207     d.resize(n);
    208     fore (i, 0, n)
    209         cin >> d[i];
    210     return true;
    211 }
    212  
    213 vector<int> Tadd, Tmin;
    214  
    215 void push(int v) {
    216     Tadd[2 * v + 1] += Tadd[v];
    217     Tadd[2 * v + 2] += Tadd[v];
    218     Tadd[v] = 0;
    219 }
    220  
    221 int getmin(int v) {
    222     return Tmin[v] + Tadd[v];
    223 }
    224  
    225 void upd(int v) {
    226     Tmin[v] = min(getmin(2 * v + 1), getmin(2 * v + 2));
    227 }
    228  
    229 void init(int v, int l, int r) {
    230     if (l + 1 == r) {
    231         Tmin[v] = -l;
    232         return;
    233     }
    234     int mid = (l + r) >> 1;
    235     init(2 * v + 1, l, mid);
    236     init(2 * v + 2, mid, r);
    237     upd(v);
    238 }
    239  
    240 void init(int n) {
    241     Tadd.assign(4 * n, 0);
    242     Tmin.resize(4 * n);
    243     init(0, 0, n);
    244 }
    245  
    246 void addVal(int v, int l, int r, int lf, int rg, int val) {
    247     if (l == lf && r == rg) {
    248         Tadd[v] += val;
    249         return;
    250     }
    251     int mid = (l + r) >> 1;
    252     push(v);
    253     if (lf < mid)
    254         addVal(2 * v + 1, l, mid, lf, min(mid, rg), val);
    255     if (rg > mid)
    256         addVal(2 * v + 2, mid, r, max(lf, mid), rg, val);
    257     upd(v);
    258 }
    259  
    260 int firstNeg(int v, int l, int r) {
    261     if (l + 1 == r) {
    262         assert(getmin(v) < 0);
    263         return l;
    264     }
    265     push(v);
    266     int mid = (l + r) >> 1;
    267     int ans = -1;
    268     if (getmin(2 * v + 1) < 0)
    269         ans = firstNeg(2 * v + 1, l, mid);
    270     else
    271         ans = firstNeg(2 * v + 2, mid, r);
    272     upd(v);
    273     return ans;
    274 }
    275  
    276 int calcDemand(int i) {
    277     return min(n, max(a[i] - ac, 0) + max(d[i] - dr, 0));
    278 }
    279  
    280 inline void solve() {
    281     init(n + 2);
    282     fore (i, 0, n) {
    283         int p = calcDemand(i);
    284         addVal(0, 0, n + 2, p + 1, n + 2, 1);
    285     }
    286  
    287     int m; cin >> m;
    288     fore (j, 0, m) {
    289         int k, na, nd;
    290         cin >> k >> na >> nd;
    291         k--;
    292         int p = calcDemand(k);
    293         addVal(0, 0, n + 2, p + 1, n + 2, -1);
    294         a[k] = na;
    295         d[k] = nd;
    296         p = calcDemand(k);
    297         addVal(0, 0, n + 2, p + 1, n + 2, 1);
    298  
    299         int ans = firstNeg(0, 0, n + 2);
    300         cout << ans - 1 << '\n';
    301     }
    302 }
    303  
    304 int main() {
    305 #ifdef _DEBUG
    306     freopen("input.txt", "r", stdin);
    307     int tt = clock();
    308 #endif
    309     ios_base::sync_with_stdio(false);
    310     cin.tie(0), cout.tie(0);
    311     cout << fixed << setprecision(15);
    312     
    313     if(read()) {
    314         solve();
    315         
    316 #ifdef _DEBUG
    317         cerr << "TIME = " << clock() - tt << endl;
    318         tt = clock();
    319 #endif
    320     }
    321     return 0;
    322 }
    323 ```
    324 
    325 [2145F - Long Journey](/contest/2145/problem/F "Educational Codeforces Round 183 (Rated for Div. 2)")
    326 
    327 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    328 
    329 **Tutorial**
    330 
    331 Tutorial is loading...
    332 
    333 **Solution (Neon)**
    334 
    335 ```
    336 #include <bits/stdc++.h>
    337  
    338 using namespace std;
    339  
    340 using li = long long;
    341  
    342 const int N = 10;
    343 const int LOG = 50;
    344 const int LCM = 2520;
    345  
    346 int n;
    347 li m;
    348 int a[N], b[N];
    349 li go[LOG][N][LCM];
    350  
    351 void solve() {
    352   cin >> n >> m;
    353   for (int i = 0; i < n; ++i) cin >> a[i];
    354   for (int i = 0; i < n; ++i) cin >> b[i];
    355   for (int x = 0; x < n; ++x) {
    356     for (int y = 0; y < LCM; ++y) {
    357       go[0][x][y] = ((y + 1) % a[x]) != b[x];
    358     }
    359   }
    360   for (int i = 1; i < LOG; ++i) {
    361     for (int x = 0; x < n; ++x) {
    362       for (int y = 0; y < LCM; ++y) {
    363         go[i][x][y] = go[i - 1][x][y] + go[i - 1][(x + (1LL << (i - 1))) % n][(y + go[i - 1][x][y]) % LCM];  
    364       }
    365     }
    366   }
    367   if (go[LOG - 1][0][0] < m) {
    368     cout << -1 << endl;
    369     return;
    370   }
    371   li s = 0, ans = 0;
    372   for (int i = LOG - 1; i >= 0; --i) {
    373     if (s + go[i][ans % n][s % LCM] < m) {
    374       s += go[i][ans % n][s % LCM];
    375       ans += 1LL << i;
    376     }
    377   }
    378   cout << ans + 1 << endl;
    379 }
    380  
    381 int main() {
    382   int t;
    383   cin >> t;
    384   while (t--) solve();
    385 }
    386 ```
    387 
    388 [2145G - Cost of Coloring](/contest/2145/problem/G "Educational Codeforces Round 183 (Rated for Div. 2)")
    389 
    390 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    391 
    392 **Tutorial**
    393 
    394 Tutorial is loading...
    395 
    396 **Solution (BledDest)**
    397 
    398 ```
    399 #include<bits/stdc++.h>
    400  
    401 using namespace std;
    402  
    403 int n, m, k;
    404  
    405 const int N = 4043;
    406 const int MOD = 998244353;
    407  
    408 int add(int x, int y)
    409 {
    410     x += y;
    411     while(x >= MOD) x -= MOD;
    412     while(x < 0) x += MOD;
    413     return x;
    414 }   
    415  
    416 int sub(int x, int y)
    417 {
    418     return add(x, -y);
    419 }
    420  
    421 int mul(int x, int y)
    422 {
    423     return (x * 1ll * y) % MOD;
    424 }
    425  
    426 int binpow(int x, int y)
    427 {
    428     int z = 1;
    429     while(y > 0)
    430     {
    431         if(y % 2 == 1) z = mul(z, x);
    432         x = mul(x, x);
    433         y /= 2;
    434     }
    435     return z;
    436 }
    437  
    438 int fact[N];
    439 int rfact[N];
    440  
    441 void precalc_factorials()
    442 {
    443     fact[0] = 1;
    444     for(int i = 1; i < N; i++)
    445         fact[i] = mul(fact[i - 1], i);
    446     for(int i = 0; i < N; i++)
    447         rfact[i] = binpow(fact[i], MOD - 2);
    448 }
    449  
    450 int choose(int x, int y)
    451 {
    452     if(x < 0 || y < 0 || x < y) return 0;
    453     return mul(fact[x], mul(rfact[y], rfact[x - y]));
    454 }
    455  
    456 vector<int> prefix_sum(const vector<int>& a)
    457 {
    458     int n = a.size();
    459     vector<int> p(n + 1);
    460     for(int i = 0; i < n; i++) p[i + 1] = add(a[i], p[i]);
    461     return p;
    462 }
    463  
    464 int get(const vector<int>& a, int i)
    465 {
    466     if(a.size() > i) return a[i];
    467     else return a.back();
    468 }   
    469  
    470 int main()
    471 {
    472     ios_base::sync_with_stdio(0);
    473     cin.tie(0);
    474     int n, m, k;
    475     cin >> n >> m >> k;
    476     precalc_factorials();
    477  
    478     vector<vector<int>> A(k, vector<int>(n + m));
    479     for(int x = 0; x < k; x++)
    480     {
    481         vector<int> by_rows(n + 1);
    482         for(int i = 1; i <= n; i++)
    483             by_rows[i] = mul(choose(n, i), binpow(x, n - i));
    484         vector<int> pr = prefix_sum(by_rows);
    485  
    486         vector<int> by_cols(m + 1);
    487         for(int i = 1; i <= m; i++)
    488             by_cols[i] = mul(choose(m, i), binpow(x, m - i));
    489         vector<int> pc = prefix_sum(by_cols);
    490  
    491         for(int i = 1; i <= max(n, m); i++)
    492         {
    493             A[x][n + m - i] = sub(mul(get(pr, i + 1), get(pc, i + 1)), mul(get(pr, i), get(pc, i)));
    494         }     
    495     }
    496  
    497     for(int i = min(n, m); i < n + m; i++)
    498     {
    499         int ans = 0;
    500         for(int j = 0; j < k; j++)
    501         {
    502             int cur = mul(choose(k - 1, j), A[k - 1 - j][i]);
    503             if(j % 2 == 0)
    504                 ans = add(ans, cur);
    505             else
    506                 ans = add(ans, -cur);
    507         }
    508         cout << ans << " ";
    509     }
    510     cout << endl;
    511 }
    512 ```