codeforces-scrape

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

1921.md (8465B)


      1 Source: https://codeforces.com/blog/entry/124757
      2 
      3 [1921A - Square](/contest/1921/problem/A "Codeforces Round 920 (Div. 3)")
      4 
      5 Idea: [goncharovmike](/profile/goncharovmike "Candidate Master goncharovmike"), prepared: [pashka](/profile/pashka "International Grandmaster pashka")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 t = int(input())
     15 for _ in range(t):
     16     a = [[int(x) for x in input().split()] for i in range(4)]
     17     x = [p[0] for p in a]
     18     dx = max(x) - min(x)
     19     print(dx * dx)
     20 ```
     21 
     22 [1921B - Arranging Cats](/contest/1921/problem/B "Codeforces Round 920 (Div. 3)")
     23 
     24 Idea: [pashka](/profile/pashka "International Grandmaster pashka"), prepared: [ikrpprppp](/profile/ikrpprppp "Master ikrpprppp")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution**
     31 
     32 ```
     33 t = int(input())
     34 
     35 for _ in range(t):
     36     n = int(input())
     37     start = [int(x) for x in input()]
     38     finish = [int(x) for x in input()]
     39     pairs = list(zip(start, finish))
     40     add_amnt = sum(int(a < b) for a, b in pairs)
     41     rmv_amnt = sum(int(a > b) for a, b in pairs)
     42     print(max(add_amnt, rmv_amnt))
     43 ```
     44 
     45 [1921C - Sending Messages](/contest/1921/problem/C "Codeforces Round 920 (Div. 3)")
     46 
     47 Idea: [step_by_step](/profile/step_by_step "International Grandmaster step_by_step"), prepared: [step_by_step](/profile/step_by_step "International Grandmaster step_by_step"), [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
     48 
     49 **Tutorial**
     50 
     51 Tutorial is loading...
     52 
     53 **Solution**
     54 
     55 ```
     56 t = int(input())
     57 for _ in range(t):
     58     n, f, a, b = map(int, input().split())
     59     m = [0] + [int(x) for x in input().split()]
     60     for i in range(1, n + 1):
     61         f -= min(a * (m[i] - m[i - 1]), b)
     62     print('YES' if f > 0 else 'NO')
     63 ```
     64 
     65 [1921D - Very Different Array](/contest/1921/problem/D "Codeforces Round 920 (Div. 3)")
     66 
     67 Idea: [Vitaly239239](/profile/Vitaly239239 "Expert Vitaly239239"), prepared: [pashka](/profile/pashka "International Grandmaster pashka")
     68 
     69 **Tutorial**
     70 
     71 Tutorial is loading...
     72 
     73 **Solution**
     74 
     75 ```
     76 #include <bits/stdc++.h>
     77 using namespace std;
     78 
     79 struct test {
     80    void solve() {
     81         int n, m;
     82         cin >> n >> m;
     83         vector<int> a(n);
     84         for (int i = 0; i < n; i++) cin >> a[i];
     85         vector<int> b(m);
     86         for (int i = 0; i < m; i++) cin >> b[i];
     87         sort(a.begin(), a.end());
     88         sort(b.rbegin(), b.rend());
     89         vector<int> c(n);
     90         long long s = 0;
     91         for (int i = 0; i < n; i++) {
     92             c[i] = b[m &mdash; n + i];
     93             s += abs(c[i] &mdash; a[i]);
     94         }
     95         long long res = 0;
     96         for (int k = 0; k <= n; k++) {
     97             res = max(res, s);
     98             if (k < n) {
     99                 s -= abs(c[k] &mdash; a[k]);
    100                 c[k] = b[k];
    101                 s += abs(c[k] &mdash; a[k]);
    102             }
    103         }
    104         cout << res << "\n";
    105     }
    106 };
    107 
    108 int main() {
    109     ios::sync_with_stdio(false);
    110     int n;
    111     cin >> n;
    112     for (int i = 0; i < n; i++) {
    113         test().solve();
    114     }
    115     return 0;
    116 }
    117 ```
    118 
    119 [1921E - Eat the Chip](/contest/1921/problem/E "Codeforces Round 920 (Div. 3)")
    120 
    121 Idea: [ikrpprppp](/profile/ikrpprppp "Master ikrpprppp"), prepared: [ikrpprppp](/profile/ikrpprppp "Master ikrpprppp")
    122 
    123 **Tutorial**
    124 
    125 Tutorial is loading...
    126 
    127 **Solution**
    128 
    129 ```
    130 def solve():
    131     h, w, xA, yA, xB, yB = map(int, input().split())
    132 
    133     if (xA - xB) % 2 == 0:
    134         winner = "Bob"
    135         if xA >= xB:
    136             win = False
    137         elif yA == yB:
    138             win = True
    139         else:
    140             if yA < yB:
    141                 n_turns = yB - 1
    142             else:
    143                 n_turns = w - yB
    144             win = xB - 2 * n_turns >= xA
    145 
    146     else:
    147         winner = "Alice"
    148 
    149         xA += 1
    150         yA += 0 if yB - yA == 0 else 1 if yB - yA > 0 else -1
    151 
    152         if xA > xB:
    153             win = False
    154         elif yA == yB:
    155             win = True
    156         else:
    157             if yA < yB:
    158                 n_turns = w - yA
    159             else:
    160                 n_turns = yA - 1
    161             win = xB - 2 * n_turns >= xA
    162 
    163     print(winner if win else "Draw")
    164 
    165 t = int(input())
    166 
    167 for _ in range(t):
    168     solve()
    169 ```
    170 
    171 [1921F - Sum of Progression](/contest/1921/problem/F "Codeforces Round 920 (Div. 3)")
    172 
    173 Idea: [Vitaly239239](/profile/Vitaly239239 "Expert Vitaly239239"), prepared: [Vitaly239239](/profile/Vitaly239239 "Expert Vitaly239239")
    174 
    175 **Tutorial**
    176 
    177 Tutorial is loading...
    178 
    179 **Solution**
    180 
    181 ```
    182 #include <bits/stdc++.h>
    183 
    184 using namespace std;
    185 
    186 long long precalc[322][200322];
    187 long long precalci[322][200322];
    188 
    189 void solve() {
    190     int n, q;
    191     cin >> n >> q;
    192     vector<long long> a(n);
    193     int pivot = 1;
    194     while (pivot * pivot < n) {
    195         pivot++;
    196     }
    197     for (int i = 0; i < n; i++) {
    198         cin >> a[i];
    199     }
    200     for (int i = 0; i < pivot; i++) {
    201         for (int j = 0; j <= i; j++) {
    202             precalc[i][j] = 0LL;
    203             precalci[i][j] = 0LL;
    204         }
    205         for (int j = 0; j < n; j++) {
    206             precalci[i][j + i + 1] = precalci[i][j] + a[j] * (j / (i + 1) + 1);
    207             precalc[i][j + i + 1] = precalc[i][j] + a[j];
    208         }
    209     }
    210     while (q--) {
    211         int s, d;
    212         long long k;
    213         long long ans = 0;
    214         cin >> s >> d >> k;
    215         s--;
    216         if (d > pivot) {
    217             for (int i = s; i <= s + (k - 1) * d; i += d) {
    218                 ans += a[i] * ((i - s) / d + 1);
    219             }
    220             cout << ans << " ";
    221             continue;
    222         }
    223         long long last = s + d * k - d;
    224         int first = s;
    225         cout << precalci[d - 1][last + d] - precalci[d - 1][first] -
    226                 (precalc[d - 1][last + d] - precalc[d - 1][first]) * (first / d) << ' ';
    227     }
    228 }
    229 
    230 int main() {
    231     ios_base::sync_with_stdio(false);
    232     cin.tie(nullptr);
    233     cout.tie(nullptr);
    234     int tests;
    235     cin >> tests;
    236     while (tests--) {
    237         solve();
    238         if (tests) cout << "\n";
    239     }
    240     return 0;
    241 }
    242 ```
    243 
    244 [1921G - Mischievous Shooter](/contest/1921/problem/G "Codeforces Round 920 (Div. 3)")
    245 
    246 Idea: [Vitaly239239](/profile/Vitaly239239 "Expert Vitaly239239"), prepared: [goncharovmike](/profile/goncharovmike "Candidate Master goncharovmike")
    247 
    248 **Tutorial**
    249 
    250 Tutorial is loading...
    251 
    252 **Solution**
    253 
    254 ```
    255 //ciao_chill
    256 #include<bits/stdc++.h>
    257 using namespace std;
    258 #define int long long
    259 
    260 int n, m, k;
    261 vector<vector<int>> a;
    262 
    263 bool prov(int i, int j) {
    264     return 0 <= i && i < n && 0 <= j && j < m;
    265 }
    266 
    267 int ans() {
    268     int cnt = 0;
    269     int dp[n][m];
    270     int pref[n][m];
    271     int pref_up[n][m];
    272     for (int i = 0; i < n; i++) {
    273         for (int j = 0; j < m; j++) {
    274             pref_up[i][j] = a[i][j];
    275             if (prov(i - 1, j))
    276                 pref_up[i][j] += pref_up[i - 1][j];
    277         }
    278     }
    279 
    280     for (int i = 0; i < n; i++) {
    281         for (int j = m - 1; j >= 0; j--) {
    282             pref[i][j] = a[i][j];
    283             if (prov(i - 1, j + 1))
    284                 pref[i][j] += pref[i - 1][j + 1];
    285         }
    286     }
    287 
    288     for (int i = 0; i < n; i++) {
    289         for (int j = 0; j < m; j++) {
    290             dp[i][j] = pref_up[i][j];
    291             if (prov(i - k, j))
    292                 dp[i][j] -= pref_up[i - k][j];
    293             if (prov(i, j - 1))
    294                 dp[i][j] += dp[i][j - 1];
    295             if (j < k) {
    296                 int i1 = j - k + i;
    297                 if (i1 >= 0)
    298                     dp[i][j] -= pref[i1][0];
    299             }
    300             else
    301                 dp[i][j] -= pref[i][j - k];
    302             if (prov(i - k, j))
    303                 dp[i][j] += pref[i - k][j];
    304             cnt = max(cnt, dp[i][j]);
    305         }
    306     }
    307 
    308     return cnt;
    309 }
    310 
    311 void solve() {
    312     cin >> n >> m >> k;
    313     k++;
    314     char c;
    315     bool st[n][m];
    316     a.resize(n);
    317     for (int i = 0; i < n; i++) {
    318         a[i].resize(m);
    319     }
    320     for (int i = 0; i < n; i++) {
    321         for (int j = 0; j < m; j++)
    322         {
    323             cin >> c;
    324             st[i][j] = (c == '#');
    325             a[i][j] = st[i][j];
    326         }
    327     }
    328 
    329     int mx = ans();
    330     for (int i = 0; i < n; i++) {
    331         for (int j = 0; j < m; j++) {
    332             a[i][j] = st[n - i - 1][j];
    333         }
    334     }
    335     mx = max(mx, ans());
    336     for (int i = 0; i < n; i++) {
    337         for (int j = 0; j < m; j++) {
    338             a[i][j] = st[i][m - j - 1];
    339         }
    340     }
    341     mx = max(mx, ans());
    342     for (int i = 0; i < n; i++) {
    343         for (int j = 0; j < m; j++) {
    344             a[i][j] = st[n - i - 1][m - j - 1];
    345         }
    346     }
    347     mx = max(mx, ans());
    348 
    349     cout << mx << '\n';
    350 
    351 }
    352 
    353 signed main() {
    354     cin.tie(nullptr);
    355     cout.tie(nullptr);
    356     ios_base::sync_with_stdio(false);
    357 
    358     int tt;
    359     cin >> tt;
    360     while (tt--)
    361         solve();
    362 
    363     return 0;
    364 }
    365 ```