codeforces-scrape

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

1955.md (11437B)


      1 Source: https://codeforces.com/blog/entry/128243
      2 
      3 [1955A - Yogurt Sale](/contest/1955/problem/A "Codeforces Round 938 (Div. 3)")
      4 
      5 Idea: [mainyutin](/profile/mainyutin "Expert mainyutin"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15  
     16 using ll = signed long long int;
     17  
     18 using namespace std;
     19  
     20 void solve() {
     21     ll n, a, b;
     22     cin >> n >> a >> b;
     23     ll ans = n * a;
     24     if (b < 2 * a) {
     25         ans = (n / 2) * b + (n % 2) * a;
     26     }
     27     cout << ans << '\n';
     28 }
     29  
     30 int main() {
     31     int t;
     32     cin >> t;
     33     while (t--) {
     34         solve();
     35     }
     36 }
     37 ```
     38 
     39 [1955B - Progressive Square](/contest/1955/problem/B "Codeforces Round 938 (Div. 3)")
     40 
     41 Idea: [ssor96](/profile/ssor96 "Master ssor96"), [mainyutin](/profile/mainyutin "Expert mainyutin"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     42 
     43 **Tutorial**
     44 
     45 Tutorial is loading...
     46 
     47 **Solution**
     48 
     49 ```
     50 #include <bits/stdc++.h>
     51  
     52 using namespace std;
     53  
     54 #define all(x) (x).begin(), (x).end()
     55  
     56 using ll = signed long long int;
     57 using pii = pair<int, int>;
     58 using pll = pair<ll, ll>;
     59 using vi = vector<int>;
     60 using vl = vector<ll>;
     61  
     62 void solve() {
     63     int n;
     64     ll c, d;
     65     cin >> n >> c >> d;
     66     vl a(n * n);
     67     for (int i = 0; i < n * n; ++i) {
     68         cin >> a[i];
     69     }
     70     sort(all(a));
     71     vl b(n * n);
     72     b[0] = a[0];
     73     for (int i = 1; i < n; ++i) {
     74         b[i] = b[i - 1] + c;
     75     }
     76     for (int i = 1; i < n; ++i) {
     77         for (int j = 0; j < n; ++j) {
     78             b[i * n + j] = b[(i - 1) * n + j] + d;
     79         }
     80     }
     81     sort(all(b));
     82     cout << (a == b ? "YEs" : "nO") << '\n';
     83 }
     84  
     85 int main() {
     86     int t;
     87     cin >> t;
     88     while (t--) {
     89         solve();
     90     }
     91 }
     92 ```
     93 
     94 [1955C - Inhabitant of the Deep Sea](/contest/1955/problem/C "Codeforces Round 938 (Div. 3)")
     95 
     96 Idea: [ssor96](/profile/ssor96 "Master ssor96"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin")
     97 
     98 **Tutorial**
     99 
    100 Tutorial is loading...
    101 
    102 **Solution**
    103 
    104 ```
    105 #include <bits/stdc++.h>
    106 
    107 using namespace std;
    108 
    109 #define all(x) (x).begin(), (x).end()
    110 
    111 using ll = signed long long int;
    112 
    113 void solve() {
    114     int n;
    115     ll k;
    116     cin >> n >> k;
    117     deque<ll> dq(n);
    118     for (int i = 0; i < n; ++i) {
    119         cin >> dq[i];
    120     }
    121     while (dq.size() > 1 && k) {
    122         ll mn = min(dq.front(), dq.back());
    123         if (k < 2 * mn) {
    124             dq.front() -= k / 2 + k % 2;
    125             dq.back() -= k / 2;
    126             k = 0;
    127         } else {
    128             dq.front() -= mn;
    129             dq.back() -= mn;
    130             k -= 2 * mn;
    131         }
    132         if (dq.front() == 0) {
    133             dq.pop_front();
    134         }
    135         if (dq.back() == 0) {
    136             dq.pop_back();
    137         }
    138     }
    139     int ans = n - dq.size();
    140     cout << ans + (dq.size() && dq.front() <= k) << '\n';
    141 }
    142 
    143 int main() {
    144     int t;
    145     cin >> t;
    146     while (t--) {
    147         solve();
    148     }
    149 }
    150 ```
    151 
    152 [1955D - Inaccurate Subsequence Search](/contest/1955/problem/D "Codeforces Round 938 (Div. 3)")
    153 
    154 Idea: [mainyutin](/profile/mainyutin "Expert mainyutin"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin")
    155 
    156 **Tutorial**
    157 
    158 Tutorial is loading...
    159 
    160 **Solution**
    161 
    162 ```
    163 #include <bits/stdc++.h>
    164  
    165 using ll = signed long long int;
    166  
    167 #define all(x) (x).begin(), (x).end()
    168  
    169 using pii = std::pair<int, int>;
    170 using pll = std::pair<ll, ll>;
    171  
    172 using namespace std;
    173  
    174 void solve() {
    175     int n, m;
    176     size_t k;
    177     cin >> n >> m >> k;
    178     vector<int> a(n);
    179     for (int i = 0; i < n; ++i) {
    180         cin >> a[i];
    181     }
    182     multiset<int> todo, done, extra;
    183     for (int j = 0; j < m; ++j) {
    184         int b;
    185         cin >> b;
    186         todo.insert(b);
    187     }
    188     for (int j = 0; j < m; ++j) {
    189         if (todo.find(a[j]) != todo.end()) {
    190             todo.erase(todo.find(a[j]));
    191             done.insert(a[j]);
    192         } else {
    193             extra.insert(a[j]);
    194         }
    195     }
    196     int ans = (done.size() >= k);
    197     for (int r = m; r < n; ++r) {
    198         int old = a[r - m];
    199         if (extra.find(old) != extra.end()) {
    200             extra.erase(extra.find(old));
    201         } else if (done.find(old) != done.end()) {
    202             done.erase(done.find(old));
    203             todo.insert(old);
    204         }
    205         if (todo.find(a[r]) != todo.end()) {
    206             todo.erase(todo.find(a[r]));
    207             done.insert(a[r]);
    208         } else {
    209             extra.insert(a[r]);
    210         }
    211         ans += (done.size() >= k);
    212     }
    213     cout << ans << '\n';
    214 }
    215  
    216 int main() {
    217     int t;
    218     cin >> t;
    219     while (t--) {
    220         solve();
    221     }
    222 }
    223 ```
    224 
    225 [1955E - Long Inversions](/contest/1955/problem/E "Codeforces Round 938 (Div. 3)")
    226 
    227 Idea: [ssor96](/profile/ssor96 "Master ssor96"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    228 
    229 **Tutorial**
    230 
    231 Tutorial is loading...
    232 
    233 **Solution**
    234 
    235 ```
    236 #include <bits/stdc++.h>
    237  
    238 using ll = signed long long int;
    239  
    240 #define all(x) (x).begin(), (x).end()
    241  
    242 using pii = std::array<int, 2>;
    243 using pll = std::array<ll, 2>;
    244 using vi = std::vector<int>;
    245 using vl = std::vector<ll>;
    246  
    247 using namespace std;
    248  
    249 void solve() {
    250     int n;
    251     string s;
    252     cin >> n >> s;
    253     for (int k = n; k > 0; --k) {
    254         vector<char> t(n), end(n + 1);
    255         for (int i = 0; i < n; ++i) {
    256             t[i] = s[i] - '0';
    257         }
    258         int cnt = 0;
    259         for (int i = 0; i < n; ++i) {
    260             cnt -= end[i];
    261             t[i] ^= (cnt & 1);
    262             if (t[i] == 0) {
    263                 if (i + k <= n) {
    264                     ++end[i + k];
    265                     ++cnt;
    266                     t[i] = 1;
    267                 } else {
    268                     break;
    269                 }
    270             }
    271         }
    272         if (*min_element(all(t)) == 1) {
    273             cout << k << '\n';
    274             return;
    275         }
    276     }
    277     assert(false);
    278 }
    279  
    280 int main() {
    281     int t;
    282     cin >> t;
    283     while (t--) {
    284         solve();
    285     }
    286 }
    287 ```
    288 
    289 [1955F - Unfair Game](/contest/1955/problem/F "Codeforces Round 938 (Div. 3)")
    290 
    291 Idea: [mainyutin](/profile/mainyutin "Expert mainyutin"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin")
    292 
    293 **Tutorial**
    294 
    295 Tutorial is loading...
    296 
    297 **Solution**
    298 
    299 ```
    300 #include <bits/stdc++.h>
    301  
    302 using namespace std;
    303  
    304 const int N = 201;
    305  
    306 int dp[N][N][N];
    307  
    308 void precalc() {
    309     dp[0][0][0] = 0;
    310     for (int i = 0; i < N; ++i) {
    311         for (int j = 0; j < N; ++j) {
    312             for (int k = 0; k < N; ++k) {
    313                 int prev = 0;
    314                 if (i) prev = max(prev, dp[i - 1][j][k]);
    315                 if (j) prev = max(prev, dp[i][j - 1][k]);
    316                 if (k) prev = max(prev, dp[i][j][k - 1]);
    317                 dp[i][j][k] = prev;
    318                 int xr = ((i & 1) * 1) ^ ((j & 1) * 2) ^ ((k & 1) * 3);
    319                 if (xr == 0 && (i || j || k)) {
    320                     ++dp[i][j][k];
    321                 }
    322             }
    323         }
    324     }
    325 }
    326  
    327 void solve() {
    328     vector<int> cnt(4);
    329     for (int i = 0; i < 4; ++i) {
    330         cin >> cnt[i];
    331     }
    332     cout << dp[cnt[0]][cnt[1]][cnt[2]] + cnt[3] / 2 << '\n';
    333 }
    334  
    335 int main() {
    336     precalc();
    337     int t;
    338     cin >> t;
    339     while (t--) {
    340         solve();
    341     }
    342 }
    343 ```
    344 
    345 [1955G - GCD on a grid](/contest/1955/problem/G "Codeforces Round 938 (Div. 3)")
    346 
    347 Idea: [ZergTricky](/profile/ZergTricky "Master ZergTricky"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin")
    348 
    349 **Tutorial**
    350 
    351 Tutorial is loading...
    352 
    353 **Solution**
    354 
    355 ```
    356 #include <bits/stdc++.h>
    357  
    358 using ll = signed long long int;
    359  
    360 #define all(x) (x).begin(), (x).end()
    361  
    362 using pii = std::pair<int, int>;
    363 using pll = std::pair<ll, ll>;
    364  
    365 using namespace std;
    366  
    367 void solve() {
    368     int n, m;
    369     cin >> n >> m;
    370     vector<vector<int> > a(n, vector<int>(m));
    371     for (int i = 0; i < n; ++i) {
    372         for (int j = 0; j < m; ++j) {
    373             cin >> a[i][j];
    374         }
    375     }
    376     int ans = 1, g = gcd(a[0][0], a[n - 1][m - 1]);
    377     vector<vector<char> > dp(n, vector<char>(m));
    378     for (int x = 1; x * x <= g; ++x) {
    379         if (g % x > 0) {
    380             continue;
    381         }
    382         vector<int> cand = {x, g / x};
    383         for (int el : cand) {
    384             for (int i = 0; i < n; ++i) {
    385                 dp[i].assign(m, 0);
    386             }
    387             dp[0][0] = 1;
    388             for (int i = 0; i < n; ++i) {
    389                 for (int j = 0; j < m; ++j) {
    390                     if (a[i][j] % el > 0) {
    391                         continue;
    392                     }
    393                     if (!dp[i][j] && i) {
    394                         dp[i][j] = (dp[i - 1][j] == 1 ? 1 : 0);
    395                     }
    396                     if (!dp[i][j] && j) {
    397                         dp[i][j] = (dp[i][j - 1] == 1 ? 1 : 0);
    398                     }
    399                 }
    400             }
    401             if (dp[n - 1][m - 1]) {
    402                 ans = max(ans, el);
    403             }
    404         }
    405     }
    406     cout << ans << '\n';
    407 }
    408  
    409 int main() {
    410     int t;
    411     cin >> t;
    412     while (t--) {
    413         solve();
    414     }
    415 }
    416 ```
    417 
    418 [1955H - The Most Reckless Defense](/contest/1955/problem/H "Codeforces Round 938 (Div. 3)")
    419 
    420 Idea: [VManoshin](/profile/VManoshin "Expert VManoshin"), prepared: [mainyutin](/profile/mainyutin "Expert mainyutin")
    421 
    422 **Tutorial**
    423 
    424 Tutorial is loading...
    425 
    426 **Solution**
    427 
    428 ```
    429 #include <bits/stdc++.h>
    430  
    431 using ll = signed long long int;
    432  
    433 #define all(x) (x).begin(), (x).end()
    434  
    435 using pii = std::pair<int, int>;
    436 using pll = std::pair<ll, ll>;
    437  
    438 using namespace std;
    439  
    440 const int R = 12, INF = 2e9;
    441  
    442 bool check(int x, int n) { return (0 <= x && x < n); }
    443  
    444 void solve() {
    445     int n, m, k;
    446     cin >> n >> m >> k;
    447     vector<string> gr(n);
    448     for (int i = 0; i < n; ++i) {
    449         cin >> gr[i];
    450     }
    451     vector<pii> cord(k);
    452     vector<int> p(k);
    453     for (int i = 0; i < k; ++i) {
    454         cin >> cord[i].first >> cord[i].second >> p[i];
    455         --cord[i].first;
    456         --cord[i].second;
    457     }
    458     vector<vector<int> > cover(k, vector<int>(R + 1));
    459     for (int i = 0; i < k; ++i) {
    460         int x = cord[i].first;
    461         int y = cord[i].second;
    462         for (int r = 1; r <= R; ++r) {
    463             for (int dx = -r; dx <= r; ++dx) {
    464                 for (int dy = -r; dy <= r; ++dy) {
    465                     int nx = x + dx;
    466                     int ny = y + dy;
    467                     if (!check(nx, n) || !check(ny, m)) {
    468                         continue;
    469                     }
    470                     if ((x - nx) * (x - nx) + (y - ny) * (y - ny) <= r * r) {
    471                         cover[i][r] += (gr[nx][ny] == '#');
    472                     }
    473                 }
    474             }
    475         }
    476     }
    477     vector<vector<int> > dp(k + 1, vector<int>(1 << R, -INF));
    478     dp[0][0] = 0;
    479     for (int i = 1; i <= k; ++i) {
    480         for (int mask = 0; mask < (1 << R); ++mask) {
    481             dp[i][mask] = dp[i - 1][mask];
    482             for (int r = 1; r <= R; ++r) {
    483                 int j = r - 1;
    484                 if (!(mask & (1 << j))) {
    485                     continue;
    486                 }
    487                 dp[i][mask] = max(dp[i][mask], dp[i - 1][mask ^ (1 << j)] +
    488                                                    p[i - 1] * cover[i - 1][r]);
    489             }
    490         }
    491     }
    492     int ans = 0;
    493     for (int mask = 0; mask < (1 << R); ++mask) {
    494         int hp = 0, mlt = 3;
    495         for (int j = 0; j < R; ++j) {
    496             if (mask & (1 << j)) {
    497                 hp += mlt;
    498             }
    499             mlt *= 3;
    500         }
    501         for (int i = 0; i <= k; ++i) {
    502             ans = max(ans, dp[i][mask] - hp);
    503         }
    504     }
    505     cout << ans << '\n';
    506 }
    507  
    508 int main() {
    509     int t;
    510     cin >> t;
    511     while (t--) {
    512         solve();
    513     }
    514 }
    515 ```