codeforces-scrape

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

1675.md (8646B)


      1 Source: https://codeforces.com/blog/entry/102550
      2 
      3 [1675A - Food for Animals](/contest/1675/problem/A "Codeforces Round 787 (Div. 3)")
      4 
      5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 #define forn(i, n) for (int i = 0; i < int(n); i++)
     19 
     20 int main() {
     21     int t;
     22     cin >> t;
     23     forn(tt, t) {
     24         int a, b, c, x, y;
     25         cin >> a >> b >> c >> x >> y;
     26         int ax = min(a, x);
     27         int by = min(b, y);
     28         a -= ax;
     29         x -= ax;
     30         b -= by;
     31         y -= by;
     32         if (c >= x + y)
     33             cout << "YES" << endl;
     34         else
     35             cout << "NO" << endl;
     36     }
     37 }
     38 ```
     39 
     40 [1675B - Make It Increasing](/contest/1675/problem/B "Codeforces Round 787 (Div. 3)")
     41 
     42 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     43 
     44 **Tutorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Solution**
     49 
     50 ```
     51 #include<bits/stdc++.h>
     52 using namespace std;
     53 void solve(){
     54     int n;
     55     cin >> n;
     56     vector<int>a(n);
     57     for(auto &i : a) cin >> i;
     58     int ans = 0;
     59     for(int i = n - 2; i >= 0; i--){
     60         while(a[i] >= a[i + 1] && a[i] > 0){
     61             a[i] /= 2;
     62             ans++;
     63         }
     64         if(a[i] == a[i+1]){
     65             cout << -1 << '\n';
     66             return;
     67         }
     68     }
     69     cout << ans << '\n';
     70 }
     71 int main(){
     72     int t;
     73     cin >> t;
     74     while(t--){
     75         solve();
     76     }
     77 }
     78 ```
     79 
     80 [1675C - Detective Task](/contest/1675/problem/C "Codeforces Round 787 (Div. 3)")
     81 
     82 Idea: [Gol_D](/profile/Gol_D "Candidate Master Gol_D")
     83 
     84 **Tutorial**
     85 
     86 Tutorial is loading...
     87 
     88 **Solution**
     89 
     90 ```
     91 #include <bits/stdc++.h>
     92 
     93 using namespace std;
     94 
     95 #define forn(i, n) for (int i = 0; i < int(n); i++)
     96 
     97 int main() {
     98     int t;
     99     cin >> t;
    100     forn(tt, t) {
    101         string s;
    102         cin >> s;
    103         int n = s.length();
    104         vector<bool> a(n + 1);
    105         a[0] = true;
    106         forn(i, n)
    107             a[i + 1] = a[i] && (s[i] == '1' || s[i] == '?');
    108         vector<bool> b(n + 1);
    109         b[0] = true;
    110         for (int i = n - 1; i >= 0; i--)
    111             b[n - i] = b[n - i - 1] && (s[i] == '0' || s[i] == '?');
    112         int result = 0;
    113         forn(i, n)
    114             if (a[i] && b[n - i - 1])
    115                 result++;
    116         cout << result << endl;
    117     }
    118 }
    119 ```
    120 
    121 [1675D - Vertical Paths](/contest/1675/problem/D "Codeforces Round 787 (Div. 3)")
    122 
    123 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    124 
    125 **Tutorial**
    126 
    127 Tutorial is loading...
    128 
    129 **Solution**
    130 
    131 ```
    132 #include<bits/stdc++.h>
    133 using namespace std;
    134 
    135 void solve(){
    136     int n;
    137     cin >> n;
    138     vector<int>b(n + 1);
    139     vector<bool>leaf(n + 1, true);
    140     for(int i = 1; i <= n; i++) {
    141         cin >> b[i];
    142         leaf[b[i]] = false;
    143     }
    144 
    145     if(n == 1){
    146         cout << "1\n1\n1\n\n";
    147         return;
    148     }
    149 
    150     vector<int>paths[n + 1];
    151     vector<bool>used(n + 1, false);
    152     int color = 0;
    153 
    154     for(int i = 1; i <= n; i++){
    155         if(!leaf[i]) continue;
    156         used[i] = true;
    157         paths[color].emplace_back(i);
    158 
    159         int v = i;
    160         while (b[v] != v && !used[b[v]]){
    161             v = b[v];
    162             used[v] = true;
    163             paths[color].emplace_back(v);
    164         }
    165         color++;
    166     }
    167 
    168     cout << color << '\n';
    169     for(auto &path : paths){
    170         if(path.empty()) continue;
    171         cout << (int)path.size() << '\n';
    172         reverse(path.begin(), path.end());
    173         for(auto &v: path) cout << v << ' ';
    174         cout << '\n';
    175     }
    176     cout << '\n';
    177 }
    178 int main(){
    179     int t;
    180     cin >> t;
    181     while(t--){
    182         solve();
    183     }
    184 }
    185 ```
    186 
    187 [1675E - Replace With the Previous, Minimize](/contest/1675/problem/E "Codeforces Round 787 (Div. 3)")
    188 
    189 Idea: [myav](/profile/myav "Pupil myav")
    190 
    191 **Tutorial**
    192 
    193 Tutorial is loading...
    194 
    195 **Solution**
    196 
    197 ```
    198 #include <bits/stdc++.h>
    199 
    200 using namespace std;
    201 
    202 #define forn(i, n) for (int i = 0; i < int(n); i++)
    203 #define sz(v) (int)v.size()
    204 #define all(v) v.begin(),v.end()
    205 #define eb emplace_back
    206 
    207 template <class T> bool ckmax(T &a, T b) {return a<b ? a=b, true : false;}
    208 
    209 void solve() {
    210     int n,k; cin >> n >> k;
    211     string s; cin >> s;
    212 
    213     char mn = 'a';
    214     for (int i = 0; i < n; i++) if(s[i] > mn) {
    215         if (s[i] - 'a' > k) {
    216             k -= mn - 'a';
    217             int to = s[i] - k;
    218             for (char c = s[i]; c > to; c--) {
    219                 for (char &e:s) if (e == c) {
    220                     e = char(c-1);
    221                 }
    222             }
    223             break;
    224         } else ckmax(mn, s[i]);
    225     }
    226     for (char &e:s) if (e <= mn) {
    227         e = 'a';
    228     }
    229     cout << s << endl;
    230 }
    231 
    232 int main() {
    233     int t;
    234     cin >> t;
    235 
    236     forn(tt, t) {
    237         solve();
    238     }
    239 }
    240 ```
    241 
    242 [1675F - Vlad and Unfinished Business](/contest/1675/problem/F "Codeforces Round 787 (Div. 3)")
    243 
    244 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    245 
    246 **Tutorial**
    247 
    248 Tutorial is loading...
    249 
    250 **Solution**
    251 
    252 ```
    253 #include <bits/stdc++.h>
    254 
    255 using namespace std;
    256 
    257 //#define int long long
    258 #define ll long long
    259 //#define double long double
    260 #define all(a) a.begin(), a.end()
    261 #define rall(a) a.rbegin(), a.rend()
    262 
    263 const int MOD = 1e9 + 7;
    264 const int maxN = 5e3 + 1;
    265 const int INF = 2e9;
    266 const int MB = 20;
    267 
    268 vector<vector<int>> g;
    269 vector<bool> todo, good;
    270 
    271 void dfs(int v, int p = -1) {
    272     for (int u : g[v]) {
    273         if (u != p) {
    274             dfs(u, v);
    275             if (todo[u]) {
    276                 todo[v] = true;
    277             }
    278             if (good[u]) {
    279                 good[v] = true;
    280             }
    281         }
    282     }
    283 }
    284 
    285 void solve() {
    286     int n, k;
    287     cin >> n >> k;
    288     g.clear();
    289     g.resize(n);
    290     int x, y;
    291     cin >> x >> y;
    292     --x;
    293     --y;
    294     todo.resize(n);
    295     fill(all(todo), false);
    296     good.resize(n);
    297     fill(all(good), false);
    298     for (int i = 0; i < k; ++i) {
    299         int v;
    300         cin >> v;
    301         --v;
    302         todo[v] = true;
    303     }
    304     good[y] = true;
    305     for (int i = 0; i < n - 1; ++i) {
    306         int v, u;
    307         cin >> v >> u;
    308         --v;
    309         --u;
    310         g[v].push_back(u);
    311         g[u].push_back(v);
    312     }
    313     dfs(x);
    314     int ans = 0;
    315     for (int i = 0; i < n; ++i) {
    316         if (i == x) {
    317             continue;
    318         }
    319         if (good[i]) {
    320             ++ans;
    321         } else if (todo[i]) {
    322             ans += 2;
    323         }
    324     }
    325     cout << ans << '\n';
    326 }
    327 
    328 signed main() {
    329     ios_base::sync_with_stdio(false);
    330     cin.tie(0);
    331     cout.tie(0);
    332     //    srand(time(0));
    333     int t = 1;
    334     cin >> t;
    335     while (t--) solve();
    336 }
    337 ```
    338 
    339 [1675G - Sorting Pancakes](/contest/1675/problem/G "Codeforces Round 787 (Div. 3)")
    340 
    341 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    342 
    343 **Tutorial**
    344 
    345 Tutorial is loading...
    346 
    347 **Solution**
    348 
    349 ```
    350 #include <bits/stdc++.h>
    351 
    352 //#define int long long
    353 #define mp make_pair
    354 #define x first
    355 #define y second
    356 #define all(a) (a).begin(), (a).end()
    357 #define rall(a) (a).rbegin(), (a).rend()
    358 
    359 typedef long double ld;
    360 typedef long long ll;
    361 
    362 using namespace std;
    363 
    364 mt19937 rnd(143);
    365 
    366 const ll inf = 1e9 + 7;
    367 const ll M = 998'244'353;
    368 const ld pi = atan2(0, -1);
    369 const ld eps = 1e-4;
    370 
    371 void solve(int test_case) {
    372     int n, m;
    373     cin >> n >> m;
    374     vector<int> a(n), pancakes(1);
    375     for(int &e: a) cin >> e;
    376     for(int i = 0; i < n; ++i){
    377         for(int j = 0; j < a[i]; ++j){
    378             pancakes.emplace_back(i);
    379             int c = pancakes.size();
    380             pancakes[c - 1] += pancakes[c - 2];
    381         }
    382         if(i > 0) a[i] += a[i - 1];
    383     }
    384     vector<vector<vector<int>>> dp(n, vector<vector<int>>(m + 1, vector<int>(m + 1, inf)));
    385     for(int j = 0; j <= m; j++){
    386         if(a[0] >= j) dp[0][j][j] = a[0] - j;//moved right
    387         else dp[0][j][j] = pancakes[j];//moved from right
    388     }
    389     for(int j = m - 1; j >= 0; --j){
    390         for(int k = j; k <= m; ++k){
    391             dp[0][j][k] = min(dp[0][j][k], dp[0][j + 1][k]);
    392         }
    393     }
    394     for(int i = 1; i < n; ++i){
    395         for(int j = 0; j <= m; ++j){
    396             for(int k = j; k <= m; ++k){
    397                 int add = 0;
    398                 if(a[i] >= k) add = a[i] - k;//moved to i + 1
    399                 else {
    400                     int lend = min(j, k - a[i]);
    401                     add = pancakes[k] - pancakes[k - lend] - i * (lend);//moved from greater i
    402                 }
    403                 dp[i][j][k] = dp[i - 1][j][k - j] + add;
    404             }
    405         }
    406 
    407         for(int j = m - 1; j >= 0; --j){
    408             for(int k = (i + 1) * j; k <= m; ++k){
    409                 dp[i][j][k] = min(dp[i][j][k], dp[i][j + 1][k]);
    410             }
    411         }
    412     }
    413     cout << dp[n-1][0][m];
    414 }
    415 
    416 bool multi = false;
    417 
    418 signed main() {
    419     int t = 1;
    420     if (multi) {
    421         cin >> t;
    422     }
    423     for (int i = 1; i <= t; ++i) {
    424         solve(i);
    425         cout << "\n";
    426     }
    427     return 0;
    428 }
    429 ```