codeforces-scrape

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

2182.md (10120B)


      1 Source: https://codeforces.com/blog/entry/149733
      2 
      3 [2182A - New Year String](/contest/2182/problem/A "Educational Codeforces Round 186 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n = int(input())
     17     s = input()
     18     if '2025' in s and not '2026' in s:
     19         print(1)
     20     else:
     21         print(0)
     22 ```
     23 
     24 [2182B - New Year Cake](/contest/2182/problem/B "Educational Codeforces Round 186 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (BledDest)**
     33 
     34 ```
     35 t = int(input())
     36 for i in range(t):
     37     a, b = map(int, input().split())
     38     if a < b:
     39         a, b = b, a
     40     x, y = 0, 0
     41     ans = 0
     42     cur = 1
     43     while True:
     44         x, y = y + cur, x
     45         if x <= a and y <= b:
     46             ans += 1
     47             cur *= 2
     48         else:
     49             break
     50     print(ans)
     51 ```
     52 
     53 [2182C - Production of Snowmen](/contest/2182/problem/C "Educational Codeforces Round 186 (Rated for Div. 2)")
     54 
     55 Idea: [Roms](/profile/Roms "Master Roms")
     56 
     57 **Tutorial**
     58 
     59 Tutorial is loading...
     60 
     61 **Solution (BledDest)**
     62 
     63 ```
     64 def good(x, y, n, k):
     65     ans = True
     66     for i in range(n):
     67         if x[i] <= y[(i + k) % n]:
     68             ans = False
     69     return ans     
     70  
     71 t = int(input())
     72 for _ in range(t):
     73     n = int(input())
     74     a = list(map(int, input().split()))
     75     b = list(map(int, input().split()))
     76     c = list(map(int, input().split()))
     77     k1, k2 = 0, 0
     78     for i in range(n):
     79         if good(b, a, n, i):
     80             k1 += 1
     81         if good(c, b, n, i):
     82             k2 += 1
     83     print(k1 * k2 * n)
     84 ```
     85 
     86 [2182D - Christmas Tree Decoration](/contest/2182/problem/D "Educational Codeforces Round 186 (Rated for Div. 2)")
     87 
     88 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     89 
     90 **Tutorial**
     91 
     92 Tutorial is loading...
     93 
     94 **Solution (Neon)**
     95 
     96 ```
     97 #include <bits/stdc++.h>
     98  
     99 using namespace std;
    100  
    101 const int N = 55;
    102 const int MOD = 998244353;
    103  
    104 int mul(int x, int y) {
    105   return x * 1LL * y % MOD;
    106 }
    107  
    108 int binpow(int x, int y) {
    109   int z = 1;
    110   while (y > 0) {
    111     if (y & 1) z = mul(z, x);
    112     x = mul(x, x);
    113     y >>= 1;
    114   }
    115   return z;
    116 }
    117  
    118 int main() {
    119   vector<int> f(N, 1);
    120   for (int i = 1; i < N; ++i)
    121     f[i] = (f[i - 1] * 1LL * i) % MOD;
    122  
    123   int t;
    124   cin >> t;
    125   while (t--) {
    126     int n;
    127     cin >> n;
    128     vector<int> a(n + 1);
    129     for (int &x : a) cin >> x;
    130     int k = accumulate(a.begin(), a.end(), 0) / n;
    131     int z = 0, bad = 0;
    132     for (int i = 1; i <= n; ++i) {
    133       int x = min(a[i], k);
    134       a[i] -= x;
    135       a[0] -= k - x;
    136       z += a[i] == 0;
    137       bad |= a[i] > 1 || a[0] < 0;
    138     }
    139     bad |= a[0] > z;
    140     int ans = bad ? 0 : f[z];
    141     if (!bad) {
    142       ans = mul(ans, f[n - z + a[0]]);
    143       ans = mul(ans, binpow(f[a[0]], MOD - 2));
    144     }
    145     cout << ans << '\n';
    146   }
    147 }
    148 ```
    149 
    150 [2182E - New Year's Gifts](/contest/2182/problem/E "Educational Codeforces Round 186 (Rated for Div. 2)")
    151 
    152 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    153 
    154 **Tutorial**
    155 
    156 Tutorial is loading...
    157 
    158 **Solution (Neon)**
    159 
    160 ```
    161 #include <bits/stdc++.h>
    162  
    163 using namespace std;
    164  
    165 void solve() {
    166   int n, m;
    167   long long k;
    168   cin >> n >> m >> k;
    169   vector<vector<int>> ev(m);
    170   for (int i = 0; i < m; ++i) {
    171     int x; cin >> x;
    172     ev[x - 1].push_back(-1);
    173   }
    174   for (int i = 0; i < n; ++i) {
    175     int x, y, z;
    176     cin >> x >> y >> z;
    177     ev[x - 1].push_back(z - y);
    178     k -= y;
    179   }
    180   int ans = 0;
    181   multiset<int> s;
    182   for (int i = 0; i < m; ++i) {
    183     reverse(ev[i].begin(), ev[i].end());
    184     for (int x : ev[i]) {
    185       if (x == -1) {
    186         if (!s.empty()) {
    187           s.erase(--s.end());
    188           ++ans;
    189         }
    190       } else {
    191         s.insert(x);
    192       }
    193     }
    194   }
    195   while (!s.empty() && *s.begin() <= k) {
    196     k -= *s.begin();
    197     s.erase(s.begin());
    198     ++ans;
    199   }
    200   cout << ans << '\n';
    201 }
    202  
    203 int main() {
    204   ios::sync_with_stdio(false); cin.tie(0);
    205   int t;
    206   cin >> t;
    207   while (t--) solve();
    208 }
    209 ```
    210 
    211 [2182F1 - Christmas Reindeer (easy version)](/contest/2182/problem/F1 "Educational Codeforces Round 186 (Rated for Div. 2)")
    212 
    213 [2182F2 - Christmas Reindeer (hard version)](/contest/2182/problem/F2 "Educational Codeforces Round 186 (Rated for Div. 2)")
    214 
    215 Idea: [Roms](/profile/Roms "Master Roms")
    216 
    217 **Tutorial**
    218 
    219 Tutorial is loading...
    220 
    221 **Solution (BledDest)**
    222 
    223 ```
    224 #include<bits/stdc++.h>
    225  
    226 using namespace std;
    227  
    228 const int MOD = 998244353;
    229 const int LOGN = 61;
    230  
    231 int add(int x, int y)
    232 {
    233     x += y;
    234     if(x >= MOD) x -= MOD;
    235     if(x < 0) x += MOD;
    236     return x;
    237 }
    238  
    239 int sub(int x, int y)
    240 {
    241     return add(x, -y);
    242 }
    243  
    244 int mul(int x, int y)
    245 {
    246     return (x * 1ll * y) % MOD;
    247 }   
    248  
    249 int binpow(int x, int y)
    250 {
    251     int z = 1;
    252     while(y > 0)
    253     {
    254         if(y % 2 == 1) z = mul(z, x);
    255         x = mul(x, x);
    256         y /= 2;
    257     }
    258     return z;
    259 }                   
    260  
    261 vector<int> get_required(long long x)
    262 {
    263     vector<int> ans(LOGN);
    264     int cnt = 0;
    265     for(int i = LOGN - 1; i >= 0; i--)
    266     {
    267         if((x >> i) & 1)
    268         {
    269             ans[i + cnt]++;
    270             cnt++;
    271         }
    272     }
    273     return ans;
    274 }
    275  
    276 void solve()
    277 {
    278     int n, m;
    279     cin >> n >> m;        
    280     vector<int> freq(LOGN);
    281     for(int i = 0; i < n; i++)
    282     {
    283         int x;
    284         cin >> x;
    285         freq[x]++;
    286     }
    287     
    288     int max_n = n + m + 111;
    289  
    290     vector<int> fact(max_n, 1);
    291     for(int i = 1; i < max_n; i++)
    292         fact[i] = mul(fact[i - 1], i);
    293     vector<int> inv_fact(max_n);
    294     for(int i = 0; i < max_n; i++)
    295         inv_fact[i] = binpow(fact[i], MOD - 2);
    296     vector<int> pow2(max_n, 1);
    297     for(int i = 1; i < max_n; i++)
    298         pow2[i] = mul(pow2[i - 1], 2);
    299  
    300     auto choose = [&](int x, int y)
    301     {           
    302         if(x < y || x < 0 || y < 0) return 0;
    303         return mul(fact[x], mul(inv_fact[y], inv_fact[x - y]));
    304     };
    305  
    306     auto sum_greater = [&](int x, int y)
    307     {
    308         if(y >= x) return 0;
    309         int ans = pow2[x];
    310         for(int i = 0; i <= y; i++)
    311             ans = sub(ans, choose(x, i));
    312         return ans;
    313     };
    314  
    315     for(int i = 0; i < m; i++)
    316     {
    317         int t;
    318         long long x;
    319         cin >> t >> x;
    320         if(t == 1)
    321             freq[x]++;
    322         else if(t == 2)
    323             freq[x]--;
    324         else
    325         {
    326             auto req = get_required(x);
    327             int ans = 0;
    328             int cur = 1;
    329             int cnt_less = 0;
    330             for(int i = 0; i < LOGN; i++) cnt_less += freq[i];
    331             for(int i = LOGN - 1; i >= 0; i--)
    332             {
    333                 cnt_less -= freq[i];
    334                 ans = add(ans, mul(cur, mul(sum_greater(freq[i], req[i]), pow2[cnt_less])));
    335                 cur = mul(cur, choose(freq[i], req[i]));
    336             }
    337             ans = add(ans, cur);
    338             cout << ans << "\n";
    339         }
    340     }
    341 }
    342  
    343 int main()
    344 {
    345     ios_base::sync_with_stdio(0);
    346     cin.tie(0);    
    347     int t = 1;
    348     //cin >> t;
    349     for(int i = 0; i < t; i++) solve();
    350 }
    351 ```
    352 
    353 [2182G - Short Garland](/contest/2182/problem/G "Educational Codeforces Round 186 (Rated for Div. 2)")
    354 
    355 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    356 
    357 **Tutorial**
    358 
    359 Tutorial is loading...
    360 
    361 **Solution (awoo)**
    362 
    363 ```
    364 #include <bits/stdc++.h>
    365  
    366 #define forn(i, n) for (int i = 0; i < int(n); i++)
    367  
    368 using namespace std;
    369  
    370 const int MOD = 998244353;
    371  
    372 int add(int a, int b){
    373     a += b;
    374     if (a >= MOD) a -= MOD;
    375     if (a < 0) a += MOD;
    376     return a;
    377 }
    378  
    379 int mul(int a, int b){
    380     return a * 1ll * b % MOD;
    381 }
    382  
    383 int binpow(int a, int b){
    384     int res = 1;
    385     while (b){
    386         if (b & 1)
    387             res = mul(res, a);
    388         a = mul(a, a);
    389         b >>= 1;
    390     }
    391     return res;
    392 }
    393  
    394 int n, k;
    395 vector<vector<int>> g;
    396  
    397 struct dpar{
    398     vector<int> dp;
    399     int ml, ad;
    400     dpar(){
    401         ml = 1, ad = 0;
    402         dp.clear();
    403     }
    404     int& operator [](int k){
    405         return dp[max(0, int(dp.size()) - k - 1)];
    406     }
    407     int get(int k){
    408         int x = dp[max(0, int(dp.size()) - k - 1)];
    409         return add(mul(x, ml), ad);
    410     }
    411 };
    412  
    413 vector<dpar> dp;
    414 vector<int> fact;
    415  
    416 void dfs(int v){
    417     int bst = -1;
    418     vector<int> val;
    419     for (int u : g[v]){
    420         dfs(u);
    421         dp[u].dp.push_back(add(0, mul(binpow(dp[u].ml, MOD - 2), -dp[u].ad)));
    422         if (bst == -1 || dp[u].dp.size() > dp[bst].dp.size())
    423             bst = u;
    424         val.push_back(dp[u].get(k - 1));
    425     }
    426     if (val.empty()){
    427         dp[v].dp.push_back(1);
    428         return;
    429     }
    430  
    431     vector<int> pr(val.size() + 1, 1), su(val.size() + 1, 1);
    432     forn(i, val.size()){
    433         pr[i + 1] = mul(pr[i], val[i]);
    434         su[val.size() - i - 1] = mul(su[val.size() - i], val[val.size() - i - 1]);
    435     }
    436  
    437     swap(dp[v], dp[bst]);
    438     {
    439         int i = find(g[v].begin(), g[v].end(), bst) - g[v].begin();
    440         int cur = mul(fact[g[v].size() - 1], mul(pr[i], su[i + 1]));
    441         if (cur == 0){
    442             int mx = 1;
    443             for (int u : g[v]) mx = max(mx, int(dp[u].dp.size()));
    444             dp[v].dp.assign(mx, 0);
    445             dp[v].ml = 1, dp[v].ad = 0;
    446         }
    447         else{
    448             dp[v].ml = mul(dp[v].ml, cur);
    449             dp[v].ad = mul(dp[v].ad, cur);
    450         }
    451     }
    452  
    453     int rev = binpow(dp[v].ml, MOD - 2);
    454     forn(i, g[v].size()){
    455         int u = g[v][i];
    456         if (u == bst) continue;
    457         int cur = mul(fact[g[v].size() - 1], mul(pr[i], su[i + 1]));
    458         int tot = mul(cur, dp[u].get(n));
    459         dp[v].ad = add(dp[v].ad, tot);
    460         forn(j, dp[u].dp.size()){
    461             dp[v][j] = add(dp[v][j], -mul(rev, tot));
    462             dp[v][j] = add(dp[v][j], mul(mul(cur, dp[u].get(j)), rev));
    463         }
    464     }
    465 }
    466  
    467 int main() {
    468     cin.tie(0);
    469     ios::sync_with_stdio(false);
    470     int t;
    471     cin >> t;
    472     while (t--){
    473         cin >> n >> k;
    474         g.assign(n, {});
    475         for (int i = 1; i < n; ++i){
    476             int p;
    477             cin >> p;
    478             --p;
    479             g[p].push_back(i);
    480         }
    481         dp.assign(n, {});
    482         fact.resize(n + 1, 1);
    483         for (int i = 1; i <= n; ++i)
    484             fact[i] = mul(fact[i - 1], i);
    485         dfs(0);
    486         cout << dp[0].get(n) << '\n';
    487     }
    488     return 0;
    489 }
    490 ```