codeforces-scrape

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

1626.md (5904B)


      1 Source: https://codeforces.com/blog/entry/99136
      2 
      3 [1626A - Equidistant Letters](/contest/1626/problem/A "Educational Codeforces Round 121 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15   print(''.join(sorted(input())))
     16 ```
     17 
     18 [1626B - Minor Reduction](/contest/1626/problem/B "Educational Codeforces Round 121 (Rated for Div. 2)")
     19 
     20 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     21 
     22 **Tutorial**
     23 
     24 Tutorial is loading...
     25 
     26 **Solution (awoo)**
     27 
     28 ```
     29 for _ in range(int(input())):
     30   x = [ord(c) - ord('0') for c in input()]
     31   n = len(x)
     32   for i in range(n - 2, -1, -1):
     33     if x[i] + x[i + 1] >= 10:
     34       x[i + 1] += x[i] - 10
     35       x[i] = 1
     36       break
     37   else:
     38     x[1] += x[0]
     39     x.pop(0)
     40   print(''.join([chr(c + ord('0')) for c in x]))
     41 ```
     42 
     43 [1626C - Monsters And Spells](/contest/1626/problem/C "Educational Codeforces Round 121 (Rated for Div. 2)")
     44 
     45 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution (awoo)**
     52 
     53 ```
     54 for _ in range(int(input())):
     55   n = int(input())
     56   k = list(map(int, input().split()))
     57   h = list(map(int, input().split()))
     58   st = []
     59   for i in range(n):
     60     st.append([k[i] - h[i], k[i]])
     61   st.sort()
     62   l, r = -1, -1
     63   ans = 0
     64   for it in st:
     65     if it[0] >= r:
     66       ans += (r - l) * (r - l + 1) // 2
     67       l, r = it
     68     else:
     69       r = max(r, it[1])
     70   ans += (r - l) * (r - l + 1) // 2
     71   print(ans)
     72 ```
     73 
     74 [1626D - Martial Arts Tournament](/contest/1626/problem/D "Educational Codeforces Round 121 (Rated for Div. 2)")
     75 
     76 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     77 
     78 **Tutorial**
     79 
     80 Tutorial is loading...
     81 
     82 **Solution (awoo)**
     83 
     84 ```
     85 calc = 1
     86 nxt = [1, 0]
     87 
     88 for _ in range(int(input())):
     89   n = int(input())
     90   a = sorted(list(map(int, input().split())))
     91   while calc <= n:
     92     for i in range(calc):
     93       nxt.append(calc - i - 1)
     94     calc *= 2
     95   left = []
     96   for i in range(n + 1):
     97     if i == 0 or i == n or a[i] != a[i - 1]:
     98       left.append(i)
     99     else:
    100       left.append(left[-1])
    101   mid = 1
    102   ans = n + 2
    103   while mid <= n:
    104     for len1 in range(n + 1):
    105       if left[len1] == len1:
    106         len2 = left[min(n, len1 + mid)] - len1
    107         len3 = n - len1 - len2
    108         ans = min(ans, nxt[len1] + (mid - len2) + nxt[len3])
    109     mid *= 2
    110   print(ans)
    111 ```
    112 
    113 [1626E - Black and White Tree](/contest/1626/problem/E "Educational Codeforces Round 121 (Rated for Div. 2)")
    114 
    115 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    116 
    117 **Tutorial**
    118 
    119 Tutorial is loading...
    120 
    121 **Solution (BledDest)**
    122 
    123 ```
    124 #include<bits/stdc++.h>
    125 
    126 using namespace std;
    127 
    128 const int N = 300043;
    129 
    130 vector<int> g[N];
    131 int cnt[N];
    132 int c[N];
    133 vector<int> g2[N];
    134 int par[N];
    135 int used[N];
    136 
    137 void dfs(int x, int p = -1)
    138 {
    139     par[x] = p;
    140     for(auto y : g[x])
    141         if(y != p)
    142         {
    143             dfs(y, x);
    144             cnt[x] += cnt[y];
    145         }
    146     cnt[x] += c[x];
    147 }   
    148 
    149 int main()
    150 {
    151     int n;
    152     scanf("%d", &n);
    153     for(int i = 0; i < n; i++) scanf("%d", &c[i]);
    154     for(int i = 1; i < n; i++)
    155     {
    156         int x, y;
    157         scanf("%d %d", &x, &y);
    158         --x;
    159         --y;
    160         g[x].push_back(y);
    161         g[y].push_back(x);
    162     }
    163     dfs(0);
    164     for(int i = 0; i < n; i++)
    165         for(auto j : g[i])
    166         {
    167             if(i == par[j])
    168             {
    169                 if(c[i] == 1 || cnt[0] - cnt[j] > 1)
    170                     g2[i].push_back(j);
    171             }
    172             else
    173             {
    174                 if(c[i] == 1 || cnt[i] > 1)
    175                     g2[i].push_back(j);
    176             }
    177         }
    178     queue<int> q;
    179     for(int i = 0; i < n; i++)
    180     {
    181         if(c[i] == 1)
    182         {
    183             q.push(i);
    184             used[i] = 1;
    185         }
    186     }
    187     while(!q.empty())
    188     {
    189         int k = q.front();
    190         q.pop();
    191         for(auto y : g2[k])
    192             if(used[y] == 0)
    193             {
    194                 used[y] = 1;
    195                 q.push(y);
    196             }
    197     }
    198     for(int i = 0; i < n; i++)
    199         printf("%d ", used[i]);
    200     puts("");
    201 }
    202 ```
    203 
    204 [1626F - A Random Code Problem](/contest/1626/problem/F "Educational Codeforces Round 121 (Rated for Div. 2)")
    205 
    206 Idea: [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 MOD = 998244353;
    220 const int L = 720720;
    221 
    222 int add(int x, int y, int m = MOD)
    223 {
    224     x += y;
    225     if(x >= m) x -= m;
    226     return x;
    227 }
    228 
    229 int mul(int x, int y, int m = MOD)
    230 {
    231     return (x * 1ll * y) % m;
    232 }
    233 
    234 int binpow(int x, int y)
    235 {
    236     int z = 1;
    237     while(y > 0)
    238     {
    239         if(y % 2 == 1) z = mul(z, x);
    240         x = mul(x, x);
    241         y /= 2;
    242     }
    243     return z;
    244 }
    245 
    246 int inv(int x)
    247 {
    248     return binpow(x, MOD - 2);
    249 }
    250 
    251 int divide(int x, int y)
    252 {
    253     return mul(x, inv(y));
    254 }
    255 
    256 int main()
    257 {
    258     int n, a0, x, y, k, M;
    259     cin >> n >> a0 >> x >> y >> k >> M;
    260     vector<int> arr(n);
    261     arr[0] = a0;
    262     for(int i = 1; i < n; i++)
    263         arr[i] = add(mul(arr[i - 1], x, M), y, M);
    264     int ans = 0;
    265     int total_ways = binpow(n, k);
    266     int coeff = mul(divide(total_ways, n), k);
    267     vector<vector<int>> dp(k, vector<int>(L));
    268     for(int i = 0; i < n; i++)
    269     {
    270         int p = arr[i] / L;
    271         int q = arr[i] % L;
    272         dp[0][q]++;
    273         ans = add(ans, mul(p, mul(L, coeff)));
    274     }
    275     int cur_coeff = divide(total_ways, n);
    276     for(int i = 1; i <= k; i++)
    277     {
    278         for(int j = 0; j < L; j++)
    279         {
    280             int cur = dp[i - 1][j];
    281             if(i < k)
    282                 dp[i][j] = add(dp[i][j], mul(n - 1, cur));
    283             ans = add(ans, mul(j, mul(cur, cur_coeff)));
    284             if(i < k)
    285                 dp[i][j - (j % i)] = add(dp[i][j - (j % i)], cur);
    286         }
    287         cur_coeff = divide(cur_coeff, n);
    288     }
    289     cout << ans << endl;        
    290 }
    291 ```