codeforces-scrape

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

1954.md (8499B)


      1 Source: https://codeforces.com/blog/entry/128421
      2 
      3 [1954A - Painting the Ribbon](/contest/1954/problem/A "Educational Codeforces Round 164 (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, m, k = map(int, input().split())
     17     max_color = (n + m - 1) / m
     18     if max_color + k >= n:
     19         print('NO')
     20     else:
     21         print('YES')
     22 ```
     23 
     24 [1954B - Make It Ugly](/contest/1954/problem/B "Educational Codeforces Round 164 (Rated for Div. 2)")
     25 
     26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     27 
     28 **Tutorial**
     29 
     30 Tutorial is loading...
     31 
     32 **Solution (awoo)**
     33 
     34 ```
     35 for _ in range(int(input())):
     36     n = int(input())
     37     a = list(map(int, input().split()))
     38     lst = -1
     39     ans = n
     40     for i in range(n):
     41         if a[i] != a[0]:
     42             ans = min(ans, i - lst - 1)
     43             lst = i
     44     ans = min(ans, n - lst - 1)
     45     if ans == n:
     46         print(-1)
     47     else:
     48         print(ans)
     49 ```
     50 
     51 [1954C - Long Multiplication](/contest/1954/problem/C "Educational Codeforces Round 164 (Rated for Div. 2)")
     52 
     53 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     54 
     55 **Tutorial**
     56 
     57 Tutorial is loading...
     58 
     59 **Solution (Neon)**
     60 
     61 ```
     62 #include <bits/stdc++.h>
     63  
     64 using namespace std;
     65  
     66 int main() {
     67   int t;
     68   cin >> t;
     69   while (t--) {
     70     string x, y;
     71     cin >> x >> y;
     72     int n = x.size();
     73     bool f = false;
     74     for (int i = 0; i < n; ++i) {
     75       if ((x[i] > y[i]) == f) swap(x[i], y[i]);
     76       f |= (x[i] != y[i]);
     77     }
     78     cout << x << '\n' << y << '\n';
     79   }
     80 }
     81 ```
     82 
     83 [1954D - Colored Balls](/contest/1954/problem/D "Educational Codeforces Round 164 (Rated for Div. 2)")
     84 
     85 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     86 
     87 **Tutorial**
     88 
     89 Tutorial is loading...
     90 
     91 **Solution (Neon)**
     92 
     93 ```
     94 #include <bits/stdc++.h>
     95  
     96 using namespace std;
     97  
     98 const int MOD = 998244353;
     99  
    100 int add(int x, int y) {
    101   x += y;
    102   if (x >= MOD) x -= MOD;
    103   return x;
    104 } 
    105  
    106 int mul(int x, int y) {
    107   return x * 1LL * y % MOD;
    108 }
    109  
    110 int main() {
    111   int n;
    112   cin >> n;
    113   vector<int> a(n);
    114   for (int i = 0; i < n; ++i) cin >> a[i];
    115   int s = accumulate(a.begin(), a.end(), 0);
    116   vector<int> dp(s + 1);
    117   dp[0] = 1;
    118   for (int i = 0; i < n; ++i)
    119     for (int j = s - a[i]; j >= 0; --j) 
    120       dp[j + a[i]] = add(dp[j + a[i]], dp[j]);
    121   int ans = 0;
    122   for (int j = 0; j <= s; ++j) 
    123     ans = add(ans, mul((j + 1) / 2, dp[j]));
    124   for (int i = 0; i < n; ++i)
    125     for (int j = 0; j < a[i]; ++j) 
    126       ans = add(ans, mul(a[i] - (a[i] + j + 1) / 2, dp[j]));
    127   cout << ans << '\n';
    128 }
    129 ```
    130 
    131 [1954E - Chain Reaction](/contest/1954/problem/E "Educational Codeforces Round 164 (Rated for Div. 2)")
    132 
    133 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    134 
    135 **Tutorial**
    136 
    137 Tutorial is loading...
    138 
    139 **Solution 1 (awoo)**
    140 
    141 ```
    142 #include <bits/stdc++.h>
    143  
    144 #define forn(i, n) for (int i = 0; i < int(n); i++)
    145  
    146 using namespace std;
    147  
    148 int divup(int a, int b){
    149     return (a + b - 1) / b;
    150 }
    151  
    152 int main() {
    153     cin.tie(0);
    154     ios::sync_with_stdio(false);
    155     int n;
    156     cin >> n;
    157     vector<int> a(n);
    158     forn(i, n) cin >> a[i];
    159     int mx = *max_element(a.begin(), a.end());
    160     vector<long long> ans(mx + 1);
    161     forn(i, n){
    162         int coef = 0;
    163         if (i == 0 || a[i] > a[i - 1]) ++coef;
    164         if (i + 1 < n && a[i] < a[i + 1]) --coef;
    165         int r = a[i];
    166         ans[r] += coef;
    167         while (r > 0){
    168             int val = divup(a[i], r);
    169             int l = divup(a[i], val);
    170             ans[l - 1] += coef * val;
    171             ans[r] -= coef * val;
    172             r = l - 1;
    173         }
    174     }
    175     forn(i, mx) ans[i + 1] += ans[i];
    176     forn(i, mx) cout << ans[i] << ' ';
    177     cout << '\n';
    178     return 0;
    179 }
    180 ```
    181 
    182 **Solution 2 (awoo)**
    183 
    184 ```
    185 #include <bits/stdc++.h>
    186  
    187 #define forn(i, n) for (int i = 0; i < int(n); i++)
    188  
    189 using namespace std;
    190  
    191 int main() {
    192     cin.tie(0);
    193     ios::sync_with_stdio(false);
    194     int n;
    195     cin >> n;
    196     vector<int> a(n);
    197     forn(i, n) cin >> a[i];
    198     int mx = *max_element(a.begin(), a.end());
    199     vector<long long> pr(mx + 1);
    200     forn(i, n){
    201         int coef = 0;
    202         if (i == 0 || a[i] > a[i - 1]) ++coef;
    203         if (i + 1 < n && a[i] < a[i + 1]) --coef;
    204         pr[a[i]] += coef;
    205     }
    206     forn(i, mx) pr[i + 1] += pr[i];
    207     for (int k = 1; k <= mx; ++k){
    208         long long ans = 0;
    209         for (int l = 1, val = 1; l <= mx; l += k, ++val)
    210             ans += val * 1ll * (pr[min(mx, l + k - 1)] - pr[l - 1]);
    211         cout << ans << ' ';
    212     }
    213     cout << '\n';
    214     return 0;
    215 }
    216 ```
    217 
    218 [1954F - Unique Strings](/contest/1954/problem/F "Educational Codeforces Round 164 (Rated for Div. 2)")
    219 
    220 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    221 
    222 **Tutorial**
    223 
    224 Tutorial is loading...
    225 
    226 **Solution (adedalic)**
    227 
    228 ```
    229 #include<bits/stdc++.h>
    230  
    231 using namespace std;
    232  
    233 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    234 #define sz(a) int((a).size())
    235  
    236 typedef long long li;
    237 typedef pair<int, int> pt;
    238  
    239 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    240     return out << "(" << p.x << ", " << p.y << ")";
    241 }
    242 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    243     fore(i, 0, sz(v)) {
    244         if(i) out << " ";
    245         out << v[i];
    246     }
    247     return out;
    248 }
    249  
    250 const int MOD = int(1e9) + 7;
    251 int add(int a, int b) {
    252     a += b;
    253     while (a >= MOD)
    254         a -= MOD;
    255     while (a < 0)
    256         a += MOD;
    257     return a;
    258 }
    259 void upd(int &ans, int val) {
    260     ans = add(ans, val);
    261 }
    262 int mul(int a, int b) {
    263     return int(a * 1ll * b % MOD);
    264 }
    265 int binPow(int a, int k) {
    266     int ans = 1;
    267     while (k > 0) {
    268         if (k & 1)
    269             ans = mul(ans, a);
    270         a = mul(a, a);
    271         k >>= 1;
    272     }
    273     return ans;
    274 }
    275  
    276 const int N = 3055;
    277 int f[N], invf[N];
    278  
    279 void precalcFact() {
    280     f[0] = invf[0] = 1;
    281     fore (i, 1, N) {
    282         f[i] = mul(f[i - 1], i);
    283         invf[i] = binPow(f[i], MOD - 2);
    284     }
    285 }
    286 int C(int n, int k) {
    287     if (k < 0 || k > n)
    288         return 0;
    289     return mul(f[n], mul(invf[k], invf[n - k]));
    290 }
    291  
    292 int n, c, k;
    293  
    294 inline bool read() {
    295     if(!(cin >> n >> c >> k))
    296         return false;
    297     return true;
    298 }
    299  
    300 int d[N][N], sum[N][N];
    301  
    302 // d[z][l] - number of strings of length l, with z zeroes and blocks of 1-s shorter than mx
    303 void precalcShort(int mx) {
    304     memset(d, 0, sizeof d);
    305     d[0][0] = 1;
    306     fore (z, 0, n) {
    307         fore (l, 0, n) {
    308             if (d[z][l] == 0)
    309                 continue;
    310             upd(d[z + 1][l + 1], +d[z][l]);
    311             upd(d[z + 1][min(n, l + mx) + 1], -d[z][l]);
    312         }
    313         fore (l, 0, n + 1)
    314             upd(d[z + 1][l + 1], d[z + 1][l]);
    315     }
    316         
    317     memset(sum, 0, sizeof sum);
    318     fore (z, 0, n + 1) fore (l, 0, n + 1)
    319         sum[z][l + 1] = add(sum[z][l], d[z][l]);
    320     
    321 }
    322  
    323 //[lf, rg)
    324 int getSum(int z, int lf, int rg) {
    325     if (z < 0 || z > n || lf >= rg)
    326         return 0;
    327     return add(sum[z][rg], -sum[z][lf]);
    328 }
    329  
    330 // cnt[g] is a number of x <= n with gcd(x, n) = g
    331 vector<int> precalcCnt(int n) {
    332     vector<int> cnt(n + 1, 0);
    333     fore (x, 1, n + 1)
    334         cnt[gcd(x, n)]++;
    335     return cnt;
    336 }
    337  
    338 int calcFixedPoints(int g) {
    339     if (c >= g)
    340         return c + k >= n;
    341     
    342     int cntOnes = (c + k) / (n / g);
    343     int cntZeros = g - cntOnes;
    344     
    345     int all = 0;
    346     fore (ones, 0, cntOnes + 1)
    347         upd(all, C(g, ones));
    348     
    349     int bad = 0;
    350     fore (pref, 0, c) {
    351         int minZeros = max(0, cntZeros - 1);
    352         int minMid = g - c;
    353         int sufLen = g - pref - 1;
    354         fore (z, minZeros, sufLen + 1)
    355             upd(bad, getSum(z, minMid, sufLen + 1));
    356     }
    357     return add(all, -bad);
    358 }
    359  
    360 inline void solve() {
    361     precalcFact();
    362     precalcShort(c);
    363     auto cnt = precalcCnt(n);
    364     
    365     int ans = 0;
    366     fore (g, 1, n + 1) {
    367         if (n % g != 0)
    368             continue;
    369         
    370         int cntFP = calcFixedPoints(g);
    371 //      cerr << "g = " << g << " += " << cnt[g] << " * " << cntFP << endl;
    372         upd(ans, mul(cnt[g], cntFP));
    373     }
    374     
    375 //  cerr << "ans/n = " << ans << " " << n << endl;
    376     cout << mul(ans, binPow(n, MOD - 2)) << endl;
    377 }
    378  
    379 int main() {
    380 #ifdef _DEBUG
    381     freopen("input.txt", "r", stdin);
    382     int tt = clock();
    383 #endif
    384     ios_base::sync_with_stdio(false);
    385     cin.tie(0), cout.tie(0);
    386     cout << fixed << setprecision(15);
    387     
    388     if(read()) {
    389         solve();
    390         
    391 #ifdef _DEBUG
    392         cerr << "TIME = " << clock() - tt << endl;
    393         tt = clock();
    394 #endif
    395     }
    396     return 0;
    397 }
    398 ```