codeforces-scrape

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

2276.md (10597B)


      1 Source: https://codeforces.com/blog/entry/157752
      2 
      3 [2276A - Perfect Sandwiches](/contest/2276/problem/A "Educational Codeforces Round 195 (Rated for Div. 2)")
      4 
      5 Author: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for _ in range(t):
     16     a, b = map(int, input().split())
     17     if b >= a:
     18         print(-1)
     19     else:
     20         print(min(b, a - b))
     21 ```
     22 
     23 [2276B - Replace and Compress](/contest/2276/problem/B "Educational Codeforces Round 195 (Rated for Div. 2)")
     24 
     25 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     26 
     27 **Tutorial**
     28 
     29 Tutorial is loading...
     30 
     31 **Solution (BledDest)**
     32 
     33 ```
     34 t = int(input())
     35 for _ in range(t):
     36     s = input()
     37     ans = 1
     38     if "010" in s or "101" in s:
     39         ans += 1
     40     if "000" in s or "111" in s:
     41         ans += 1
     42     print(ans)
     43 ```
     44 
     45 [2276C - Subarrays](/contest/2276/problem/C "Educational Codeforces Round 195 (Rated for Div. 2)")
     46 
     47 Author: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     48 
     49 **Tutorial**
     50 
     51 Tutorial is loading...
     52 
     53 **Solution (BledDest)**
     54 
     55 ```
     56 t = int(input())
     57 for _ in range(t):
     58     n, k = map(int, input().split())
     59     a = list(map(int, input().split()))
     60     
     61     p = [0 for i in range(n+1)]
     62     for i in range(n):
     63         p[i+1] = (p[i]+a[i]) % k
     64 
     65     ans = 0
     66     cnt = [0 for i in range(k)]
     67     for i in range(k+1, n+1):
     68         cnt[p[i-k-1]] += 1
     69         ans += cnt[p[i]]
     70 
     71     print(ans)
     72 ```
     73 
     74 [2276D - Caveman](/contest/2276/problem/D "Educational Codeforces Round 195 (Rated for Div. 2)")
     75 
     76 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution (BledDest)**
     83 
     84 ```
     85 #include<bits/stdc++.h>
     86 
     87 using namespace std;
     88 
     89 void solve()
     90 {
     91     int n, m;
     92     cin >> n >> m;
     93     vector<int> d(n);
     94     for(int i = 0; i < m; i++)
     95     {
     96         int x, y;
     97         cin >> x >> y;
     98         x--;
     99         y--;
    100         d[x]++;
    101         d[y]++;
    102     }
    103     sort(d.begin(), d.end());
    104     if(d[0] == 0)
    105         cout << "Brain Melt\n";
    106     else if(d[n - 1] == n - 1 && d[n - 2] == 1)
    107         cout << 2 << "\n";
    108     else
    109         cout << "Many\n";
    110 }
    111 
    112 int main()
    113 {
    114     ios_base::sync_with_stdio(0);
    115     cin.tie(0);
    116     int t;
    117     cin >> t;
    118     for(int i = 0; i < t; i++)
    119         solve();
    120 }
    121 ```
    122 
    123 [2276E - Good Substrings](/contest/2276/problem/E "Educational Codeforces Round 195 (Rated for Div. 2)")
    124 
    125 Author: [Roms](/profile/Roms "Master Roms")
    126 
    127 **Tutorial**
    128 
    129 Tutorial is loading...
    130 
    131 **Solution (Roms)**
    132 
    133 ```
    134 #include <bits/stdc++.h>
    135 
    136 using namespace std;
    137 
    138 int t;
    139 
    140 int main() {
    141     const string s25 = "2025", s26 = "2026";
    142     
    143     cin >> t;
    144     for (int tc = 0; tc < t; ++tc) {
    145         int n;
    146         string s;
    147         cin >> n >> s;
    148         
    149         vector <vector <int>> nxt(n, vector <int> (10));
    150         vector <int> cur(10, n);
    151         
    152         for (int i = n - 1; i >= 0; --i) {
    153             cur[s[i] - '0'] = i;
    154             for (int j = 0; j < 10; ++j)
    155                 nxt[i][j] = cur[j];
    156         }
    157         
    158         vector <int> d(n + 1);
    159         vector <int> dd(n + 1);
    160         
    161         for (int l = 0; l < n; ++l) {
    162             int r25 = l, r26 = l;
    163             int i25 = 0, i26 = 0;
    164             
    165             while(i25 < s25.size() && r25 < n) {
    166                 int x = s25[i25++] - '0';
    167                 r25 = nxt[r25][x];
    168             }
    169             
    170             while(i26 < s26.size() && r26 < n) {
    171                 int x = s26[i26++] - '0';
    172                 r26 = nxt[r26][x];
    173             }
    174             
    175             int cnt = n - l;
    176             d[l] += cnt;
    177             --dd[l + 1];
    178             
    179             if (r25 < r26) {
    180                 // bad == [r25..r26-1]
    181                 cnt = r26 - r25;
    182                 d[l] -= cnt;
    183                 ++dd[r25 + 1];
    184                 //--dd[r26];
    185                 if(r26 < n)
    186                     --dd[r26 + 1];
    187             }
    188         }
    189         
    190         vector <int> ans(n);
    191         long long sum = 0, add = 0;
    192         for (int i = 0; i < n; ++i) {
    193             sum += d[i];
    194             add += dd[i];
    195             sum += add;
    196             cout << sum << ' ';
    197         }
    198         cout << endl;
    199     }
    200     return 0;
    201 }
    202 ```
    203 
    204 [2276F - Permutation Coloring Game](/contest/2276/problem/F "Educational Codeforces Round 195 (Rated for Div. 2)")
    205 
    206 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    207 
    208 **Tutorial**
    209 
    210 Tutorial is loading...
    211 
    212 **Solution (BledDest)**
    213 
    214 ```
    215 #include<bits/stdc++.h>
    216 
    217 using namespace std;
    218 
    219 const int INF = 1e9;
    220 
    221 void upd(int& x, int y)
    222 {
    223     if(x > y) x = y;
    224 }
    225 
    226 void solve()
    227 {
    228     int n, k;
    229     cin >> n >> k;
    230     vector<int> p(n);
    231     for(int i = 0; i < n; i++)
    232     {
    233         cin >> p[i];
    234         p[i]--;
    235     }
    236 
    237     vector<bool> used(n);
    238     vector<int> len;
    239     for(int i = 0; i < n; i++)
    240     {
    241         if(!used[i])
    242         {
    243             used[i] = true;
    244             int cur_len = 1;
    245             int j = p[i];
    246             while(!used[j])
    247             {
    248                 used[j] = true;
    249                 cur_len++;
    250                 j = p[j];
    251             }
    252             len.push_back(cur_len);
    253         }
    254     }
    255     sort(len.begin(), len.end());
    256     reverse(len.begin(), len.end());
    257 
    258     if(k == 1)
    259     {
    260         if(len[0] >= 3)
    261             cout << "Bob\n";
    262         else if(len[0] == 1 || n % 2 == 1)
    263             cout << "Alice\n";
    264         else 
    265             cout << "Bob\n";        
    266     }
    267     else if(len[0] > k + 1)
    268     {
    269         cout << "Bob\n";
    270     }
    271     else if(len[0] == k + 1)
    272     {
    273         if(len.size() > 1 && len[1] == k + 1)
    274         {
    275             cout << "Bob\n";
    276         }
    277         else
    278         {
    279             int must_remove = 0;
    280             int cnt1 = 0;
    281             for(int i = 1; i < len.size(); i++)
    282             {
    283                 if(len[i] > 1)
    284                     must_remove += len[i];
    285                 else cnt1++;
    286             }
    287             int alice_move = must_remove + cnt1 % (k + 1);
    288             if(alice_move > k || alice_move == 0)
    289                 cout << "Bob\n";
    290             else
    291                 cout << "Alice\n";
    292         }
    293     }
    294     else
    295     {                        
    296         int m = len.size();
    297         m = min(m, 2 * k);
    298         vector<vector<vector<int>>> dp(m+1, vector<vector<int>>(k+1, vector<int>(k + 1, INF)));
    299         dp[0][0][0] = 0;
    300         for(int i = 0; i < m; i++)
    301             for(int j = 0; j <= k; j++)
    302                 for(int c = 0; c <= k; c++)
    303                 {
    304                     if(dp[i][j][c] == INF) continue;
    305                     bool alice_can = (j + len[i] <= k);
    306                     bool bob_can = (i - c < k);
    307                     if(alice_can)
    308                         upd(dp[i+1][j + len[i]][c + 1], dp[i][j][c]);
    309                     upd(dp[i+1][j][c], dp[i][j][c] + (bob_can ? len[i] - 1 : 0));
    310                 }
    311         bool alice_win = false;
    312         for(int j = 0; j <= k; j++)
    313             for(int c = 0; c <= k; c++)
    314                 if(dp[m][j][c] <= k)
    315                     alice_win = true;
    316 
    317         if(alice_win)
    318             cout << "Alice\n";
    319         else
    320             cout << "Bob\n";
    321     }
    322 }
    323 
    324 int main()
    325 {
    326     ios_base::sync_with_stdio(0);
    327     cin.tie(0);
    328     int t;
    329     cin >> t;
    330     for(int i = 0; i < t; i++)
    331         solve();
    332 }
    333 ```
    334 
    335 [2276G - Elimination of Players](/contest/2276/problem/G "Educational Codeforces Round 195 (Rated for Div. 2)")
    336 
    337 Author: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    338 
    339 **Tutorial**
    340 
    341 Tutorial is loading...
    342 
    343 **Solution (BledDest)**
    344 
    345 ```
    346 #include<bits/stdc++.h>
    347 
    348 using namespace std;
    349 
    350 const int MOD = 998244353;
    351 const int N = 5005;
    352 
    353 int add(int x, int y)
    354 {
    355     x += y;
    356     while(x >= MOD) x -= MOD;
    357     while(x < 0) x += MOD;
    358     return x;
    359 }
    360 
    361 int mul(int x, int y)
    362 {
    363     return (x * 1ll * y) % MOD;
    364 }
    365 
    366 int sub(int x, int y)
    367 {
    368     return add(x, -y);
    369 }
    370 
    371 int binpow(int x, int y)
    372 {
    373     int z = 1;
    374     while(y)
    375     {
    376         if(y & 1) z = mul(z, x);
    377         x = mul(x, x);
    378         y >>= 1;
    379     }
    380     return z;
    381 }
    382 
    383 int fact[N];
    384 int inv[N];
    385 
    386 void precalc()
    387 {
    388     fact[0] = 1;
    389     for(int i = 1; i < N; i++)
    390         fact[i] = mul(i, fact[i - 1]);    
    391     for(int i = 0; i < N; i++)
    392         inv[i] = binpow(i, MOD - 2);
    393 }
    394 
    395 struct Blocks
    396 {
    397     int n;
    398     vector<int> cutoff_pos;
    399     vector<int> pref;
    400     vector<int> pref_G;
    401     vector<pair<int, int>> a;
    402 
    403     void rebuild()
    404     {
    405         pref = { 0 };
    406         pref_G = { 0 };
    407         vector<bool> used(n);
    408         vector<pair<int, int>> b;
    409         cutoff_pos = vector<int>(n, -1);
    410         int sign = 1;
    411         int cnt = n - 1;
    412         for(int i = 0; i < a.size(); i++)
    413         {
    414             int x = a[i].first;
    415             int len = a[i].second;
    416             if(used[x])
    417                 break;
    418             used[x] = true;
    419             b.push_back(make_pair(x, len));
    420             cutoff_pos[x] = i;
    421             int c = mul(sign, mul(len, fact[cnt]));
    422             int c_G = mul(sign, mul(len, fact[cnt - 1]));
    423             --cnt;
    424             sign = sub(0, sign);
    425             pref.push_back(add(pref.back(), c));
    426             pref_G.push_back(add(pref_G.back(), c_G));
    427         }
    428 
    429         a = b;
    430     }
    431 
    432     int getF()
    433     {
    434         return pref.back();
    435     }
    436 
    437     int getG(int x)
    438     {
    439         if(cutoff_pos[x] == -1) return pref_G.back();
    440         else return pref_G[cutoff_pos[x]];
    441     }
    442 
    443     void append(int x)
    444     {
    445         if(a.empty() || a[0].first != x)
    446             a.insert(a.begin(), make_pair(x, 0));
    447         a[0].second++;
    448         rebuild();
    449     }
    450 
    451     Blocks(int n = 0) : n(n) {};
    452 };
    453 
    454 void solve()
    455 {
    456     int n;
    457     cin >> n;
    458     vector<int> a(n - 1);
    459     for(int i = 0; i < n - 1; i++)
    460     {
    461         cin >> a[i];
    462         a[i]--;
    463     }
    464     Blocks b(n);
    465     vector<vector<int>> ans(n - 1, vector<int>(n));
    466     vector<vector<int>> G(n - 1, vector<int>(n));
    467     vector<int> F(n - 1);
    468     for(int i = 0; i < n - 1; i++)
    469     {
    470         int x = a[i];
    471         b.append(x);
    472         F[i] = b.getF();
    473         for(int j = 0; j < n; j++)
    474             G[i][j] = b.getG(j);
    475         for(int j = 0; j < n; j++)
    476         {
    477             if(a[i] == j) continue;
    478             int s = add(fact[n - 1], G[i][j]);
    479             if(i > 0)
    480             {
    481                 s = sub(s, G[i - 1][j]);
    482                 if(a[i - 1] == j)
    483                     s = add(s, F[i - 1]);
    484             }
    485             ans[i][j] = s;   
    486         }
    487     }
    488     
    489     long long res = 0;
    490     for(int i = 0; i < n - 1; i++)
    491         for(int j = 0; j < n; j++)
    492             res ^= ans[i][j] * 1ll * (i + 1) * 1ll * (j + 1);
    493     cout << res << endl;
    494 }
    495 
    496 int main() 
    497 {
    498     precalc();
    499     ios_base::sync_with_stdio(0);
    500     cin.tie(0);
    501     int t;
    502     cin >> t;
    503     for(int i = 0; i < t; i++)
    504         solve();   
    505 }
    506 ```