codeforces-scrape

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

2121.md (7354B)


      1 Source: https://codeforces.com/blog/entry/143822
      2 
      3 Thank you all for participating! 👊👊👊
      4 
      5 [2121A - Letter Home](/contest/2121/problem/A "Codeforces Round 1032 (Div. 3)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main() {
     19     ios_base::sync_with_stdio(0);
     20     cin.tie(0);
     21     cout.tie(0);
     22     int t;
     23     cin >> t;
     24     while (t--) {
     25         int n, s;
     26         cin >> n >> s;
     27         vector<int> x(n);
     28         for (int i = 0; i < n; i++) cin >> x[i];
     29         int ans = min(abs(s - x[0]), abs(s - x.back())) + x.back() - x[0];
     30         cout << ans << '\n';
     31     }
     32     return 0;
     33 }
     34 ```
     35 
     36 [2121B - Above the Clouds](/contest/2121/problem/B "Codeforces Round 1032 (Div. 3)")
     37 
     38 **Tutorial**
     39 
     40 Tutorial is loading...
     41 
     42 **Code**
     43 
     44 ```
     45 #include<bits/stdc++.h>
     46 
     47 using namespace std;
     48 
     49 int main() {
     50     ios_base::sync_with_stdio(0);
     51     cin.tie(0);
     52     cout.tie(0);
     53     int t;
     54     cin >> t;
     55     while (t--) {
     56         int n;
     57         cin >> n;
     58         string s;
     59         cin >> s;
     60         vector<int> cnt(26, 0);
     61         for (auto c : s) cnt[c - 'a']++;
     62         int flag = 0;
     63         for (int i = 0; i < 26; i++) {
     64             if (cnt[i] >= 3) flag = 1;
     65             else if (cnt[i] == 2 && (s[0] - 'a' != i || s.back() - 'a' != i)) flag = 1;
     66         }
     67         if (flag) cout << "Yes" << '\n';
     68         else cout << "No" << '\n';
     69     }
     70     return 0;
     71 }
     72 ```
     73 
     74 [2121C - Those Who Are With Us](/contest/2121/problem/C "Codeforces Round 1032 (Div. 3)")
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Code**
     81 
     82 ```
     83 #include<bits/stdc++.h>
     84 
     85 using namespace std;
     86 
     87 main() {
     88     ios_base::sync_with_stdio(0);
     89     cin.tie(0);
     90     cout.tie(0);
     91     int t;
     92     cin >> t;
     93     while (t--) {
     94         int n, m;
     95         cin >> n >> m;
     96         vector<vector<int>> a(n, vector<int> (m));
     97         int mx = 0, cnt_mx = 0;
     98         for (int i = 0; i < n; i++) {
     99             for (int j = 0; j < m; j++) {
    100                 cin >> a[i][j];
    101                 if (a[i][j] > mx) {
    102                     mx = a[i][j], cnt_mx = 1;
    103                 } else if (a[i][j] == mx) {
    104                     cnt_mx++;
    105                 }
    106             }
    107         }
    108         vector<int> r(n), c(m);
    109         for (int i = 0; i < n; i++) {
    110             for (int j = 0; j < m; j++) {
    111                 if (a[i][j] == mx) {
    112                     r[i]++;
    113                     c[j]++;
    114                 }
    115             }
    116         }
    117         int flag = 0;
    118         for (int i = 0; i < n; i++) {
    119             for (int j = 0; j < m; j++) {
    120                 if (r[i] + c[j] - (a[i][j] == mx) == cnt_mx) {
    121                     flag = 1;
    122                 }
    123             }
    124         }
    125         cout << mx - flag << '\n';
    126     }
    127     return 0;
    128 }
    129 ```
    130 
    131 [2121D - 1709](/contest/2121/problem/D "Codeforces Round 1032 (Div. 3)")
    132 
    133 **Tutorial**
    134 
    135 Tutorial is loading...
    136 
    137 **Code**
    138 
    139 ```
    140 #include<bits/stdc++.h>
    141 
    142 using namespace std;
    143 
    144 main() {
    145     ios_base::sync_with_stdio(0);
    146     cin.tie(0);
    147     cout.tie(0);
    148     int t;
    149     cin >> t;
    150     while (t--) {
    151         int n;
    152         cin >> n;
    153         vector<int> a(n), b(n);
    154         for (int i = 0; i < n; i++) cin >> a[i];
    155         for (int i = 0; i < n; i++) cin >> b[i];
    156         vector<pair<int, int>> ans;
    157         for (int i = 0; i < n; i++) {
    158             for (int j = 1; j < n; j++) {
    159                 if (a[j - 1] > a[j]) {
    160                     swap(a[j - 1], a[j]);
    161                     ans.push_back({1, j});
    162                 }
    163             }
    164         }
    165         for (int i = 0; i < n; i++) {
    166             for (int j = 1; j < n; j++) {
    167                 if (b[j - 1] > b[j]) {
    168                     swap(b[j - 1], b[j]);
    169                     ans.push_back({2, j});
    170                 }
    171             }
    172         }
    173         for (int i = 0; i < n; i++) {
    174             if (a[i] > b[i]) {
    175                 ans.push_back({3, i + 1});
    176             }
    177         }
    178         cout << ans.size() << '\n';
    179         for (auto [x, y] : ans) cout << x << " " << y << '\n';
    180     }
    181     return 0;
    182 }
    183 ```
    184 
    185 [2121E - Sponsor of Your Problems](/contest/2121/problem/E "Codeforces Round 1032 (Div. 3)")
    186 
    187 **Tutorial**
    188 
    189 Tutorial is loading...
    190 
    191 **Code**
    192 
    193 ```
    194 #include<bits/stdc++.h>
    195 
    196 using namespace std;
    197 
    198 int main() {
    199     ios_base::sync_with_stdio(0);
    200     cin.tie(0);
    201     cout.tie(0);
    202     int t;
    203     cin >> t;
    204     while (t--) {
    205         string l, r;
    206         cin >> l >> r;
    207         if (l == r) {
    208             cout << 2 * l.size() << '\n';
    209             continue;
    210         }
    211         int ptr = 0;
    212         while (ptr < l.size() && l[ptr] == r[ptr]) ptr++;
    213         if (l[ptr] + 1 < r[ptr]) {
    214             cout << 2 * ptr << '\n';
    215         } else {
    216             int res = 2 * ptr + 1;
    217             for (int i = ptr + 1; i < l.size(); i++) {
    218                 if (l[i] == '9' && r[i] == '0') res++;
    219                 else break;
    220             }
    221             cout << res << '\n';
    222         }
    223     }
    224     return 0;
    225 }
    226 ```
    227 
    228 [2121F - Yamakasi](/contest/2121/problem/F "Codeforces Round 1032 (Div. 3)")
    229 
    230 **Tutorial**
    231 
    232 Tutorial is loading...
    233 
    234 **Code**
    235 
    236 ```
    237 #include<bits/stdc++.h>
    238 
    239 using namespace std;
    240 
    241 typedef long long ll;
    242 int const maxn = 2e5 + 5;
    243 int a[maxn];
    244 ll pref[maxn], s;
    245 
    246 main() {
    247     ios_base::sync_with_stdio(0);
    248     cin.tie(0);
    249     cout.tie(0);
    250     int t;
    251     cin >> t;
    252     while (t--) {
    253         int n, x;
    254         cin >> n >> s >> x;
    255         for (int i = 1; i <= n; i++) {
    256             cin >> a[i];
    257             pref[i] = pref[i - 1] + a[i];
    258         }
    259         ll ans = 0;
    260         map<ll, int> cnt;
    261         int lef = 1;
    262         for (int r = 1; r <= n; r++) {
    263             if (a[r] > x) cnt.clear(), lef = r + 1;
    264             else if (a[r] == x) {
    265                 while (lef <= r) {
    266                     cnt[pref[lef - 1]]++;
    267                     lef++;
    268                 }
    269             }
    270             ans += cnt[pref[r] - s];
    271         }
    272         cout << ans << '\n';
    273     }
    274     return 0;
    275 }
    276 ```
    277 
    278 [2121G - Gangsta](/contest/2121/problem/G "Codeforces Round 1032 (Div. 3)")
    279 
    280 **Tutorial**
    281 
    282 Tutorial is loading...
    283 
    284 **Code**
    285 
    286 ```
    287 #include<bits/stdc++.h>
    288 
    289 using namespace std;
    290 
    291 typedef long long ll;
    292 int const maxn = 2e5 + 5;
    293 int pref[maxn];
    294 
    295 main() {
    296     ios_base::sync_with_stdio(0);
    297     cin.tie(0);
    298     cout.tie(0);
    299     int t;
    300     cin >> t;
    301     while (t--) {
    302         int n;
    303         cin >> n;
    304         string s;
    305         cin >> s;
    306         ll ans = 0;
    307         for (int i = 0; i < n; i++) {
    308             pref[i + 1] = pref[i];
    309             if (s[i] == '0') pref[i + 1]--;
    310             else pref[i + 1]++;
    311         }
    312         for (int i = 1; i <= n; i++) {
    313             ans += (ll)i * (n - i + 1);
    314         }
    315         sort(pref, pref + n + 1);
    316         for (int i = 0; i <= n; i++) {
    317             ans += (ll)pref[i] * (i - (n - i));
    318         }
    319         cout << ans / 2 << '\n';
    320     }
    321     return 0;
    322 }
    323 ```
    324 
    325 [2121H - Ice Baby](/contest/2121/problem/H "Codeforces Round 1032 (Div. 3)")
    326 
    327 **Tutorial**
    328 
    329 Tutorial is loading...
    330 
    331 **Code**
    332 
    333 ```
    334 #include<bits/stdc++.h>
    335 
    336 using namespace std;
    337 
    338 main() {
    339     ios_base::sync_with_stdio(0);
    340     cin.tie(0);
    341     cout.tie(0);
    342     int t;
    343     cin >> t;
    344     while (t--) {
    345         int n;
    346         cin >> n;
    347         multiset<int> dp;
    348         for (int i = 1; i <= n; i++) {
    349             int l, r;
    350             cin >> l >> r;
    351             auto it = dp.upper_bound(r);
    352             if (it != dp.end()) {
    353                 dp.erase(it);
    354             }
    355             dp.insert(l);
    356             cout << dp.size() << " ";
    357         }
    358         cout << '\n';
    359     }
    360     return 0;
    361 }
    362 ```