codeforces-scrape

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

1611.md (10459B)


      1 Source: https://codeforces.com/blog/entry/97288
      2 
      3 [1611A - Make Even](/contest/1611/problem/A "Codeforces Round 756 (Div. 3)")
      4 
      5 Idea: [MisterGu](/profile/MisterGu "Unrated, MisterGu")
      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 int main() {
     19     int t;
     20     cin >> t;
     21     while(t--) {
     22         string n;
     23         cin >> n;
     24         if((n.back() - '0') % 2 == 0) {
     25             cout << "0\n";
     26             continue;
     27         }
     28         if((n[0] - '0') % 2 == 0) {
     29             cout << "1\n";
     30             continue;
     31         }
     32         int count_2 = count(n.begin(), n.end(), '2');
     33         int count_4 = count(n.begin(), n.end(), '4');
     34         int count_6 = count(n.begin(), n.end(), '6');
     35         int count_8 = count(n.begin(), n.end(), '8');
     36         if(count_2 > 0 || count_4 > 0 || count_6 > 0 || count_8 > 0) {
     37             cout << "2\n";
     38             continue;
     39         }
     40         cout << "-1\n";
     41     }
     42     return 0;
     43 }
     44 ```
     45 
     46 [1611B - Team Composition: Programmers and Mathematicians](/contest/1611/problem/B "Codeforces Round 756 (Div. 3)")
     47 
     48 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     49 
     50 **Tutorial**
     51 
     52 Tutorial is loading...
     53 
     54 **Solution**
     55 
     56 ```
     57 #include <bits/stdc++.h>
     58  
     59 using namespace std;
     60 using ll = long long;
     61  
     62 void solve() {
     63     ll a, b;
     64     cin >> a >> b;
     65     cout << min(min(a, b), (a + b) / 4) << '\n';
     66 }
     67  
     68 int main() {
     69     int t;
     70     cin >> t;
     71     for (int i = 0; i < t; ++i) {
     72         solve();
     73     }
     74     return 0;
     75 }
     76 ```
     77 
     78 [1611C - Polycarp Recovers the Permutation](/contest/1611/problem/C "Codeforces Round 756 (Div. 3)")
     79 
     80 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     81 
     82 **Tutorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Solution**
     87 
     88 ```
     89 #include <bits/stdc++.h>
     90  
     91 using namespace std;
     92  
     93 #define forn(i, n) for (int i = 0; i < int(n); i++)
     94  
     95 int main() {
     96     int t;
     97     cin >> t;
     98     forn(tt, t) {
     99         int n;
    100         cin >> n;
    101         vector<int> a(n);
    102         forn(i, n)
    103             cin >> a[i];
    104         if (a[0] != n && a[n - 1] != n)
    105             cout << -1 << endl;
    106         else {
    107             for (int i = n - 1; i >= 0; i--)
    108                 cout << a[i] << " ";
    109             cout << endl;
    110         }
    111     }
    112 }
    113 ```
    114 
    115 [1611D - Weights Assignment For Tree Edges](/contest/1611/problem/D "Codeforces Round 756 (Div. 3)")
    116 
    117 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    118 
    119 **Tutorial**
    120 
    121 Tutorial is loading...
    122 
    123 **Solution**
    124 
    125 ```
    126 #include <bits/stdc++.h>
    127  
    128 using namespace std;
    129  
    130 void solve(){
    131     int n;
    132     cin >> n;
    133     vector<int> b(n + 1), p(n + 1), dist(n + 1, -1);
    134  
    135     for(int i = 1; i <= n; i++)
    136         cin >> b[i];
    137     for(int i = 1; i <= n; i++)
    138         cin >> p[i];
    139  
    140     if (b[p[1]] != p[1]){
    141         cout << -1 << '\n';
    142         return;
    143     }
    144  
    145     dist[p[1]] = 0;
    146     for(int i = 2; i <= n; i++){
    147         if(dist[b[p[i]]] == -1){
    148             cout << -1 << '\n';
    149             return;
    150         }
    151         dist[p[i]] = dist[p[i - 1]] + 1;
    152     }
    153  
    154     for(int i = 1; i <= n; i++) {
    155         cout << dist[i] - dist[b[i]] << ' ';
    156     }
    157     cout << '\n';
    158 }
    159  
    160 int main() {
    161     int t;
    162     cin >> t;
    163     while(t-- > 0) {
    164         solve();
    165     }
    166 }
    167 ```
    168 
    169 [1611E1 - Escape The Maze (easy version)](/contest/1611/problem/E1 "Codeforces Round 756 (Div. 3)")
    170 
    171 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    172 
    173 **Tutorial**
    174 
    175 Tutorial is loading...
    176 
    177 **Solution**
    178 
    179 ```
    180 //
    181 // Created by Vlad on 16.11.2021.
    182 //
    183  
    184 #include <bits/stdc++.h>
    185  
    186 #define int long long
    187 #define mp make_pair
    188 #define x first
    189 #define y second
    190 #define all(a) (a).begin(), (a).end()
    191 #define rall(a) (a).rbegin(), (a).rend()
    192  
    193 typedef long double ld;
    194 typedef long long ll;
    195  
    196 using namespace std;
    197  
    198 mt19937 rnd(143);
    199  
    200 const int inf = 1e10;
    201 const int M = 998244353;
    202 const ld pi = atan2(0, -1);
    203 const ld eps = 1e-4;
    204  
    205 void solve() {
    206     int n, k;
    207     cin >> n >> k;
    208     vector<int> color(n, -1);
    209     deque<int> q;
    210     for(int i = 0; i < k; ++i){
    211         int x;
    212         cin >> x;
    213         color[--x] = 0;
    214         q.push_back(x);
    215     }
    216     color[0] = 1;
    217     q.push_back(0);
    218     vector<vector<int>> g(n);
    219     for(int i = 0; i < n - 1; ++i){
    220         int u, v;
    221         cin >> u >> v;
    222         g[--u].push_back(--v);
    223         g[v].push_back(u);
    224     }
    225     while(!q.empty()){
    226         int v = q.front();
    227         q.pop_front();
    228         for(int u: g[v]){
    229             if(color[u] == -1){
    230                 color[u] = color[v];
    231                 q.push_back(u);
    232             }
    233         }
    234     }
    235     for(int v = 1; v < n; ++v){
    236         if(g[v].size() == 1 && color[v] == 1){
    237             cout << "YES";
    238             return;
    239         }
    240     }
    241     cout << "NO";
    242 }
    243  
    244 bool multi = true;
    245  
    246 signed main() {
    247     int t = 1;
    248     if (multi) {
    249         cin >> t;
    250     }
    251     for (; t != 0; --t) {
    252         solve();
    253         cout << "\n";
    254     }
    255     return 0;
    256 }
    257 ```
    258 
    259 [1611E2 - Escape The Maze (hard version)](/contest/1611/problem/E2 "Codeforces Round 756 (Div. 3)")
    260 
    261 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
    262 
    263 **Tutorial**
    264 
    265 Tutorial is loading...
    266 
    267 **Solution**
    268 
    269 ```
    270 #include <bits/stdc++.h>
    271  
    272 #define int long long
    273 #define mp make_pair
    274 #define x first
    275 #define y second
    276 #define all(a) (a).begin(), (a).end()
    277 #define rall(a) (a).rbegin(), (a).rend()
    278  
    279 /*#pragma GCC optimize("Ofast")
    280 #pragma GCC optimize("no-stack-protector")
    281 #pragma GCC optimize("unroll-loops")
    282 #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
    283 #pragma GCC optimize("fast-math")
    284 */
    285 typedef long double ld;
    286 typedef long long ll;
    287  
    288 using namespace std;
    289  
    290 mt19937 rnd(143);
    291  
    292 const int inf = 1e10;
    293 const int M = 998244353;
    294 const ld pi = atan2(0, -1);
    295 const ld eps = 1e-4;
    296  
    297 vector<vector<int>> sl;
    298 vector<int> nearest;
    299  
    300 int count(int v, int dist, int p = -1){
    301     bool children = true;
    302     int s = 0;
    303     for(int u: sl[v]){
    304         if(u == p) continue;
    305         int c = count(u, dist + 1, v);
    306         if(c < 0) children = false;
    307         nearest[v] = min(nearest[v], nearest[u] + 1);
    308         s += c;
    309     }
    310     if(nearest[v] <= dist) return 1;
    311     if(s == 0 || !children) return -1;
    312     return s;
    313 }
    314  
    315 void solve() {
    316     int n, k;
    317     cin >> n >> k;
    318     sl.assign(n, vector<int>(0));
    319     nearest.assign(n, n);
    320     for(int i = 0; i < k; ++i){
    321         int x;
    322         cin >> x;
    323         --x;
    324         nearest[x] = 0;
    325     }
    326     for(int i = 1; i  < n; ++i){
    327         int u, v;
    328         cin >> u >> v;
    329         --u, --v;
    330         sl[u].emplace_back(v);
    331         sl[v].emplace_back(u);
    332     }
    333     cout << count(0, 0);
    334 }
    335  
    336 bool multi = true;
    337  
    338 signed main() {
    339     //freopen("in.txt", "r", stdin);
    340     //freopen("in.txt", "w", stdout);
    341     /*ios_base::sync_with_stdio(false);
    342     cin.tie(nullptr);
    343     cout.tie(nullptr);*/
    344     int t = 1;
    345     if (multi) {
    346         cin >> t;
    347     }
    348     for (; t != 0; --t) {
    349         solve();
    350         cout << "\n";
    351     }
    352     return 0;
    353 }
    354 ```
    355 
    356 [1611F - ATM and Students](/contest/1611/problem/F "Codeforces Round 756 (Div. 3)")
    357 
    358 Idea: [Gol_D](/profile/Gol_D "Candidate Master Gol_D"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    359 
    360 **Tutorial**
    361 
    362 Tutorial is loading...
    363 
    364 **Solution**
    365 
    366 ```
    367 #include <bits/stdc++.h>
    368 
    369 using namespace std;
    370 
    371 typedef long long ll;
    372 
    373 #define forn(i, n) for (int i = 0; i < int(n); i++)
    374 
    375 vector<ll> t, a;
    376 ll s, tl;
    377 
    378 const ll MAX = 1'000'000'000'000'000LL;
    379 
    380 void build(int v, int l, int r) {
    381 	if (l == r)
    382 		t[v] = a[l];
    383 	else {
    384 		int m = (l + r) / 2;
    385 		build (v * 2, l, m);
    386 		build (v * 2 + 1, m + 1, r);
    387 		t[v] = min(t[v * 2], t[v * 2 + 1]);
    388 	}
    389 }
    390 
    391 void update(int v, int l, int r) {
    392 	if (l == r)
    393 		t[v] = MAX;
    394 	else {
    395 		int m = (l + r) / 2;
    396 		if (tl <= m)
    397 			update(v * 2, l, m);
    398 		else
    399 			update(v * 2 + 1, m + 1, r);
    400 		t[v] = min(t[v * 2], t[v * 2 + 1]);
    401 	}
    402 }
    403 
    404 int lower_bound_s(int v, int l, int r) {
    405 	if (r < tl || (l == r && s < -t[v])) {
    406 		return -1;
    407 	}
    408     if (l == r || -t[v] <= s) {
    409         return r;
    410     }
    411 	int m = (l + r) / 2;
    412 
    413 	if (m < tl) {
    414         return lower_bound_s(2 * v + 1, m + 1, r);
    415 	}
    416 	if (s < -t[2 * v]) {
    417         return lower_bound_s(2 * v, l, m);
    418 	}
    419 	int res = lower_bound_s(2 * v + 1, m + 1, r);
    420 	return (res == -1) ? m : res;
    421 }
    422 
    423 int main() {
    424     int tests;
    425     cin >> tests;
    426     forn(tt, tests) {
    427         int n;
    428         cin >> n >> s;
    429         t = vector<ll>(4 * n);
    430         a = vector<ll>(n);
    431         forn(i, n) {
    432             cin >> a[i];
    433         }
    434         for (int i = 1; i < n; ++i) {
    435             a[i] += a[i - 1];
    436         }
    437         build(1, 0, n - 1);
    438         int first = -1, second = -2;
    439         for (tl = 0; tl < n; ++tl) {
    440             int v = lower_bound_s(1, 0, n - 1);
    441             if (v != -1 && v - tl > second - first) {
    442                 first = tl + 1;
    443                 second = v + 1;
    444             }
    445             s -= a[tl];
    446             if (tl != 0) s += a[tl - 1];
    447             update(1, 0, n - 1);
    448         }
    449         if (first == -1) {
    450             cout << -1;
    451         } else {
    452             cout << first << " " << second;
    453         }
    454         cout << endl;
    455     }
    456 }
    457 ```
    458 
    459 [1611G - Robot and Candies](/contest/1611/problem/G "Codeforces Round 756 (Div. 3)")
    460 
    461 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    462 
    463 **Tutorial**
    464 
    465 Tutorial is loading...
    466 
    467 **Solution**
    468 
    469 ```
    470 #include <bits/stdc++.h>
    471  
    472 using namespace std;
    473  
    474 #define forn(i, n) for (int i = 0; i < int(n); i++)
    475 #define sz(v) (int)v.size()
    476  
    477 const int N = 1e6 + 50;
    478 string a[N];
    479  
    480 int n,m;
    481 int ans;
    482  
    483 void solve(int sum0) {
    484     vector<int> v;
    485     for (int sum = sum0, ad = 0, pref = 0; sum < n + m; sum += 2, ad++) {
    486         vector<int> cur;
    487         int li = max(0, sum - m + 1), ri = min(n - 1, sum);
    488         if (li > ri) continue;
    489  
    490         for (int i = li; i <= ri; i++) {
    491             int j = sum - i;
    492  
    493             if (a[i][j] == '1')
    494                 cur.emplace_back(i);
    495         }
    496  
    497         while (pref != sz(v) && v[pref] + ad > ri) {
    498             pref++;
    499         }
    500         for (int i = pref; i < sz(v); i++) {
    501             int new_val = v[i];
    502             while (!cur.empty() && cur.back() - ad >= v[i]) {
    503                 new_val = max(new_val, cur.back() - ad);
    504                 cur.pop_back();
    505             }
    506             v[i] = new_val;
    507         }
    508         if (!cur.empty()) {
    509             v.emplace_back(cur.back() - ad);
    510             ans++;
    511         }
    512     }
    513 }
    514  
    515 int main() {
    516     int t;
    517     cin >> t;
    518  
    519     forn(tt, t) {
    520         cin >> n >> m;
    521  
    522         forn(i, n) {
    523             string s; 
    524             cin >> a[i];
    525         }
    526  
    527         ans = 0;
    528         solve(0);
    529         solve(1);
    530         
    531         cout << ans << '\n';
    532     }
    533 }
    534 ```