codeforces-scrape

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

2050.md (6629B)


      1 Source: https://codeforces.com/blog/entry/137018
      2 
      3 [2050A - Line Breaks](/contest/2050/problem/A "Codeforces Round 991 (Div. 3)")
      4 
      5 Идея: [kbats183](/profile/kbats183 "Specialist kbats183")
      6 
      7 **Решение**
      8 
      9 Tutorial is loading...
     10 
     11 **Код**
     12 
     13 ```
     14 def solve():
     15     n, m = [int(i) for i in input().split()]
     16 
     17     ans = 0
     18     for i in range(n):
     19         l = input()
     20         if len(l) <= m:
     21             m -= len(l)
     22             ans += 1
     23         else:
     24             for i in range(i + 1, n):
     25                 input()
     26             break
     27 
     28     print(ans)
     29 
     30 t = int(input())
     31 for i in range(t):
     32     solve()
     33 ```
     34 
     35 [2050B - Transfusion](/contest/2050/problem/B "Codeforces Round 991 (Div. 3)")
     36 
     37 Идея: [AVdovin](/profile/AVdovin "Expert AVdovin")
     38 
     39 **Решение**
     40 
     41 Tutorial is loading...
     42 
     43 **Код**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47 
     48 using namespace std;
     49 
     50 void solve() {
     51     int n; cin >> n;
     52     vector<int> a(n);
     53     for (int &x : a) cin >> x;
     54     
     55     long long ods = 0, evs = 0;
     56     for (int i = 0; i < n; i++) {
     57         if (i & 1) ods += a[i];
     58         else evs += a[i];
     59     }
     60     int odc = n / 2, evc = n / 2;
     61     if (n & 1) evc++;
     62 
     63     if (ods % odc != 0 || evs % evc != 0 || ods / odc != evs / evc) {
     64         cout << "NO";
     65         return;
     66     }
     67     cout << "YES";
     68 }
     69 
     70 int main() {
     71     int TESTS; cin >> TESTS;
     72     while (TESTS --> 0) {
     73         solve();
     74         cout << '\n';
     75     }
     76     return 0;
     77 }
     78 ```
     79 
     80 [2050C - Uninteresting Number](/contest/2050/problem/C "Codeforces Round 991 (Div. 3)")
     81 
     82 Идея: [DanGolov](/profile/DanGolov "Expert DanGolov")
     83 
     84 **Решение**
     85 
     86 Tutorial is loading...
     87 
     88 **Код**
     89 
     90 ```
     91 def solve():
     92     s = [int(x) for x in list(input())]
     93 
     94     sm = sum(s)
     95     twos = s.count(2)
     96     threes = s.count(3)
     97 
     98     for i in range(min(10, twos + 1)):
     99         for j in range(min(10, threes + 1)):
    100             if (sm + i * 2 + j * 6) % 9 == 0:
    101                 print('YES')
    102                 return
    103     print('NO')
    104 
    105 t = int(input())
    106 for _ in range(t):
    107     solve()
    108 ```
    109 
    110 [2050D - Digital string maximization](/contest/2050/problem/D "Codeforces Round 991 (Div. 3)")
    111 
    112 Идея: [AVdovin](/profile/AVdovin "Expert AVdovin")
    113 
    114 **Решение**
    115 
    116 Tutorial is loading...
    117 
    118 **Код**
    119 
    120 ```
    121 #include <bits/stdc++.h>
    122 
    123 using namespace std;
    124 
    125 void solve() {
    126     string s; cin >> s;
    127     for (int i = 0; i < s.size(); i++) {
    128         int best = s[i] - '0', pos = i;
    129         for (int j = i; j < min(i + 10, (int) s.size()); j++) {
    130             if (s[j] - '0' - (j - i) > best) {
    131                 best = s[j] - '0' - (j - i);
    132                 pos = j;
    133             }
    134         }
    135         while (pos > i) {
    136             swap(s[pos], s[pos - 1]);
    137             pos--;
    138         }
    139         s[i] = char(best + '0');
    140     }
    141     cout << s;
    142 }
    143 
    144 int main() {
    145     int TESTS = 1; cin >> TESTS;
    146     while (TESTS --> 0) {
    147         solve();
    148         cout << '\n';
    149     }
    150     return 0;
    151 }
    152 ```
    153 
    154 [2050E - Three Strings](/contest/2050/problem/E "Codeforces Round 991 (Div. 3)")
    155 
    156 Идея: [pskobx](/profile/pskobx "Candidate Master pskobx"), [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya")
    157 
    158 **Решение**
    159 
    160 Tutorial is loading...
    161 
    162 **Код**
    163 
    164 ```
    165 #include <iostream>
    166 #include <algorithm>
    167 
    168 static const int inf = 1e9;
    169 
    170 void solve() {
    171     std::string a, b, res;
    172     std::cin >> a >> b >> res;
    173     int n = (int) a.size(), m = (int) b.size();
    174     int dp[n + 1][m + 1];
    175     std::fill(&dp[0][0], &dp[0][0] + (n + 1) * (m + 1), inf);
    176     dp[0][0] = 0;
    177     for (int i = 0; i < n; i++) {
    178         dp[i + 1][0] = dp[i][0] + (a[i] != res[i]);
    179     }
    180     for (int j = 0; j < m; j++) {
    181         dp[0][j + 1] = dp[0][j] + (b[j] != res[j]);
    182     }
    183     for (int i = 1; i <= n; i++) {
    184         for (int j = 1; j <= m; j++) {
    185             dp[i][j] = std::min(dp[i - 1][j] + (a[i - 1] != res[i + j - 1]),
    186                                 dp[i][j - 1] + (b[j - 1] != res[i + j - 1]));
    187         }
    188     }
    189     std::cout << dp[n][m] << std::endl;
    190 }
    191 
    192 int main() {
    193     int tests;
    194     std::cin >> tests;
    195     while (tests--) {
    196         solve();
    197     }
    198 }
    199 ```
    200 
    201 [2050F - Maximum modulo equality](/contest/2050/problem/F "Codeforces Round 991 (Div. 3)")
    202 
    203 Идея: [AVdovin](/profile/AVdovin "Expert AVdovin")
    204 
    205 **Решение**
    206 
    207 Tutorial is loading...
    208 
    209 **Код**
    210 
    211 ```
    212 #include <bits/stdc++.h>
    213 
    214 using namespace std;
    215 
    216 const int LOGN = 20;
    217 
    218 vector<vector<int>> stGCD;
    219 
    220 int get_gcd(int l, int r) {
    221     int k = __lg(r - l + 1);
    222     return __gcd(stGCD[k][l], stGCD[k][r - (1 << k) + 1]);
    223 }
    224 
    225 void solve() {
    226     stGCD.clear();
    227     int n, q; cin >> n >> q;
    228     vector<int> a(n);
    229     for (int &x : a) cin >> x;
    230 
    231     vector<int> b;
    232     for (int i = 1; i < n; i++)
    233         b.push_back(abs(a[i - 1] - a[i]));
    234 
    235     stGCD.resize(LOGN, vector<int>(b.size(), 1));
    236     for (int i = 0; i < b.size(); i++)
    237         stGCD[0][i] = b[i];
    238     for (int i = 1; i < LOGN; i++)
    239         for (int j = 0; j + (1 << (i - 1)) < b.size(); j++)
    240             stGCD[i][j] = __gcd(stGCD[i - 1][j], stGCD[i - 1][j + (1 << (i - 1))]);
    241 
    242     while (q--) {
    243         int l, r; cin >> l >> r;
    244         if (l == r) {
    245             cout << 0 << " ";
    246             continue;
    247         }
    248         l--; r -= 2;
    249         int gcd = get_gcd(l, r);
    250         cout << gcd << " ";
    251     }
    252 }
    253 
    254 int main() {
    255     int TESTS = 1; cin >> TESTS;
    256     while (TESTS --> 0) {
    257         solve();
    258         cout << "\n";
    259     }
    260     return 0;
    261 }
    262 ```
    263 
    264 [2050G - Tree Destruction](/contest/2050/problem/G "Codeforces Round 991 (Div. 3)")
    265 
    266 Идея: [AVdovin](/profile/AVdovin "Expert AVdovin")
    267 
    268 **Решение**
    269 
    270 Tutorial is loading...
    271 
    272 **Код**
    273 
    274 ```
    275 #include <bits/stdc++.h>
    276 
    277 #define int long long
    278 #define x first
    279 #define y second
    280 
    281 using namespace std;
    282 
    283 void dfs(int v, int p, vector<vector<int>> &sl, vector<pair<int, int>> &dp){
    284     dp[v].x = sl[v].size();
    285     int m1 = -1, m2 = -1;
    286     for(int u: sl[v]){
    287         if(u == p){
    288             continue;
    289         }
    290         dfs(u, v, sl, dp);
    291         dp[v].x = max(dp[v].x, dp[u].x + (int)sl[v].size() - 2);
    292         m2 = max(m2, dp[u].x);
    293         if(m1 < m2) swap(m1, m2);
    294     }
    295     dp[v].y = dp[v].x;
    296     if(m2 != -1){
    297         dp[v].y = m1 + m2 + sl[v].size() - 4;
    298     }
    299 }
    300 
    301 void solve(int tc){
    302     int n;
    303     cin >> n;
    304     vector<vector<int>> sl(n);
    305     for(int i = 1; i < n; ++i){
    306         int u, v;
    307         cin >> u >> v;
    308         sl[--u].emplace_back(--v);
    309         sl[v].emplace_back(u);
    310     }
    311     vector<pair<int, int>> dp(n);
    312     dfs(0, 0, sl, dp);
    313     int ans = 0;
    314     for(int i = 0; i < n; ++i){
    315         ans = max(ans, max(dp[i].x, dp[i].y));
    316     }
    317     cout << ans;
    318 }
    319 
    320 bool multi = true;
    321 
    322 signed main() {
    323     int t = 1;
    324     if (multi)cin >> t;
    325     for (int i = 1; i <= t; ++i) {
    326         solve(i);
    327         cout << "\n";
    328     }
    329     return 0;
    330 }
    331 ```