codeforces-scrape

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

1506.md (7159B)


      1 Source: https://codeforces.com/blog/entry/89007
      2 
      3 [1506A - Strange Table](/contest/1506/problem/A "Codeforces Round 710 (Div. 3)")
      4 
      5 Problem author: [sodafago](/profile/sodafago "Specialist sodafago")
      6 
      7 **Editorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 using ll = long long;
     18 
     19 void solve() {
     20     ll n, m, x;
     21     cin >> n >> m >> x;
     22     x--;
     23     ll col = x / n;
     24     ll row = x % n;
     25     cout << row * m + col + 1 << "\n";
     26 }
     27 
     28 int main() {
     29     ios_base::sync_with_stdio(false);
     30     cin.tie(nullptr); cout.tie(nullptr);
     31     int n;
     32     cin >> n;
     33     while (n--) {
     34         solve();
     35     }
     36 }
     37 ```
     38 
     39 [1506B - Partial Replacement](/contest/1506/problem/B "Codeforces Round 710 (Div. 3)")
     40 
     41 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     42 
     43 **Editorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution**
     48 
     49 ```
     50 #include <bits/stdc++.h>
     51 using namespace std;
     52 
     53 void solve() {
     54   int n, k;
     55   cin >> n >> k;
     56   string s;
     57   cin >> s;
     58   int res = 1;
     59   int i = s.find_first_of('*');
     60   while (true) {
     61     int j = min(n - 1, i + k);
     62     for (; i < j && s[j] == '.'; j--) {}
     63     if (i == j) {
     64       break;
     65     }
     66     res++;
     67     i = j;
     68   }
     69   cout << res << "\n";
     70 }
     71 
     72 int main() {
     73   int tests;
     74   cin >> tests;
     75   while (tests-- > 0) {
     76     solve();
     77   }
     78   return 0;
     79 }
     80 ```
     81 
     82 [1506C - Double-ended Strings](/contest/1506/problem/C "Codeforces Round 710 (Div. 3)")
     83 
     84 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     85 
     86 **Editorial**
     87 
     88 Tutorial is loading...
     89 
     90 **Solution**
     91 
     92 ```
     93 #include <bits/stdc++.h>
     94 
     95 using namespace std;
     96 using ll = long long;
     97 
     98 void solve() {
     99     string a, b;
    100     cin >> a >> b;
    101     int n = a.size(), m = b.size();
    102     int ans = 0;
    103     for (int len = 1; len <= min(n, m); len++) {
    104         for (int i = 0; i + len <= n; i++) {
    105             for (int j = 0; j + len <= m; j++) {
    106                 if (a.substr(i, len) == b.substr(j, len)) {
    107                     ans = max(ans, len);
    108                 }
    109             }
    110         }
    111     }
    112     cout << a.size() + b.size() - 2 * ans << "\n";
    113 }
    114 
    115 int main() {
    116     ios_base::sync_with_stdio(false);
    117     cin.tie(nullptr); cout.tie(nullptr);
    118     int n;
    119     cin >> n;
    120     while (n--) {
    121         solve();
    122     }
    123 }
    124 ```
    125 
    126 [1506D - Epic Transformation](/contest/1506/problem/D "Codeforces Round 710 (Div. 3)")
    127 
    128 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    129 
    130 **Editorial**
    131 
    132 Tutorial is loading...
    133 
    134 **Solution**
    135 
    136 ```
    137 #include <bits/stdc++.h>
    138 
    139 using namespace std;
    140 using ll = long long;
    141 
    142 void solve() {
    143     priority_queue<pair<int, int>> q;
    144     int n;
    145     cin >> n;
    146     map<int, int> v;
    147     for (int i = 0; i < n; i++) {
    148         int x;
    149         cin >> x;
    150         v[x]++;
    151     }
    152     for (auto [x, y] : v) {
    153         q.push({y, x});
    154     }
    155     int sz = n;
    156     while (q.size() >= 2) {
    157         auto [cnt1, x1] = q.top();
    158         q.pop();
    159         auto [cnt2, x2] = q.top();
    160         q.pop();
    161         cnt1--;
    162         cnt2--;
    163         sz -= 2;
    164         if (cnt1) {
    165             q.push({cnt1, x1});
    166         }
    167         if (cnt2) {
    168             q.push({cnt2, x2});
    169         }
    170     }
    171     cout << sz << "\n";
    172 }
    173 
    174 int main() {
    175     ios_base::sync_with_stdio(false);
    176     cin.tie(nullptr); cout.tie(nullptr);
    177     int n;
    178     cin >> n;
    179     while (n--) {
    180         solve();
    181     }
    182 }
    183 ```
    184 
    185 [1506E - Restoring the Permutation](/contest/1506/problem/E "Codeforces Round 710 (Div. 3)")
    186 
    187 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    188 
    189 **Editorial**
    190 
    191 Tutorial is loading...
    192 
    193 **Solution**
    194 
    195 ```
    196 #include <bits/stdc++.h>
    197 using namespace std;
    198 
    199 void placeLeft(vector<int> &q, bool minimize) {
    200   set<int> left;
    201   for (int i = 1; i <= (int) q.size(); i++) {
    202     left.insert(i);
    203   }
    204   for (int i : q) {
    205     if (i != -1) {
    206       left.erase(i);
    207     }
    208   }
    209   int lastPlaced = -1;
    210   for (int &i : q) {
    211     if (i == -1) {
    212       set<int>::const_iterator it;
    213       if (minimize) {
    214         it = left.begin();
    215       } else {
    216         it = --left.lower_bound(lastPlaced);
    217       }
    218       i = *it;
    219       left.erase(it);
    220     } else {
    221       lastPlaced = i;
    222     }
    223   }
    224 }
    225 
    226 void solve() {
    227   int n;
    228   cin >> n;
    229   vector<int> q(n);
    230   for (int i = 0; i < n; i++) {
    231     cin >> q[i];
    232   }
    233 
    234   vector<int> res1(n, -1), res2(n, -1);
    235   for (int i = 0, lastPlaced = -1; i < n; lastPlaced = q[i], i++) {
    236     if (lastPlaced != q[i]) {
    237       res1[i] = q[i];
    238       res2[i] = q[i];
    239     }
    240   }
    241   placeLeft(res1, true);
    242   placeLeft(res2, false);
    243   for (int x : res1) {
    244     cout << x << " ";
    245   }
    246   cout << "\n";
    247   for (int x : res2) {
    248     cout << x << " ";
    249   }
    250   cout << "\n";
    251 }
    252 
    253 int main() {
    254   int tests;
    255   cin >> tests;
    256   while (tests-- > 0) {
    257     solve();
    258   }
    259   return 0;
    260 }
    261 ```
    262 
    263 [1506F - Triangular Paths](/contest/1506/problem/F "Codeforces Round 710 (Div. 3)")
    264 
    265 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [Stepavly](/profile/Stepavly "Master Stepavly"), [Supermagzzz](/profile/Supermagzzz "Master Supermagzzz")
    266 
    267 **Editorial**
    268 
    269 Tutorial is loading...
    270 
    271 **Solution**
    272 
    273 ```
    274 #include <bits/stdc++.h>
    275 using namespace std;
    276 
    277 bool isLeftArrow(int r, int c) {
    278   return (r + c) % 2 == 0;
    279 }
    280 
    281 bool isRightArrow(int r, int c) {
    282   return (r + c) % 2 == 1;
    283 }
    284 
    285 int calcDist(int r1, int c1, int r2, int c2) {
    286   if (r1 - c1 == r2 - c2) {
    287     return isRightArrow(r1, c1) ? 0 : r2 - r1;
    288   }
    289   r2 -= r1 - 1;
    290   c2 -= c1 - 1;
    291   if (isLeftArrow(r1, c1)) {
    292     return (r2 - c2) / 2;
    293   } else {
    294     return (r2 - c2 + 1) / 2;
    295   }
    296 }
    297 
    298 void solve() {
    299   int n;
    300   cin >> n;
    301   vector<int> r(n);
    302   vector<int> c(n);
    303   for (int i = 0; i < n; i++) {
    304     cin >> r[i];
    305   }
    306   for (int i = 0; i < n; i++) {
    307     cin >> c[i];
    308   }
    309   vector<pair<int, int>> pts;
    310   for (int i = 0; i < n; i++) {
    311     pts.emplace_back(r[i], c[i]);
    312   }
    313   sort(pts.begin(), pts.end());
    314   int curR = 1, curC = 1;
    315   int res = 0;
    316   for (auto[nextR, nextC] : pts) {
    317     res += calcDist(curR, curC, nextR, nextC);
    318     curR = nextR;
    319     curC = nextC;
    320   }
    321   cout << res << "\n";
    322 }
    323 
    324 int main() {
    325   int tests;
    326   cin >> tests;
    327   while (tests-- > 0) {
    328     solve();
    329   }
    330   return 0;
    331 }
    332 ```
    333 
    334 [1506G - Maximize the Remaining String](/contest/1506/problem/G "Codeforces Round 710 (Div. 3)")
    335 
    336 Problem author: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    337 
    338 **Editorial**
    339 
    340 Tutorial is loading...
    341 
    342 **Solution**
    343 
    344 ```
    345 #include <bits/stdc++.h>
    346 using namespace std;
    347 
    348 int distinct(string s) {
    349   sort(s.begin(), s.end());
    350   return unique(s.begin(), s.end()) - s.begin();
    351 }
    352 
    353 string filter(const string &s, char c) {
    354   string t;
    355   bool foundFirst = false;
    356   for (char a : s) {
    357     if (a != c && foundFirst) {
    358       t += a;
    359     } else if (a == c) {
    360       foundFirst = true;
    361     }
    362   }
    363   return t;
    364 }
    365 
    366 void solve() {
    367   string s;
    368   cin >> s;
    369   int m = distinct(s);
    370   unordered_set<char> used(s.begin(), s.end());
    371   string t;
    372   while (m > 0) {
    373     char maxC = -1;
    374     for (char c : used) {
    375       if (distinct(filter(s, c)) == m - 1) {
    376         maxC = max(maxC, c);
    377       }
    378     }
    379     t += maxC;
    380     s = filter(s, maxC);
    381     used.erase(maxC);
    382     m--;
    383   }
    384   cout << t << "\n";
    385 }
    386 
    387 int main() {
    388   int tests;
    389   cin >> tests;
    390   while (tests-- > 0) {
    391     solve();
    392   }
    393   return 0;
    394 }
    395 ```