codeforces-scrape

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

1822.md (10023B)


      1 Source: https://codeforces.com/blog/entry/115409
      2 
      3 [1822A - TubeTube Feed](/contest/1822/problem/A "Codeforces Round 867 (Div. 3)")
      4 
      5 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 def solve():
     15     n, t = map(int, input().split())
     16     a = [int(x) for x in input().split()]
     17     b = [int(x) for x in input().split()]
     18     bst = -2
     19     for i in range(n):
     20         if i + a[i] <= t and (bst == -2 or b[bst] < b[i]):
     21             bst = i
     22     print(bst + 1)
     23  
     24  
     25 t = int(input())
     26 for _ in range(t):
     27     solve()
     28 ```
     29 
     30 **Rate the problem**
     31 
     32 * Didn't solve
     33 * Good task
     34 * Average task
     35 * Bad task
     36 
     37 [1822B - Karina and Array](/contest/1822/problem/B "Codeforces Round 867 (Div. 3)")
     38 
     39 Idea: [playerr17](/profile/playerr17 "Expert playerr17"), prepared: [playerr17](/profile/playerr17 "Expert playerr17")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution**
     46 
     47 ```
     48 t = int(input())
     49  
     50 for testCase in range(t):
     51     n = int(input())
     52     a = list(map(int, input().split(' ')))
     53     a.sort()
     54     print(max(a[0] * a[1], a[-1] * a[-2]))
     55 ```
     56 
     57 **Rate the problem**
     58 
     59 * Didn't solve
     60 * Good task
     61 * Average task
     62 * Bad task
     63 
     64 [1822C - Bun Lover](/contest/1822/problem/C "Codeforces Round 867 (Div. 3)")
     65 
     66 Idea: [diskoteka](/profile/diskoteka "Candidate Master diskoteka"), prepared: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
     67 
     68 **Tutorial**
     69 
     70 Tutorial is loading...
     71 
     72 **Solution**
     73 
     74 ```
     75 #include <bits/stdc++.h>
     76 
     77 using namespace std;
     78 
     79 #define int long long
     80 
     81 int32_t main() {
     82     int q;
     83     cin >> q;
     84     while (q--) {
     85         int n;
     86         cin >> n;
     87         cout << ((n + 1) * n) + n + 2 << "\n";
     88     }
     89     return 0;
     90 }
     91 ```
     92 
     93 **Rate the problem**
     94 
     95 * Didn't solve
     96 * Good task
     97 * Average task
     98 * Bad task
     99 
    100 [1822D - Super-Permutation](/contest/1822/problem/D "Codeforces Round 867 (Div. 3)")
    101 
    102 Idea: [isosto](/profile/isosto "Candidate Master isosto"), [pavlekn](/profile/pavlekn "Master pavlekn"), prepared: [diskoteka](/profile/diskoteka "Candidate Master diskoteka")
    103 
    104 **Tutorial**
    105 
    106 Tutorial is loading...
    107 
    108 **Solution**
    109 
    110 ```
    111 #include <bits/stdc++.h>
    112 
    113 using namespace std;
    114 
    115 int main() {
    116     int q;
    117     cin >> q;
    118     while (q--) {
    119         int n;
    120         cin >> n;
    121         if (n == 1) {
    122             cout << "1\n";
    123             continue;
    124         }
    125         if (n % 2) {
    126             cout << "-1\n";
    127         } else {
    128             for (int i = 0; i < n; ++i) {
    129                 if (i % 2) {
    130                     cout << i << " ";
    131                 } else {
    132                     cout << n - i << " ";
    133                 }
    134             }
    135             cout << "\n";
    136         }
    137     }
    138     return 0;
    139 }
    140 ```
    141 
    142 **Rate the problem**
    143 
    144 * Didn't solve
    145 * Good task
    146 * Average task
    147 * Bad task
    148 
    149 [1822E - Making Anti-Palindromes](/contest/1822/problem/E "Codeforces Round 867 (Div. 3)")
    150 
    151 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), prepared: [pavlekn](/profile/pavlekn "Master pavlekn")
    152 
    153 **Tutorial**
    154 
    155 Tutorial is loading...
    156 
    157 **Solution**
    158 
    159 ```
    160 #include <bits/stdc++.h>
    161 
    162 using namespace std;
    163 
    164 void solve(int n, string & s) {
    165     if (n % 2 == 1) {
    166         cout << -1 << endl;
    167         return;
    168     }
    169     vector<int> cnt(26);
    170     for (int i = 0; i < n; ++i) {
    171         ++cnt[s[i] - 'a'];
    172     }
    173     for (int i = 0; i < 26; ++i) {
    174         if (cnt[i] * 2 > n) {
    175             cout << -1 << endl;
    176             return;
    177         }
    178     }
    179     int pairs = 0;
    180     vector<int> cnt_pairs(26);
    181     for (int i = 0; i * 2 < n; ++i) {
    182         if (s[i] == s[n - i - 1]) {
    183            ++pairs;
    184            ++cnt_pairs[s[i] - 'a'];
    185         }
    186     }
    187     for (int i = 0; i < 26; ++i) {
    188         if (cnt_pairs[i] * 2 > pairs) {
    189             cout << cnt_pairs[i] << endl;
    190             return;
    191         }
    192     }
    193     cout << (pairs + 1) / 2 << endl;
    194 }
    195 
    196 int32_t main() {
    197     int t;
    198     cin >> t;
    199     for (int _ = 0; _ < t; ++_) {
    200         int n;
    201         cin >> n;
    202         string s;
    203         cin >> s;
    204         solve(n, s);
    205     }
    206 }
    207 ```
    208 
    209 **Rate the problem**
    210 
    211 * Didn't solve
    212 * Good task
    213 * Average task
    214 * Bad task
    215 
    216 [1822F - Gardening Friends](/contest/1822/problem/F "Codeforces Round 867 (Div. 3)")
    217 
    218 Idea: [playerr17](/profile/playerr17 "Expert playerr17"), prepared: [playerr17](/profile/playerr17 "Expert playerr17")
    219 
    220 **Tutorial**
    221 
    222 Tutorial is loading...
    223 
    224 **Solution**
    225 
    226 ```
    227 #include<bits/stdc++.h>
    228 
    229 using namespace std;
    230 
    231 struct Value {
    232     int64_t value = 0;
    233     int vertex = 0;
    234 };
    235 
    236 vector<vector<int>> nei;
    237 vector<vector<int>> depth_vertex;
    238 vector<int> depth;
    239 vector<int> parent;
    240 
    241 void dfs(int v, int p = -1, int cnt = 0) {
    242     depth_vertex[cnt].push_back(v);
    243     depth[v] = cnt;
    244     parent[v] = p;
    245     for (int u : nei[v]) {
    246         if (u == p) continue;
    247         dfs(u, v, cnt + 1);
    248     }
    249 }
    250 
    251 void solve() {
    252     int n, root = 1;
    253     int64_t k_wei, cost;
    254     cin >> n >> k_wei >> cost;
    255 
    256     nei.clear();
    257     nei.resize(n + 1);
    258     depth_vertex.clear();
    259     depth_vertex.resize(n + 1);
    260     depth.clear();
    261     depth.resize(n + 1);
    262     parent.clear();
    263     parent.resize(n + 1);
    264 
    265     for (int _ = 0; _ < n - 1; ++_) {
    266         int u, v;
    267         cin >> u >> v;
    268         nei[u].push_back(v);
    269         nei[v].push_back(u);
    270     }
    271 
    272     dfs(root);
    273 
    274     vector<pair<Value, Value>> down(n + 1);
    275 
    276     for (int tin = n; tin >= 0; --tin) {
    277         for (int v : depth_vertex[tin]) {
    278             for (int u : nei[v]) {
    279                 if (u == parent[v]) continue;
    280                 if (down[u].first.value + 1 > down[v].first.value) {
    281                     down[v].first.value = down[u].first.value + 1;
    282                     down[v].first.vertex = u;
    283                 }
    284             }
    285             for (int u : nei[v]) {
    286                 if (u == parent[v] || u == down[v].first.vertex) continue;
    287                 if (down[u].first.value + 1 > down[v].second.value) {
    288                     down[v].second.value = down[u].first.value + 1;
    289                 }
    290             }
    291         }
    292     }
    293 
    294     vector<int64_t> up(n + 1, 0);
    295 
    296     for (int tin = 1; tin <= n; ++tin) {
    297         for (int v : depth_vertex[tin]) {
    298             int p = parent[v];
    299             up[v] = up[p] + 1;
    300             if (down[p].first.vertex == v) {
    301                 up[v] = max(up[v], down[p].second.value + 1);
    302             } else {
    303                 up[v] = max(up[v], down[p].first.value + 1);
    304             }
    305         }
    306     }
    307 
    308     int64_t ans = -1'000'000'000'000'000'002;
    309 
    310     for (int v = 1; v <= n; ++v) {
    311         ans = max(ans, k_wei * max(up[v], down[v].first.value) - cost * int64_t(depth[v]));
    312     }
    313 
    314     cout << ans << endl;
    315 
    316 }
    317 
    318 int main()
    319 {
    320     int t;
    321     cin >> t;
    322     for (int _ = 1; _ <= t; ++_) {
    323         solve();
    324     }
    325     return 0;
    326 }
    327 ```
    328 
    329 **Rate the problem**
    330 
    331 * Didn't solve
    332 * Good task
    333 * Average task
    334 * Bad task
    335 
    336 [1822G1 - Magic Triples (Easy Version)](/contest/1822/problem/G1 "Codeforces Round 867 (Div. 3)")
    337 
    338 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), prepared: [pavlekn](/profile/pavlekn "Master pavlekn")
    339 
    340 **Tutorial**
    341 
    342 Tutorial is loading...
    343 
    344 **Solution**
    345 
    346 ```
    347 #include <bits/stdc++.h>
    348 
    349 using namespace std;
    350 
    351 #define int long long
    352 
    353 const int MAX_VAL = 1e6;
    354 
    355 int cnt[MAX_VAL + 1];
    356 
    357 int32_t main() {
    358     int t;
    359     cin >> t;
    360     for (int _ = 0; _ < t; ++_) {
    361         int n;
    362         cin >> n;
    363         vector<int> a(n);
    364         for (int i = 0; i < n; ++i) {
    365             cin >> a[i];
    366             ++cnt[a[i]];
    367         }
    368         int ans = 0;
    369         for (int i = 0; i < n; ++i) {
    370             ans += (cnt[a[i]] - 1) * (cnt[a[i]] - 2);
    371             for (int b = 2; a[i] * b * b <= MAX_VAL; ++b) {
    372                 ans += cnt[a[i] * b] * cnt[a[i] * b * b];
    373             }
    374         }
    375         cout << ans << "\n";
    376         for (int i = 0; i < n; ++i) {
    377             --cnt[a[i]];
    378         }
    379     }
    380     return 0;
    381 }
    382 ```
    383 
    384 **Rate the problem**
    385 
    386 * Didn't solve
    387 * Good task
    388 * Average task
    389 * Bad task
    390 
    391 [1822G2 - Magic Triples (Hard Version)](/contest/1822/problem/G2 "Codeforces Round 867 (Div. 3)")
    392 
    393 Idea: [pavlekn](/profile/pavlekn "Master pavlekn"), prepared: [pavlekn](/profile/pavlekn "Master pavlekn")
    394 
    395 **Tutorial**
    396 
    397 Tutorial is loading...
    398 
    399 **Solution**
    400 
    401 ```
    402 #include <bits/stdc++.h>
    403 
    404 using namespace std;
    405 
    406 typedef long long ll;
    407 
    408 const int K = 1e6;
    409 const int MAX_VAL = 1e9;
    410 
    411 int32_t main() {
    412     int t;
    413     scanf("%d", &t);
    414     for (int _ = 0; _ < t; ++_) {
    415         int n;
    416         scanf("%d", &n);
    417         vector<int> a(n);
    418         map<int, int> cnt;
    419         for (int i = 0; i < n; ++i) {
    420             scanf("%d", &a[i]);
    421             ++cnt[a[i]];
    422         }
    423         ll ans = 0;
    424         for (int i = 0; i < n; ++i) {
    425             ans += (ll)(cnt[a[i]] - 1) * (cnt[a[i]] - 2);
    426         }
    427         for (auto el : cnt) {
    428             int num = el.first;
    429             int val = el.second;
    430             if (num > K) {
    431                 for (int b = 2; b * num <= MAX_VAL; ++b) {
    432                     if (num % b == 0 && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) {
    433                         ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val;
    434                     }
    435                 }
    436             } else {
    437                 for (int b = 2; b * b <= num; ++b) {
    438                     if (num % b == 0) {
    439                         if ((ll)num * b <= (ll)MAX_VAL && cnt.find(num / b) != cnt.end() && cnt.find(num * b) != cnt.end()) {
    440                             ans += (ll)(cnt[num / b]) * (cnt[num * b]) * val;
    441                         }
    442                         if (b * b != num) {
    443                             if ((ll)num * num / b <= (ll)MAX_VAL && cnt.find(b) != cnt.end() && cnt.find(num / b * num) != cnt.end()) {
    444                                 ans += (ll)(cnt[b]) * (cnt[num / b * num]) * val;
    445                             }
    446                         }
    447                     }
    448                 }
    449                 if (num > 1 && (ll)num * num <= (ll)MAX_VAL && cnt.find(1) != cnt.end() && cnt.find(num * num) != cnt.end()) {
    450                     ans += (ll)(cnt[1]) * (cnt[num * num]) * val;
    451                 }
    452             }
    453         }
    454         printf("%lld\n", ans);
    455     }
    456     return 0;
    457 }
    458 ```
    459 
    460 **Rate the problem**
    461 
    462 * Didn't solve
    463 * Good task
    464 * Average task
    465 * Bad task