codeforces-scrape

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

2238.md (8260B)


      1 Source: https://codeforces.com/blog/entry/154829
      2 
      3 Thank you for participating in the round! We hope you enjoyed the problems. We worked very hard while preparing this contest :)
      4 
      5 Hints for the problems will be published a bit later.
      6 
      7 **Rate the round**
      8 
      9 Excellent round
     10 
     11 Good round
     12 
     13 Average round
     14 
     15 Bad round
     16 
     17 Awful round
     18 
     19 [2238A - Another Puzzle from Papyrus](/contest/2238/problem/A "Codeforces Round 1106 (Div. 2)")
     20 
     21 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks")
     22 
     23 **Solution**
     24 
     25 Tutorial is loading...
     26 
     27 **Code**
     28 
     29 ```
     30 #include<bits/stdc++.h>
     31 
     32 using namespace std;
     33 
     34 int main() {
     35     int t;
     36     cin >> t;
     37     while (t--) {
     38         int n, C;
     39         cin >> n >> C;
     40         int ans = 0;
     41         vector<int> a(n), b(n);
     42         for (int i = 0; i < n; ++i) cin >> a[i];
     43         for (int i = 0; i < n; ++i) cin >> b[i];
     44         bool needReorder = false;
     45         for (int i = 0; i < n; ++i) {
     46             if (a[i] < b[i]) needReorder = true;
     47             ans += a[i];
     48             ans -= b[i];
     49         }
     50         if (needReorder) {
     51             needReorder = false;
     52             ans += C;
     53             sort(a.begin(), a.end());
     54             sort(b.begin(), b.end());
     55             for (int i = 0; i < n; ++i) {
     56                 if (a[i] < b[i]) {
     57                     needReorder = true;
     58                 }
     59             }
     60         }
     61         if (needReorder) cout << "-1\n";
     62         else cout << ans << "\n";
     63     }
     64 }
     65 ```
     66 
     67 **Rate the problem**
     68 
     69 Excellent problem
     70 
     71 Good problem
     72 
     73 Average problem
     74 
     75 Bad problem
     76 
     77 Awful problem
     78 
     79 [2238B - Crimson Triples](/contest/2238/problem/B "Codeforces Round 1106 (Div. 2)")
     80 
     81 Idea: [KotlechkovEgor](/profile/KotlechkovEgor "Master KotlechkovEgor")
     82 
     83 **Solution**
     84 
     85 Tutorial is loading...
     86 
     87 **Code**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 
     92 using namespace std;
     93 
     94 void solve() {
     95     int n;
     96     cin >> n;
     97     long long an = 0;
     98     for (int b = 1; b <= n; b++) {
     99         an += 1ll * (n / b) * (n / b);
    100     }
    101     cout << an << '\n';
    102 }
    103 
    104 signed main() {
    105     signed t_ = 1;
    106     cin >> t_;
    107     while (t_--) {
    108         solve();
    109     }
    110 }
    111 ```
    112 
    113 **Rate the problem**
    114 
    115 Excellent problem
    116 
    117 Good problem
    118 
    119 Average problem
    120 
    121 Bad problem
    122 
    123 Awful problem
    124 
    125 [2238C - Village Guilds](/contest/2238/problem/C "Codeforces Round 1106 (Div. 2)")
    126 
    127 Idea: [lewc](/profile/lewc "Grandmaster lewc")
    128 
    129 **Solution**
    130 
    131 Tutorial is loading...
    132 
    133 **Code**
    134 
    135 ```
    136 #include <bits/stdc++.h>
    137 
    138 using namespace std;
    139 
    140 const int maxn = 2e5;
    141 vector<int> g[maxn];
    142 int depth[maxn], dp[maxn];
    143 long long ans[maxn];
    144 
    145 void dfs(int v, int p = -1) {
    146     ans[v] = 0;
    147     dp[v] = depth[v];
    148     int m1 = depth[v], m2 = depth[v];
    149     for (auto u : g[v]) {
    150         if (u != p) {
    151             depth[u] = depth[v] + 1;
    152             dfs(u, v);
    153             dp[v] = max(dp[v], dp[u]);
    154             ans[v] += ans[u];
    155             if (dp[u] >= m1) {
    156                 m2 = m1;
    157                 m1 = dp[u];
    158             }  else if (dp[u] >= m2) {
    159                 m2 = dp[u];
    160             }
    161         }
    162     }
    163     ans[v] += m2 - depth[v] + 1;
    164 }
    165 
    166 void solve() {
    167     int n;
    168     cin >> n;
    169     for (int i = 1; i < n; ++i) {
    170         int p;
    171         cin >> p;
    172         g[p - 1].push_back(i);
    173     }
    174     dfs(0);
    175     cout << ans[0] << '\n';
    176     for (int i = 0; i < n; ++i) {
    177         g[i].clear();
    178     }
    179 }
    180 
    181 int main() {
    182     cin.tie(0);
    183     ios::sync_with_stdio(0);
    184 
    185     int t = 1;
    186     cin >> t;
    187     while (t--) {
    188         solve();
    189     }
    190 
    191     return 0;
    192 }
    193 ```
    194 
    195 **Rate the problem**
    196 
    197 Excellent problem
    198 
    199 Good problem
    200 
    201 Average problem
    202 
    203 Bad problem
    204 
    205 Awful problem
    206 
    207 [2238D - Storming Arasaka](/contest/2238/problem/D "Codeforces Round 1106 (Div. 2)")
    208 
    209 Idea: [Friendiks](/profile/Friendiks "Grandmaster Friendiks")
    210 
    211 **Solution**
    212 
    213 Tutorial is loading...
    214 
    215 **Code**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219 
    220 using namespace std;
    221 
    222 const int maxn = 1e6 + 7;
    223 
    224 int m[maxn], A[maxn], prime[maxn], nxt[maxn];
    225 
    226 int main() {
    227     for (int p = 2; p < maxn; ++p) {
    228         if (prime[p] == 0) {
    229             for (int x = p; x < maxn; x += p) {
    230                 if (prime[x] == 0) prime[x] = p;
    231             }
    232         }
    233         if (prime[p / prime[p]] == prime[p]) nxt[p] = nxt[p / prime[p]];
    234         else nxt[p] = p / prime[p];
    235         m[p] = m[nxt[p]] + 1;
    236         A[p] = A[p / prime[p]] + 1;
    237     }
    238     int t;
    239     cin >> t;
    240     while (t--) {
    241         int n;
    242         cin >> n;
    243         cout << m[n] + A[n] - 1 << "\n";
    244     }
    245     return 0;
    246 }
    247 ```
    248 
    249 **Rate the problem**
    250 
    251 Excellent problem
    252 
    253 Good problem
    254 
    255 Average problem
    256 
    257 Bad problem
    258 
    259 Awful problem
    260 
    261 [2238E - Cake Trial](/contest/2238/problem/E "Codeforces Round 1106 (Div. 2)")
    262 
    263 Idea: [lewc](/profile/lewc "Grandmaster lewc")
    264 
    265 **Solution**
    266 
    267 Tutorial is loading...
    268 
    269 **Code**
    270 
    271 ```
    272 #include <bits/stdc++.h>
    273 
    274 using namespace std;
    275 
    276 void solve() {
    277     int n;
    278     string s;
    279     cin >> n >> s;
    280     vector<vector<int>> dp(n + 1, vector<int> (n + 1, 1e9));
    281     dp[0][0] = 0; 
    282     for (int i = 0; i < n; ++i) {
    283         vector<vector<int>> ndp(n + 1, vector<int> (n + 1, 1e9));
    284         for (int cnt_f = 0; cnt_f <= i; ++cnt_f) {
    285             for (int cur_s = 0; cur_s <= i; ++cur_s) {
    286                 if (s[i] != 'T') {
    287                     ndp[cnt_f + 1][cur_s + 1] = min(ndp[cnt_f + 1][cur_s + 1], max(dp[cnt_f][cur_s], cur_s + 1));
    288                 }
    289                 if (s[i] != 'F') {
    290                     ndp[cnt_f][max(0, cur_s - 1)] = min(ndp[cnt_f][max(0, cur_s - 1)], dp[cnt_f][cur_s]);
    291                 }
    292             }
    293         }
    294         swap(dp, ndp);
    295     }
    296     int rs = 0;
    297     for (int i = 0; i <= n; ++i) {
    298         for (int j = 0; j <= n; ++j) {
    299             rs = max(rs, i - dp[i][j]);
    300         }
    301     }
    302     cout << rs << '\n';
    303 }
    304 
    305 int main(){
    306     cin.tie(0);
    307     ios::sync_with_stdio(0);
    308 
    309     int t;
    310     cin >> t;
    311     while (t--) {
    312         solve();
    313     }
    314 
    315     return 0;
    316 }
    317 ```
    318 
    319 **Rate the problem**
    320 
    321 Excellent problem
    322 
    323 Good problem
    324 
    325 Average problem
    326 
    327 Bad problem
    328 
    329 Awful problem
    330 
    331 [2238F - Infinite Work](/contest/2238/problem/F "Codeforces Round 1106 (Div. 2)")
    332 
    333 Idea: [KotlechkovEgor](/profile/KotlechkovEgor "Master KotlechkovEgor")
    334 
    335 **Solution**
    336 
    337 Tutorial is loading...
    338 
    339 **Code**
    340 
    341 ```
    342 #include <bits/stdc++.h>
    343 
    344 using namespace std;
    345 
    346 using ll = long long;
    347 
    348 const int maxn = 2e6 + 1;
    349 const ll mod = 1e9 + 7;
    350 
    351 struct md {
    352     ll x;
    353 
    354     md(ll p) {
    355         x = p % mod;
    356     }
    357 
    358     md operator+(md other) {
    359         int p = x + other.x;
    360         if (p >= mod) {
    361             p -= mod;
    362         }
    363         if (p >= mod) {
    364             p %= mod;
    365         }
    366         return {p};
    367     }
    368 
    369     md operator-(md other) {
    370         int p = x - other.x;
    371         if (p < 0) {
    372             p += mod;
    373         }
    374         if (p < 0) {
    375             p = (p % mod + mod) % mod;
    376         }
    377         return {p};
    378     }
    379 
    380     md operator*(md other) {
    381         return {1ll * x * other.x % mod};
    382     }
    383 
    384     md operator^(int x) {
    385         if (x == 0) {
    386             return {1};
    387         }
    388         if (x % 2 == 0) {
    389             md p = *this ^ (x / 2);
    390             return {p * p};
    391         }
    392         return *this * (*this ^ (x - 1));
    393     }
    394 
    395     md operator/(md p) {
    396         return *this * (p ^ (mod - 2));
    397     }
    398 };
    399 
    400 vector<md> fact(1, md(1));
    401 vector<md> rfact = fact;
    402 
    403 void prec() {
    404     fact.resize(maxn, md(1));
    405     rfact = fact;
    406     for (int i = 1; i < fact.size(); ++i) {
    407         fact[i] = fact[i - 1] * md(i);
    408     }
    409     rfact[maxn - 1] = md(1) / fact[maxn - 1];
    410     for (int i = maxn - 2; i >= 0; --i) {
    411         rfact[i] = rfact[i + 1] * (i + 1);
    412     }
    413 }
    414 
    415 md c(int n, int k) {
    416     if (n < 0 || k < 0 || k > n)return md(1);
    417     return fact[n] * rfact[k] * rfact[n - k];
    418 }
    419 
    420 md catalan(int n) {
    421     if(n == 0){
    422         return 1;
    423     }
    424     return c(2 * n, n) - c(2 * n, n - 1);
    425 }
    426 
    427 void solve() {
    428     ll n, k;
    429     cin >> n >> k;
    430     k++;
    431     vector<ll> bits(61);
    432     for (int i = 0; i < 61; ++i) {
    433         bits[i] = k >> i & 1;
    434     }
    435     for (ll x = 60; x >= n; x--) {
    436         bits[x - 1] += 2 * bits[x];
    437         bits[x] = 0;
    438     }
    439     int sm = 0;
    440     for (int i = 0; i < 61; ++i) {
    441         sm += bits[i];
    442     }
    443     md an = catalan(sm - 1) * fact[sm];
    444     for (int i = 0; i < 61; ++i) {
    445         if (bits[i] >= 2) {
    446             an = an * rfact[bits[i]];
    447         }
    448     }
    449     cout << an.x << '\n';
    450 }
    451 
    452 signed main() {
    453     prec();
    454     signed t_ = 1;
    455     cin >> t_;
    456     while (t_--) {
    457         solve();
    458     }
    459 }
    460 ```
    461 
    462 **Rate the problem**
    463 
    464 Excellent problem
    465 
    466 Good problem
    467 
    468 Average problem
    469 
    470 Bad problem
    471 
    472 Awful problem