codeforces-scrape

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

1840.md (10451B)


      1 Source: https://codeforces.com/blog/entry/117060
      2 
      3 [1840A - Cipher Shifer](/contest/1840/problem/A "Codeforces Round 878 (Div. 3)")
      4 
      5 Idea: [isosto](/profile/isosto "Candidate Master isosto"), preparation: [isosto](/profile/isosto "Candidate Master isosto")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 int main() {
     19     int t; cin >> t;
     20     while (t--) {
     21         int n; cin >> n;
     22         string s; cin >> s;
     23         int i = 0;
     24         while (i < n) {
     25             int start = i;
     26             cout << s[i++];
     27             while (s[i++] != s[start]);
     28         }
     29         cout << endl;
     30     }
     31 }
     32 ```
     33 
     34 **Rate the problem**
     35 
     36 * Didn't solve
     37 * Good task
     38 * Average task
     39 * Bad task
     40 
     41 [1840B - Binary Cafe](/contest/1840/problem/B "Codeforces Round 878 (Div. 3)")
     42 
     43 Idea: [diskoteka](/profile/diskoteka "Master diskoteka"), preparation: [diskoteka](/profile/diskoteka "Master diskoteka")
     44 
     45 **Tutorial**
     46 
     47 Tutorial is loading...
     48 
     49 **Solution**
     50 
     51 ```
     52 #include <bits/stdc++.h>
     53  
     54 using namespace std;
     55  
     56 int32_t main() {
     57     int t;
     58     cin >> t;
     59     while (t--) {
     60         int n, k;
     61         cin >> n >> k;
     62         k = min(k, 30);
     63         cout << min(n, (1 << k) - 1) + 1 << "\n";
     64     }
     65     return 0;
     66 }
     67 ```
     68 
     69 **Rate the problem**
     70 
     71 * Didn't solve
     72 * Good task
     73 * Average task
     74 * Bad task
     75 
     76 [1840C - Ski Resort](/contest/1840/problem/C "Codeforces Round 878 (Div. 3)")
     77 
     78 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), preparation: [playerr17](/profile/playerr17 "Expert playerr17")
     79 
     80 **Tutorial**
     81 
     82 Tutorial is loading...
     83 
     84 **Solution**
     85 
     86 ```
     87 testCases = int(input())
     88  
     89 for testCase in range(testCases):
     90     n, k, q = map(int, input().split(' '))
     91     a = list(map(int, input().split(' ')))
     92     
     93     ans = 0
     94     len = 0
     95     for i in range(n):
     96         if a[i] <= q:
     97             len += 1
     98         else:
     99             if len >= k:
    100                 ans += (len - k + 1) * (len - k + 2) // 2
    101             len = 0
    102     
    103     if len >= k:
    104         ans += (len - k + 1) * (len - k + 2) // 2
    105     print(ans)
    106 ```
    107 
    108 **Rate the problem**
    109 
    110 * Didn't solve
    111 * Good task
    112 * Average task
    113 * Bad task
    114 
    115 [1840D - Wooden Toy Festival](/contest/1840/problem/D "Codeforces Round 878 (Div. 3)")
    116 
    117 Idea: [diskoteka](/profile/diskoteka "Master diskoteka"), preparation: [diskoteka](/profile/diskoteka "Master diskoteka")
    118 
    119 **Tutorial**
    120 
    121 Tutorial is loading...
    122 
    123 **Solution**
    124 
    125 ```
    126 #include <bits/stdc++.h>
    127  
    128 using namespace std;
    129  
    130 int main() {
    131     int t;
    132     cin >> t;
    133     while (t--) {
    134         int n;
    135         cin >> n;
    136         vector<int> a(n);
    137         for (int i = 0; i < n; ++i) {
    138             cin >> a[i];
    139         }
    140         sort(a.begin(), a.end());
    141         int l = -1, r = 1e9;
    142         while (r - l > 1) {
    143             int m = (l + r) >> 1;
    144             int i = 0;
    145             while (i + 1 < a.size() && a[i + 1] - a[0] <= 2 * m) {
    146                 ++i;
    147             }
    148             int j = n - 1;
    149             while (j - 1 >= 0 && a.back() - a[j - 1] <= 2 * m) {
    150                 --j;
    151             }
    152             ++i; --j;
    153             if (i > j || a[j] - a[i] <= 2 * m) {
    154                 r = m;
    155             } else {
    156                 l = m;
    157             }
    158         }
    159         cout << r << "\n";
    160     }
    161     return 0;
    162 }
    163 ```
    164 
    165 **Rate the problem**
    166 
    167 * Didn't solve
    168 * Good task
    169 * Average task
    170 * Bad task
    171 
    172 [1840E - Character Blocking](/contest/1840/problem/E "Codeforces Round 878 (Div. 3)")
    173 
    174 Idea: [diskoteka](/profile/diskoteka "Master diskoteka"), preparation: [diskoteka](/profile/diskoteka "Master diskoteka")
    175 
    176 **Tutorial**
    177 
    178 Tutorial is loading...
    179 
    180 **Solution**
    181 
    182 ```
    183 #include <bits/stdc++.h>
    184  
    185 using namespace std;
    186  
    187 int main() {
    188     int x;
    189     cin >> x;
    190     while (x--) {
    191         vector<string> s(2);
    192         cin >> s[0] >> s[1];
    193         int n = s[0].size();
    194         int bad = 0;
    195         for (int i = 0; i < n; ++i) {
    196             if (s[0][i] != s[1][i]) {
    197                 ++bad;
    198             }
    199         }
    200         int t, q;
    201         cin >> t >> q;
    202         queue<pair<int, int>> unblock;
    203         for (int i = 0; i < q; ++i) {
    204             while (!unblock.empty() && unblock.front().first == i) {
    205                 if (s[0][unblock.front().second] != s[1][unblock.front().second]) {
    206                     ++bad;
    207                 }
    208                 unblock.pop();
    209             }
    210             int type;
    211             cin >> type;
    212             if (type == 1) {
    213                 int pos;
    214                 cin >> pos;
    215                 if (s[0][pos - 1] != s[1][pos - 1]) {
    216                     --bad;
    217                 }
    218                 unblock.emplace(i + t, pos - 1);
    219             } else if (type == 2) {
    220                 int num1, pos1, num2, pos2;
    221                 cin >> num1 >> pos1 >> num2 >> pos2;
    222                 --num1; --pos1; --num2; --pos2;
    223                 if (s[num1][pos1] != s[1 ^ num1][pos1]) {
    224                     --bad;
    225                 }
    226                 if (s[num2][pos2] != s[1 ^ num2][pos2]) {
    227                     --bad;
    228                 }
    229                 swap(s[num1][pos1], s[num2][pos2]);
    230                 if (s[num1][pos1] != s[1 ^ num1][pos1]) {
    231                     ++bad;
    232                 }
    233                 if (s[num2][pos2] != s[1 ^ num2][pos2]) {
    234                     ++bad;
    235                 }
    236             } else {
    237                 cout << (!bad ? "YES" : "NO") << "\n";
    238             }
    239         }
    240     }
    241     return 0;
    242 }
    243 ```
    244 
    245 **Rate the problem**
    246 
    247 * Didn't solve
    248 * Good task
    249 * Average task
    250 * Bad task
    251 
    252 [1840F - Railguns](/contest/1840/problem/F "Codeforces Round 878 (Div. 3)")
    253 
    254 Idea: [diskoteka](/profile/diskoteka "Master diskoteka"), preparation: [diskoteka](/profile/diskoteka "Master diskoteka")
    255 
    256 **Tutorial**
    257 
    258 Tutorial is loading...
    259 
    260 **Solution**
    261 
    262 ```
    263 #include <bits/stdc++.h>
    264  
    265 using namespace std;
    266  
    267 int main() {
    268     ios_base::sync_with_stdio(false);
    269     cin.tie(0); cout.tie(0);
    270     int q;
    271     cin >> q;
    272     while (q--) {
    273         int n, m;
    274         cin >> n >> m;
    275         int r;
    276         cin >> r;
    277         bool free[n + 1][m + 1][r + 1];
    278         for (int i = 0; i <= n; ++i) {
    279             for (int j = 0; j <= m; ++j) {
    280                 for (int k = 0; k <= r; ++k) {
    281                     free[i][j][k] = true;
    282                 }
    283             }
    284         }
    285         for (int i = 0; i < r; ++i) {
    286             int t, d, coord;
    287             cin >> t >> d >> coord;
    288             if (d == 1) {
    289                 for (int j = 0; j <= m; ++j) {
    290                     if (0 <= t - coord - j && t - coord - j <= r) {
    291                         free[coord][j][t - coord - j] = false;
    292                     }
    293                 }
    294             } else {
    295                 for (int j = 0; j <= n; ++j) {
    296                     if (0 <= t - coord - j && t - coord - j <= r) {
    297                         free[j][coord][t - coord - j] = false;
    298                     }
    299                 }
    300             }
    301         }
    302         bool dp[n + 1][m + 1][r + 1];
    303         for (int i = 0; i <= n; ++i) {
    304             for (int j = 0; j <= m; ++j) {
    305                 for (int k = 0; k <= r; ++k) {
    306                     dp[i][j][k] = !(i || j || k);
    307                     if (free[i][j][k]) {
    308                         if (i && dp[i - 1][j][k]) {
    309                             dp[i][j][k] = true;
    310                         }
    311                         if (j && dp[i][j - 1][k]) {
    312                             dp[i][j][k] = true;
    313                         }
    314                         if (k && dp[i][j][k - 1]) {
    315                             dp[i][j][k] = true;
    316                         }
    317                     }
    318                 }
    319             }
    320         }
    321         int ans = -1;
    322         for (int t = r; t >= 0; --t) {
    323             if (dp[n][m][t]) {
    324                 ans = n + m + t;
    325             }
    326         }
    327         cout << ans << "\n";
    328     }
    329     return 0;
    330 }
    331 ```
    332 
    333 **Rate the problem**
    334 
    335 * Didn't solve
    336 * Good task
    337 * Average task
    338 * Bad task
    339 
    340 [1840G1 - In Search of Truth (Easy Version)](/contest/1840/problem/G1 "Codeforces Round 878 (Div. 3)")
    341 
    342 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), preparation: [pavlekn](/profile/pavlekn "Master pavlekn")
    343 
    344 **Tutorial**
    345 
    346 Tutorial is loading...
    347 
    348 **Solution**
    349 
    350 ```
    351 #include <bits/stdc++.h>
    352  
    353 using namespace std;
    354  
    355 #define int long long
    356  
    357 const int MAXN = 1e6 + 7;
    358  
    359 int pos[MAXN];
    360  
    361 int32_t main() {
    362     int num;
    363     cin >> num;
    364     int ans = 0;
    365     int cur = 1;
    366     pos[num] = 1;
    367     for (int i = 0; i < 1000; ++i) {
    368         cout << '+' << " " << 1 << endl;
    369         ++cur;
    370         cin >> num;
    371         if (pos[num]) {
    372             cout << '!' << " " << cur - pos[num] << endl;
    373             return 0;
    374         }
    375         pos[num] = cur;
    376     }
    377     while (true) {
    378         cout << '+' << " " << 1000 << endl;
    379         cur += 1000;
    380         cin >> num;
    381         if (pos[num]) {
    382             cout << '!' << " " << cur - pos[num] << endl;
    383             return 0;
    384         }
    385         pos[num] = cur;
    386     }
    387     return 0;
    388 }
    389 ```
    390 
    391 **Rate the problem**
    392 
    393 * Didn't solve
    394 * Good task
    395 * Average task
    396 * Bad task
    397 
    398 [1840G2 - In Search of Truth (Hard Version)](/contest/1840/problem/G2 "Codeforces Round 878 (Div. 3)")
    399 
    400 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), preparation: [pavlekn](/profile/pavlekn "Master pavlekn")
    401 
    402 **Tutorial**
    403 
    404 Tutorial is loading...
    405 
    406 **Solution**
    407 
    408 ```
    409 #include <bits/stdc++.h>
    410  
    411 using namespace std;
    412  
    413 #define int long long
    414  
    415 const int MAXN = 1e6 + 7;
    416  
    417 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    418  
    419 int pos[MAXN];
    420  
    421 const int K = 400;
    422 const int T = 300;
    423  
    424 int get() {
    425     return rng() % MAXN;
    426 }
    427  
    428 int32_t main() {
    429     int num;
    430     cin >> num;
    431     int start = num;
    432     int cur_delta = 0;
    433     int N0 = num;
    434     for (int i = 0; i < K; ++i) {
    435         int delta = get();
    436         cout << '+' << " " << delta << endl;
    437         cur_delta += delta;
    438         cin >> num;
    439         N0 = max(N0, num);
    440     }
    441     cout << '-' << " " << cur_delta << endl;
    442     cin >> num;
    443     cout << '+' << " " << N0 - 1 << endl;
    444     cur_delta = N0 - 1;
    445     cin >> num;
    446     pos[num] = N0;
    447     for (int i = 0; i < T; ++i) {
    448         ++cur_delta;
    449         cout << '+' << " " << 1 << endl;
    450         cin >> num;
    451         pos[num] = N0 + i + 1;
    452         if (num == start) {
    453             cout << '!' << " " << N0 + i << endl;
    454             return 0;
    455         }
    456     }
    457     cout << '-' << " " << cur_delta << endl;
    458     cin >> num;
    459     int ans = 0;
    460     while (true) {
    461         cout << '-' << " " << T << endl;
    462         ans += T;
    463         cin >> num;
    464         if (pos[num]) {
    465             cout << '!' << " " << ans + pos[num] - 1 << endl;
    466             return 0;
    467         }
    468     }
    469     return 0;
    470 }
    471 ```
    472 
    473 **Rate the problem**
    474 
    475 * Didn't solve
    476 * Good task
    477 * Average task
    478 * Bad task