codeforces-scrape

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

2125.md (8746B)


      1 Source: https://codeforces.com/blog/entry/144998
      2 
      3 [2125A - Difficult Contest](/contest/2125/problem/A "Educational Codeforces Round 181 (Rated for Div. 2)")
      4 
      5 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 using namespace std;
     16  
     17 int main(){
     18     int tc;
     19     cin >> tc;
     20     while (tc--){
     21         string s;
     22         cin >> s;
     23         sort(s.begin(), s.end());
     24         reverse(s.begin(), s.end());
     25         cout << s << '\n';
     26     }
     27 }
     28 ```
     29 
     30 [2125B - Left and Down](/contest/2125/problem/B "Educational Codeforces Round 181 (Rated for Div. 2)")
     31 
     32 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     33 
     34 **Tutorial**
     35 
     36 Tutorial is loading...
     37 
     38 **Solution (ifive)**
     39 
     40 ```
     41 from math import gcd
     42 for _ in range(int(input())):
     43     a, b, k = map(int, input().split())
     44     g = gcd(a, b)
     45     print(1 if a // g <= k and b // g <= k else 2)
     46 ```
     47 
     48 [2125C - Count Good Numbers](/contest/2125/problem/C "Educational Codeforces Round 181 (Rated for Div. 2)")
     49 
     50 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     51 
     52 **Tutorial**
     53 
     54 Tutorial is loading...
     55 
     56 **Solution 1 (BledDest)**
     57 
     58 ```
     59 def good(x):
     60     return x % 2 > 0 and x % 3 > 0 and x % 5 > 0 and x % 7 > 0
     61  
     62 def get_naive(x):
     63     ans = 0
     64     for i in range(x):
     65         if good(i):
     66             ans += 1
     67     return ans
     68  
     69 def get(r):
     70     return (r // 210) * get_naive(210) + get_naive(r % 210)
     71  
     72 t = int(input())
     73 for i in range(t):
     74     l, r = map(int, input().split())
     75     print(get(r+1) - get(l))
     76 ```
     77 
     78 **Solution 2 (awoo)**
     79 
     80 ```
     81 for _ in range(int(input())):
     82     l, r = map(int, input().split())
     83  
     84     def f(x):
     85         res = 0
     86         ps = [2, 3, 5, 7]
     87         for mask in range(16):
     88             m = 1
     89             sg = 1
     90             for i in range(4):
     91                 if (mask >> i) & 1:
     92                     m *= ps[i]
     93                     sg = -sg
     94             res += sg * (x // m)
     95         return res
     96     
     97     print(f(r) - f(l - 1))
     98 ```
     99 
    100 [2125D - Segments Covering](/contest/2125/problem/D "Educational Codeforces Round 181 (Rated for Div. 2)")
    101 
    102 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    103 
    104 **Tutorial**
    105 
    106 Tutorial is loading...
    107 
    108 **Solution 1 (Neon)**
    109 
    110 ```
    111 #include <bits/stdc++.h>
    112  
    113 using namespace std;
    114  
    115 using pt = pair<int, int>;
    116  
    117 const int MOD = 998244353;
    118  
    119 int add(int x, int y) {
    120    x += y;
    121    if (x >= MOD) x -= MOD;
    122    if (x < 0) x += MOD;
    123    return x;
    124 }
    125  
    126 int mul(int x, int y) {
    127   return x * 1LL * y % MOD;
    128 }
    129  
    130 int binpow(int x, int y) {
    131   int z = 1;
    132   while (y) {
    133     if (y & 1) z = mul(z, x);
    134     x = mul(x, x);
    135     y >>= 1;
    136   }
    137   return z;
    138 }
    139  
    140 int divide(int x, int y) {
    141   return mul(x, binpow(y, MOD - 2));
    142 }
    143  
    144 int main() {
    145   ios::sync_with_stdio(false); cin.tie(0);
    146   int n, m;
    147   cin >> n >> m;
    148   vector<vector<pt>> a(m + 1);
    149   for (int i = 0; i < n; ++i) {
    150     int l, r, p, q;
    151     cin >> l >> r >> p >> q;
    152     a[r].emplace_back(l - 1, divide(p, q));
    153   }
    154   vector<int> pr(m + 1);
    155   pr[0] = 1;
    156   for (int i = 1; i <= m; ++i) {
    157     int cur = 1;
    158     for (auto [_, p] : a[i]) cur = mul(cur, add(1, -p));
    159     pr[i] = mul(pr[i - 1], cur);
    160   }
    161   vector<int> dp(m + 1);
    162   dp[0] = 1;
    163   for (int i = 1; i <= m; ++i) {
    164     for (auto [l, p] : a[i]) { 
    165       int cur = divide(pr[i], pr[l]);
    166       cur = divide(cur, add(1, -p));
    167       cur = mul(cur, p);
    168       dp[i] = add(dp[i], mul(dp[l], cur));
    169     }
    170   }
    171   cout << dp[m] << endl;  
    172 }
    173 ```
    174 
    175 **Solution 2 (Neon)**
    176 
    177 ```
    178 #include <bits/stdc++.h>
    179  
    180 using namespace std;
    181  
    182 using pt = pair<int, int>;
    183  
    184 const int MOD = 998244353;
    185  
    186 int add(int x, int y) {
    187      x += y;
    188      if (x >= MOD) x -= MOD;
    189      if (x < 0) x += MOD;
    190      return x;
    191 }
    192  
    193 int mul(int x, int y) {
    194     return x * 1LL * y % MOD;
    195 }
    196  
    197 int binpow(int x, int y) {
    198     int z = 1;
    199     while (y) {
    200         if (y & 1) z = mul(z, x);
    201         x = mul(x, x);
    202         y >>= 1;
    203     }
    204     return z;
    205 }
    206  
    207 int divide(int x, int y) {
    208     return mul(x, binpow(y, MOD - 2));
    209 }
    210  
    211 int main() {
    212     ios::sync_with_stdio(false); cin.tie(0);
    213     int n, m;
    214     cin >> n >> m;
    215     vector<vector<pt>> a(m + 1);
    216     vector<int> dp(m + 1);
    217     dp[0] = 1;
    218     for (int i = 0; i < n; ++i) {
    219         int l, r, p, q;
    220         cin >> l >> r >> p >> q;
    221         int val = divide(p, q);
    222         a[r].emplace_back(l - 1, val);
    223         dp[0] = mul(dp[0], add(1, -val));
    224     }
    225     for (int i = 1; i <= m; ++i) {
    226         for (auto [l, p] : a[i]) { 
    227             int cur = dp[l];
    228             cur = divide(cur, add(1, -p));
    229             cur = mul(cur, p);
    230             dp[i] = add(dp[i], cur);
    231         }
    232     }
    233     cout << dp[m] << endl;  
    234 }
    235 ```
    236 
    237 [2125E - Sets of Complementary Sums](/contest/2125/problem/E "Educational Codeforces Round 181 (Rated for Div. 2)")
    238 
    239 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    240 
    241 **Tutorial**
    242 
    243 Tutorial is loading...
    244 
    245 **Solution (FelixArg)**
    246 
    247 ```
    248 #include<bits/stdc++.h>
    249 using namespace std;
    250  
    251 #define int long long
    252  
    253 const int MOD = 998'244'353;
    254  
    255 void solve(){
    256     int n, x;
    257     cin >> n >> x;
    258     // need sum(mx + 1 - ai) <= mx + 1
    259     // start with 1, 2, 3, ... n
    260     // min sum + 1 is n + 1
    261  
    262     if (n == 1){
    263         cout << x << '\n';
    264         return;
    265     }
    266  
    267     int s_cur = n * (n + 1) / 2;
    268     int need = s_cur - (n + 1);
    269  
    270     // leads to n is O(sqrt(s))
    271     if (n + need > x){
    272         cout << 0 << '\n';
    273         return;
    274     }
    275  
    276     // so we can do dp[sum] knapsack
    277  
    278     vector<int> dp(x + 1);
    279     dp[0] = 1;
    280  
    281     // for -1 and 0
    282     for (int j = 0; j < 2; j++){
    283         for (int i = 0; i < x; i++){
    284             dp[i + 1] = (dp[i + 1] + dp[i]) % MOD;
    285         }
    286     }
    287  
    288     for (int i = 1; i <= n - 2; i++){
    289         for (int j = 0; j < x; j++){
    290             // increase sum by i -> mx increase by 1 + i
    291             if (j + i + 1 <= x){
    292                 dp[j + i + 1] = (dp[j + i + 1] + dp[j]) % MOD;
    293             }
    294         }
    295     }
    296  
    297     int ans = 0;
    298     for (int i = 0; i <= x; i++){
    299         int cur = n + need + i;
    300         if (cur > x){
    301             break;
    302         }
    303         ans = (ans + dp[i]) % MOD;
    304     }
    305  
    306     cout << ans << '\n';
    307 }
    308  
    309 signed main()
    310 {
    311 #ifdef FELIX
    312     auto _clock_start = chrono::high_resolution_clock::now();
    313 #endif
    314     ios_base::sync_with_stdio(false);
    315     cin.tie(0);
    316     cout.tie(0);
    317  
    318     int t = 1;
    319     cin >> t;
    320     while(t--){
    321         solve();
    322     }
    323  
    324 #ifdef FELIX
    325     cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    326         chrono::high_resolution_clock::now()
    327             - _clock_start).count() << "ms." << endl;
    328 #endif
    329     return 0;
    330 }
    331 ```
    332 
    333 [2125F - Timofey and Docker](/contest/2125/problem/F "Educational Codeforces Round 181 (Rated for Div. 2)")
    334 
    335 Idea: [FelixArg](/profile/FelixArg "Master FelixArg")
    336 
    337 **Tutorial**
    338 
    339 Tutorial is loading...
    340 
    341 **Solution (awoo)**
    342 
    343 ```
    344 #include <bits/stdc++.h>
    345  
    346 using namespace std;
    347  
    348 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    349  
    350 const int INF = 1e8;
    351 const string al = "docker";
    352  
    353 int main(){
    354     cin.tie(0);
    355     ios::sync_with_stdio(false);
    356     int tc;
    357     cin >> tc;
    358     while (tc--){
    359         string s;
    360         cin >> s;
    361         int n = s.size();
    362         int mx = n / 6;
    363         int m;
    364         cin >> m;
    365         vector<int> dx(mx + 2);
    366         forn(i, m){
    367             int l, r;
    368             cin >> l >> r;
    369             r = min(r, mx);
    370             if (l > r) continue;
    371             ++dx[l];
    372             --dx[r + 1];
    373         }
    374         forn(i, mx + 1) dx[i + 1] += dx[i];
    375  
    376         int cur = 0;
    377         vector<int> dif(max(0, n - 5));
    378         forn(i, n - 5){
    379             forn(j, 6)
    380                 dif[i] += s[i + j] != al[j];
    381             cur += dif[i] == 0;
    382         }
    383  
    384         int mxcnt = *max_element(dx.begin(), dx.end());
    385         int k = -1;
    386         int ans = INF;
    387         forn(i, mx + 1){
    388             if (dx[i] != mxcnt) continue;
    389             if (i <= cur){
    390                 ans = min(ans, cur - i);
    391                 continue;
    392             }
    393             k = i;
    394             break;
    395         }
    396  
    397         if (k == -1){
    398             cout << ans << '\n';
    399             continue;
    400         }
    401  
    402         auto calc = [&](int d){
    403             vector<pair<long long, int>> dp(n + 1, {(long long)1e18, -1});
    404             dp[0] = {0, 0};
    405             forn(i, n){
    406                 dp[i + 1] = min(dp[i + 1], dp[i]);
    407                 if (i + 6 <= n)
    408                     dp[i + 6] = min(dp[i + 6], {dp[i].first + dif[i] + d, dp[i].second - 1});
    409             }
    410             return dp[n];
    411         };
    412  
    413         int l = -INF, r = 0, sv = INF;
    414         while (l <= r){
    415             int m = (l + r) / 2;
    416             auto [val, cnt] = calc(m);
    417             if (-cnt >= k){
    418                 sv = val - k * 1ll * m;
    419                 l = m + 1;
    420             }
    421             else{
    422                 r = m - 1;
    423             }
    424         }
    425         ans = min(ans, sv);
    426  
    427         cout << ans << '\n';
    428     } 
    429 }
    430 ```