codeforces-scrape

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

2072.md (7526B)


      1 Source: https://codeforces.com/blog/entry/140039
      2 
      3 ### Thanks for participating in the most isekai NyaForces contest!
      4 
      5 We honestly strived to make good tasks.
      6 
      7 [2072A - New World, New Me, New Array](/contest/2072/problem/A "Codeforces Round 1006 (Div. 3)")
      8 
      9 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm")
     10 
     11 **Tutorial**
     12 
     13 Tutorial is loading...
     14 
     15 **Solution**
     16 
     17 ```
     18 #include <bits/stdc++.h>
     19 
     20 using namespace std;
     21 
     22 void solve() {
     23   int n, k, p;
     24   cin >> n >> k >> p;
     25   if (-n * p <= k && k <= n * p) {
     26     cout << (abs(k) + p - 1) / p << '\n';
     27   } else {
     28     cout << "-1\n";
     29   }
     30 }
     31 
     32 int main() {
     33   int tt;
     34   cin >> tt;
     35   while (tt --> 0) {
     36     solve();
     37   }
     38   return 0;
     39 }
     40 ```
     41 
     42 **Rate the problem**
     43 
     44 * Didn't solve
     45 * Good task
     46 * Average task
     47 * Bad task
     48 
     49 [2072B - Having Been a Treasurer in the Past, I Help Goblins Deceive](/contest/2072/problem/B "Codeforces Round 1006 (Div. 3)")
     50 
     51 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm")
     52 
     53 **Tutorial**
     54 
     55 Tutorial is loading...
     56 
     57 **Solution**
     58 
     59 ```
     60 #include <bits/stdc++.h>
     61 
     62 using namespace std;
     63 
     64 void solve() {
     65   int n;
     66   string s;
     67   cin >> n >> s;
     68   int64_t dash = count(s.begin(), s.end(), '-');
     69   int64_t under = n - dash;
     70   int64_t ans = (dash / 2) * (dash - dash / 2) * under;
     71   cout << ans << '\n';
     72 }
     73 
     74 int main() {
     75   int tt;
     76   cin >> tt;
     77   while (tt --> 0) {
     78     solve();
     79   }
     80   return 0;
     81 }
     82 ```
     83 
     84 **Rate the problem**
     85 
     86 * Didn't solve
     87 * Good task
     88 * Average task
     89 * Bad task
     90 
     91 [2072C - Creating Keys for StORages Has Become My Main Skill](/contest/2072/problem/C "Codeforces Round 1006 (Div. 3)")
     92 
     93 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm"), [IceHydra](/profile/IceHydra "Expert IceHydra")
     94 
     95 **Tutorial**
     96 
     97 Tutorial is loading...
     98 
     99 **Solution**
    100 
    101 ```
    102 #include <iostream>
    103 #include <vector>
    104 
    105 using namespace std;
    106 
    107 void Solve() {
    108   int len, val;
    109   cin >> len >> val;
    110   vector<int> ans(len, val);
    111   int or_val = 0;
    112   bool flag = true;
    113   for (int i = 0; i < len - 1; ++i) {
    114     if (((or_val | i) & val) == (or_val | i)) {
    115       or_val |= i;
    116       ans[i] = i;
    117     } else {
    118       flag = false;
    119       break;
    120     }
    121   }
    122   if (flag && (or_val | (len - 1)) == val) {
    123     ans[len - 1] = len - 1;
    124   }
    125   for (auto it : ans) cout << it << ' ';
    126   cout << '\n';
    127 }
    128 
    129 signed main() {
    130   cin.tie(0)->sync_with_stdio(0);
    131   int test_count = 1;
    132   cin >> test_count;
    133   while (test_count --> 0) Solve();
    134 }
    135 ```
    136 
    137 **Rate the problem**
    138 
    139 * Didn't solve
    140 * Good task
    141 * Average task
    142 * Bad task
    143 
    144 [2072D - For Wizards, the Exam Is Easy, but I Couldn't Handle It](/contest/2072/problem/D "Codeforces Round 1006 (Div. 3)")
    145 
    146 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm")
    147 
    148 **Tutorial**
    149 
    150 Tutorial is loading...
    151 
    152 **Solution**
    153 
    154 ```
    155 #include <bits/stdc++.h>
    156 
    157 using namespace std;
    158 
    159 void solve() {
    160   int n;
    161   cin >> n;
    162   vector<int> a(n);
    163   for (int i = 0; i < n; ++i) {
    164     cin >> a[i];
    165   }
    166 
    167   int best_diff = 0, L = 0, R = 0;
    168   for (int i = 0; i < n; ++i) {
    169     int cnt_greater = 0, cnt_less = 0;
    170     for (int j = i + 1; j < n; ++j) {
    171       cnt_greater += a[j] > a[i];
    172       cnt_less += a[j] < a[i];
    173 
    174       if (best_diff > cnt_greater - cnt_less) {
    175         best_diff = cnt_greater - cnt_less;
    176         L = i, R = j;
    177       }
    178     }
    179   }
    180 
    181   cout << L + 1 << ' ' << R + 1 << '\n';
    182 }
    183 
    184 int main() {
    185   int tt = 1;
    186   cin >> tt;
    187   while (tt --> 0) {
    188     solve();
    189   }
    190   return 0;
    191 }
    192 ```
    193 
    194 **Rate the problem**
    195 
    196 * Didn't solve
    197 * Good task
    198 * Average task
    199 * Bad task
    200 
    201 [2072E - Do You Love Your Hero and His Two-Hit Multi-Target Attacks?](/contest/2072/problem/E "Codeforces Round 1006 (Div. 3)")
    202 
    203 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm")
    204 
    205 **Tutorial**
    206 
    207 Tutorial is loading...
    208 
    209 **Solution**
    210 
    211 ```
    212 #include <bits/stdc++.h>
    213 
    214 using namespace std;
    215 
    216 vector<pair<int64_t, int64_t>> rec(int64_t k, int64_t x0 = 0, int64_t y0 = 0) {
    217   if (!k) {
    218     return {};
    219   }
    220   int64_t delta = 0;
    221   while (delta * (delta - 1) / 2 <= k) {
    222     delta++;
    223   }
    224   delta--;
    225   auto remaining = rec(k - delta * (delta - 1) / 2, x0 + delta + 1, y0 + 1);
    226   vector<pair<int64_t, int64_t>> ans;
    227   for (int x = x0; x < x0 + delta; ++x) {
    228     ans.push_back({x, y0});
    229   }
    230   ans.insert(ans.end(), remaining.begin(), remaining.end());
    231   return ans;
    232 }
    233 
    234 void solve() {
    235   int64_t k;
    236   cin >> k;
    237   if (!k) {
    238     cout << "1\n69 52\n";
    239     return;
    240   }
    241   auto ans = rec(k, 0, 0);
    242   cout << ans.size() << '\n';
    243   for (auto [x, y] : ans) {
    244     cout << x << ' ' << y << '\n';
    245   }
    246 }
    247 
    248 int main() {
    249   int tt = 1;
    250   cin >> tt;
    251   while (tt --> 0) {
    252     solve();
    253   }
    254   return 0;
    255 }
    256 ```
    257 
    258 **Rate the problem**
    259 
    260 * Didn't solve
    261 * Good task
    262 * Average task
    263 * Bad task
    264 
    265 [2072F - Goodbye, Banker Life](/contest/2072/problem/F "Codeforces Round 1006 (Div. 3)")
    266 
    267 Idea: [itz_pabloo](/profile/itz_pabloo "Expert itz_pabloo")
    268 
    269 **Tutorial**
    270 
    271 Tutorial is loading...
    272 
    273 **Solution**
    274 
    275 ```
    276 #include <bits/stdc++.h>
    277 
    278 using namespace std;
    279 
    280 constexpr int64_t kMaxN = 1e6 + 69;
    281 vector<int64_t> c(kMaxN);
    282 
    283 void precalc() {
    284   c[0] = c[1] = 0;
    285   for (int i = 2; i < kMaxN; ++i) {
    286     c[i] = c[i - 1];
    287     int x = i;
    288     while (x % 2 == 0) {
    289       x /= 2, c[i]++;
    290     }
    291   }
    292 }
    293 
    294 void solve() {
    295   int n, k;
    296   cin >> n >> k;
    297 
    298   --n;
    299   for (int i = 0; i <= n; ++i) {
    300     cout << k * (c[n] == c[i] + c[n - i]) << " \n"[i == n];
    301   }
    302 }
    303 
    304 int main() {
    305   ios::sync_with_stdio(0);
    306   cin.tie(0);
    307 
    308   precalc();
    309 
    310   int tt = 1;
    311   cin >> tt;
    312   while (tt --> 0) {
    313     solve();
    314   }
    315   return 0;
    316 }
    317 ```
    318 
    319 **Rate the problem**
    320 
    321 * Didn't solve
    322 * Good task
    323 * Average task
    324 * Bad task
    325 
    326 [2072G - I've Been Flipping Numbers for 300 Years and Calculated the Sum](/contest/2072/problem/G "Codeforces Round 1006 (Div. 3)")
    327 
    328 Idea: [ne_justlm](/profile/ne_justlm "Specialist ne_justlm"), [IceHydra](/profile/IceHydra "Expert IceHydra")
    329 
    330 **Tutorial**
    331 
    332 Tutorial is loading...
    333 
    334 **Solution**
    335 
    336 ```
    337 #include <bits/stdc++.h>
    338 
    339 using namespace std;
    340 
    341 constexpr int64_t mod = 1e9 + 7;
    342 constexpr int64_t twoInv = 500'000'004;
    343 constexpr int64_t sixInv = 166'666'668;
    344 
    345 int64_t add(int64_t a, int64_t b) {
    346   return (a % mod + b % mod) % mod;
    347 }
    348 
    349 int64_t mns(int64_t a, int64_t b) {
    350   return (a % mod - b % mod + mod) % mod;
    351 }
    352 
    353 int64_t mul(int64_t a, int64_t b) {
    354   return (a % mod) * (b % mod) % mod;
    355 }
    356 
    357 int64_t rev(int64_t n, int64_t p) {
    358   int64_t res = 0;
    359   while (n) {
    360     res = add(mul(res, p), n % p);
    361     n /= p;
    362   }
    363   return res;
    364 }
    365 
    366 int64_t stupid(int64_t n, int64_t k) {
    367   int64_t res = 0;
    368   for (int64_t p = 2; p <= k; ++p) {
    369     res = add(res, rev(n, p));
    370   }
    371   return res;
    372 }
    373 
    374 int64_t sum1(int64_t r) {
    375   return mul(mul(r, r + 1), twoInv);
    376 }
    377 
    378 int64_t sum1(int64_t l, int64_t r) {
    379   return mns(sum1(r), sum1(l - 1));
    380 }
    381 
    382 int64_t sum2(int64_t r) {
    383   return mul(mul(mul(r, r + 1), 2 * r + 1), sixInv);
    384 }
    385 
    386 int64_t sum2(int64_t l, int64_t r) {
    387   return mns(sum2(r), sum2(l - 1));
    388 }
    389 
    390 int64_t get(int64_t n, int64_t l, int64_t r) {
    391   if (l > r) {
    392     return 0;
    393   }
    394 
    395   int64_t res = mul(sum1(l, r), n);
    396   int64_t minus = 0, plus = 0;
    397 
    398   int64_t L = l;
    399   while (L <= r) {
    400     int64_t value = n / L;
    401     int64_t R = min(r, n / value);
    402 
    403     minus = add(minus, mul(sum2(L, R), value));
    404     plus = add(plus, mul(R - L + 1, value));
    405 
    406     L = R + 1;
    407   }
    408 
    409   return add(mns(res, minus), plus);
    410 }
    411 
    412 void solve() {
    413   int64_t n, k;
    414   cin >> n >> k;
    415 
    416   int64_t sq = (int64_t)sqrtl((long double)n);
    417   int64_t ans = mul(max<int64_t>(0, k - n), n);
    418   ans = add(ans, stupid(n, min(sq, k)));
    419   ans = add(ans, get(n, sq + 1, min(n, k)));
    420 
    421   cout << ans << '\n';
    422 }
    423 
    424 int main() {
    425   int tt = 1;
    426   cin >> tt;
    427   while (tt --> 0) {
    428     solve();
    429   }
    430   return 0;
    431 }
    432 ```
    433 
    434 **Rate the problem**
    435 
    436 * Didn't solve
    437 * Good task
    438 * Average task
    439 * Bad task