codeforces-scrape

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

1579.md (8810B)


      1 Source: https://codeforces.com/blog/entry/95447
      2 
      3 [1579A - Casimir's String Solitaire](/contest/1579/problem/A "Codeforces Round 744 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      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;
     20     cin >> t;
     21     while (t--) {
     22         string s;
     23         cin >> s;
     24         cout << (count(s.begin(), s.end(), 'B') * 2 == s.size() ?
     25                  "YES\n" : "NO\n");
     26     }
     27 }
     28 ```
     29 
     30 [1579B - Shifting Sort](/contest/1579/problem/B "Codeforces Round 744 (Div. 3)")
     31 
     32 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
     33 
     34 **Tutorial**
     35 
     36 Tutorial is loading...
     37 
     38 **Solution**
     39 
     40 ```
     41 #include <bits/stdc++.h>
     42 
     43 using namespace std;
     44 
     45 typedef pair<int, int> pii;
     46 
     47 int main() {
     48     int t;
     49     cin >> t;
     50     while (t--) {
     51         int n;
     52         cin >> n;
     53         vector<int> a(n);
     54         vector<pii> actions;
     55         for (int i = 0; i < n; i++)
     56             cin >> a[i];
     57 
     58         for (int i = 0; i < n - 1; i++) {
     59             int min_pos = i;
     60             for (int j = i + 1; j < n; j++)
     61                 if (a[j] < a[min_pos])
     62                     min_pos = j;
     63 
     64             if (min_pos > i) {
     65                 actions.push_back({i, min_pos});
     66                 int opt = a[min_pos];
     67                 for (int j = min_pos; j > i; j--)
     68                     a[j] = a[j - 1];
     69                 a[i] = opt;
     70             }
     71         }
     72 
     73         cout << actions.size() << '\n';
     74         for (auto &lr: actions) {
     75             cout << lr.first + 1 << ' ' << lr.second + 1 << ' ' << lr.second - lr.first << '\n';
     76         }
     77     }
     78 
     79 }
     80 ```
     81 
     82 [1579C - Ticks](/contest/1579/problem/C "Codeforces Round 744 (Div. 3)")
     83 
     84 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     85 
     86 **Tutorial**
     87 
     88 Tutorial is loading...
     89 
     90 **Solution**
     91 
     92 ```
     93 #include <bits/stdc++.h>
     94 
     95 using namespace std;
     96 
     97 int main() {
     98     int t;
     99     cin >> t;
    100     while (t--) {
    101         int n, m, k;
    102         cin >> n >> m >> k;
    103         vector<vector<int>> status(n, vector<int>(m, 0));
    104         for (int i = 0; i < n; i++) {
    105             string s;
    106             cin >> s;
    107             for (int j = 0; j < m; j++)
    108                 if (s[j] == '*')
    109                     status[i][j] = 1;
    110         }
    111         for (int i = n - 1; i > -1; i--) {
    112             for (int j = 0; j < m; j++) {
    113                 if (status[i][j] == 0)
    114                     continue;
    115                 int len = 0;
    116                 while (j > len && j + len + 1 < m && i > len) {
    117                     if (status[i - len - 1][j - len - 1] == 0 || status[i - len - 1][j + len + 1] == 0)
    118                         break;
    119                     len++;
    120                 }
    121                 if (len >= k) {
    122                     for (int d = 0; d <= len; d++) {
    123                         status[i - d][j - d] = 2;
    124                         status[i - d][j + d] = 2;
    125                     }
    126                 }
    127             }
    128         }
    129         bool ok = true;
    130         for (int i = 0; i < n; i++)
    131             for (int j = 0; j < m; j++)
    132                 if (status[i][j] == 1)
    133                     ok = false;
    134 
    135         cout << (ok ? "YES" : "NO") << '\n';
    136     }
    137 }
    138 ```
    139 
    140 [1579D - Productive Meeting](/contest/1579/problem/D "Codeforces Round 744 (Div. 3)")
    141 
    142 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
    143 
    144 **Tutorial**
    145 
    146 Tutorial is loading...
    147 
    148 **Solution**
    149 
    150 ```
    151 #include <bits/stdc++.h>
    152 
    153 using namespace std;
    154 
    155 typedef pair<int, int> pii;
    156 
    157 int main() {
    158     int t;
    159     cin >> t;
    160     while (t--) {
    161         int n;
    162         cin >> n;
    163         auto cmp = [](pii const &x, pii const &y) {
    164             return x > y;
    165         };
    166         set<pii, decltype(cmp)> a(cmp);
    167         vector<pii> answer;
    168         for (int i = 0; i < n; i++) {
    169             int ai;
    170             cin >> ai;
    171             if (ai > 0)
    172                 a.emplace(ai, i + 1);
    173         }
    174         while (a.size() > 1) {
    175             auto p1 = *a.begin();
    176             a.erase(a.begin());
    177             auto p2 = *a.begin();
    178             a.erase(a.begin());
    179             answer.emplace_back(p1.second, p2.second);
    180             if (p1.first > 1) a.emplace(p1.first - 1, p1.second);
    181             if (p2.first > 1) a.emplace(p2.first - 1, p2.second);
    182         }
    183         cout << answer.size() << '\n';
    184         for (auto &p : answer) {
    185             cout << p.first << ' ' << p.second << '\n';
    186         }
    187     }
    188 }
    189 ```
    190 
    191 [1579E1 - Permutation Minimization by Deque](/contest/1579/problem/E1 "Codeforces Round 744 (Div. 3)")
    192 
    193 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    194 
    195 **Tutorial**
    196 
    197 Tutorial is loading...
    198 
    199 **Solution**
    200 
    201 ```
    202 #include <bits/stdc++.h>
    203 
    204 using namespace std;
    205 
    206 int main() {
    207     int t;
    208     cin >> t;
    209     while (t--) {
    210         int n, a;
    211         cin >> n;
    212         deque<int> d;
    213         for (int i = 0; i < n; i++) {
    214             cin >> a;
    215             if (d.empty() || a < d[0])
    216                 d.push_front(a);
    217             else
    218                 d.push_back(a);
    219         }
    220         for (int x : d)
    221             cout << x << ' ';
    222         cout << '\n';
    223     }
    224 }
    225 ```
    226 
    227 [1579E2 - Array Optimization by Deque](/contest/1579/problem/E2 "Codeforces Round 744 (Div. 3)")
    228 
    229 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
    230 
    231 **Tutorial**
    232 
    233 Tutorial is loading...
    234 
    235 **Solution**
    236 
    237 ```
    238 #include <bits/stdc++.h>
    239 #include <ext/pb_ds/assoc_container.hpp>
    240 
    241 using namespace std;
    242 using namespace __gnu_pbds;
    243 
    244 typedef pair<int, int> node;
    245 typedef tree<node, null_type, less<node>,
    246             rb_tree_tag, tree_order_statistics_node_update> ordered_set;
    247 
    248 int main() {
    249     int t;
    250     cin >> t;
    251     while (t--) {
    252         int n;
    253         cin >> n;
    254         ordered_set s;
    255         long long cnt = 0;
    256         for (int i = 0; i < n; i++) {
    257             int a;
    258             cin >> a;
    259             int less = s.order_of_key(node(a, 0)),
    260                     greater = i - s.order_of_key(node(a, n));
    261             cnt += min(less, greater);
    262             s.insert(node(a, i));
    263         }
    264         cout << cnt << '\n';
    265     }
    266 }
    267 ```
    268 
    269 [1579F - Array Stabilization (AND version)](/contest/1579/problem/F "Codeforces Round 744 (Div. 3)")
    270 
    271 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov")
    272 
    273 **Tutorial**
    274 
    275 Tutorial is loading...
    276 
    277 **Solution**
    278 
    279 ```
    280 #include <bits/stdc++.h>
    281 
    282 using namespace std;
    283 
    284 int main() {
    285     int t;
    286     cin >> t;
    287     while (t--) {
    288         int n, d;
    289         cin >> n >> d;
    290         vector<int> a(n);
    291         for (int i = 0; i < n; i++)
    292             cin >> a[i];
    293         vector<bool> used(n, false);
    294         bool fail = false;
    295         int res = 0;
    296         for (int i = 0; i < n; i++) {
    297             if (used[i])
    298                 continue;
    299             int cur = i, pref = 0, last = 0, iter = 0, ans = 0;
    300             do {
    301                 used[cur] = true;
    302                 if (a[cur] == 0) {
    303                     ans = max(ans, last);
    304                     last = 0;
    305                 } else {
    306                     last++;
    307                     if (iter == pref) {
    308                         pref++;
    309                     }
    310                 }
    311                 cur = (cur + d) % n;
    312                 iter++;
    313             } while (cur != i);
    314             if (iter != pref)
    315                 ans = max(ans, pref + last);
    316             else {
    317                 fail = true;
    318                 break;
    319             }
    320             res = max(res, ans);
    321         }
    322         if (fail)
    323             cout << "-1\n";
    324         else
    325             cout << res << '\n';
    326     }
    327 }
    328 ```
    329 
    330 [1579G - Minimal Coverage](/contest/1579/problem/G "Codeforces Round 744 (Div. 3)")
    331 
    332 Idea: [doreshnikov](/profile/doreshnikov "Candidate Master doreshnikov"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    333 
    334 **Tutorial**
    335 
    336 Tutorial is loading...
    337 
    338 **Solution**
    339 
    340 ```
    341 #include <bits/stdc++.h>
    342 
    343 using namespace std;
    344 
    345 const int INF = 1000000000;
    346 
    347 int main() {
    348     int t;
    349     cin >> t;
    350     while (t--) {
    351         int n;
    352         cin >> n;
    353         vector<int> a(n);
    354         int maxl = 0;
    355         for (int i = 0; i < n; i++) {
    356             cin >> a[i];
    357             maxl = max(maxl, a[i]);
    358         }
    359         vector<vector<int>> dp(n + 1, vector<int>(2 * maxl + 1, INF));
    360         dp[0][0] = 0;
    361         for (int i = 0; i < n; i++) {
    362             for (int left = 0; left <= 2 * maxl; left++) {
    363                 if (dp[i][left] == INF)
    364                     continue;
    365                 dp[i + 1][max(left - a[i], 0)] = min(dp[i + 1][max(left - a[i], 0)], dp[i][left] + a[i]);
    366                 if (left + a[i] < dp[i + 1].size()) {
    367                     dp[i + 1][left + a[i]] = min(dp[i + 1][left + a[i]], max(dp[i][left] - a[i], 0));
    368                 }
    369             }
    370         }
    371 
    372         int ans = 2 * maxl + 1;
    373         for (int left = 0; left <= 2 * maxl; left++)
    374             ans = min(ans, left + dp[n][left]);
    375         cout << ans << '\n';
    376     }
    377 }
    378 ```