codeforces-scrape

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

2260.md (10355B)


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