codeforces-scrape

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

1702.md (10360B)


      1 Source: https://codeforces.com/blog/entry/104763
      2 
      3 [1702A - Round Down the Price](/contest/1702/problem/A "Codeforces Round 805 (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 #define sz(v) (int)v.size()
     20 #define all(v) v.begin(),v.end()
     21 #define eb emplace_back
     22 
     23 void solve() {
     24     int m; cin >> m;
     25     string t = to_string(m);
     26     string s = "1";
     27     for (int i = 1; i < sz(t); i++) {
     28         s += '0';
     29     }
     30     int k = stoi(s);
     31     cout << m - k << '\n';
     32 }
     33 
     34 int main() {
     35     int t;
     36     cin >> t;
     37 
     38     forn(tt, t) {
     39         solve();
     40     }
     41 }
     42 ```
     43 
     44 [1702B - Polycarp Writes a String from Memory](/contest/1702/problem/B "Codeforces Round 805 (Div. 3)")
     45 
     46 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     47 
     48 **Tutorial**
     49 
     50 Tutorial is loading...
     51 
     52 **Solution**
     53 
     54 ```
     55 #include <bits/stdc++.h>
     56 
     57 using namespace std;
     58 
     59 #define forn(i, n) for (int i = 0; i < int(n); i++)
     60 #define sz(v) (int)v.size()
     61 #define all(v) v.begin(),v.end()
     62 #define eb emplace_back
     63 
     64 void solve() {
     65     string s; cin >> s;
     66     set<char> v;
     67     int ans = 0;
     68     for (int i = 0; i < sz(s); i++) {
     69         v.insert(s[i]);
     70         if (sz(v) > 3) {
     71             ans++;
     72             v.clear();
     73             v.insert(s[i]);
     74         }
     75     }
     76     if (!v.empty()) ans++;
     77     cout << ans << endl;
     78 }
     79 
     80 int main() {
     81     int t;
     82     cin >> t;
     83 
     84     forn(tt, t) {
     85         solve();
     86     }
     87 }
     88 ```
     89 
     90 [1702C - Train and Queries](/contest/1702/problem/C "Codeforces Round 805 (Div. 3)")
     91 
     92 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     93 
     94 **Tutorial**
     95 
     96 Tutorial is loading...
     97 
     98 **Solution**
     99 
    100 ```
    101 #include<bits/stdc++.h>
    102 using namespace std;
    103 #define forn(i, n) for (int i = 0; i < int(n); i++)
    104 
    105 void solve(){
    106     int n, k;
    107     cin >> n >> k;
    108     map<int, pair<int, int>>m;
    109     forn(i, n){
    110         int u;
    111         cin >> u;
    112         if(!m.count(u)) {
    113             m[u].first = i;
    114             m[u].second = i;
    115         }
    116         else m[u].second = i;
    117     }
    118     forn(i, k){
    119         int a, b;
    120         cin >> a >> b;
    121         if(!m.count(a) or !m.count(b) or m[a].first > m[b].second) {
    122             cout << "NO\n"; //equals = 0 = wrong
    123         }
    124         else cout << "YES\n";
    125     }
    126 }
    127 
    128 int main(){
    129     int t;
    130     cin >> t;
    131     while(t--){
    132         solve();
    133     }
    134 }
    135 ```
    136 
    137 [1702D - Not a Cheap String](/contest/1702/problem/D "Codeforces Round 805 (Div. 3)")
    138 
    139 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    140 
    141 **Tutorial**
    142 
    143 Tutorial is loading...
    144 
    145 **Solution**
    146 
    147 ```
    148 #include <bits/stdc++.h>
    149 
    150 using namespace std;
    151 
    152 #define forn(i, n) for (int i = 0; i < int(n); i++)
    153 
    154 int main() {
    155     int t;
    156     cin >> t;
    157     forn(tt, t) {
    158         string s;
    159         cin >> s;
    160         int p;
    161         cin >> p;
    162         string w(s);
    163         sort(w.rbegin(), w.rend());
    164         int cost = 0;
    165         forn(i, s.length())
    166             cost += s[i] - 'a' + 1;
    167         map<char,int> del;
    168         forn(i, w.length())
    169             if (cost > p) {
    170                 del[w[i]]++;
    171                 cost -= w[i] - 'a' + 1;
    172             }
    173         forn(i, s.length()) {
    174             if (del[s[i]] > 0) {
    175                 del[s[i]]--;
    176                 continue;
    177             }
    178             cout << s[i];
    179         }
    180         cout << endl;
    181     }
    182 }
    183 ```
    184 
    185 [1702E - Split Into Two Sets](/contest/1702/problem/E "Codeforces Round 805 (Div. 3)")
    186 
    187 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    188 
    189 **Tutorial**
    190 
    191 Tutorial is loading...
    192 
    193 **Solution**
    194 
    195 ```
    196 #include <bits/stdc++.h>
    197 
    198 using namespace std;
    199 
    200 typedef long long ll;
    201 
    202 #define forn(i, n) for (int i = 0; i < int(n); i++)
    203 
    204 map<int, vector<int>> m;
    205 vector<bool> used;
    206 
    207 int go(int v) {
    208     used[v] = true;
    209     for (auto now : m[v]) {
    210         if (!used[now]) {
    211             return go(now) + 1;
    212         }
    213     }
    214     return 1;
    215 }
    216 
    217 void solve() {
    218 
    219     int n, x, y;
    220     cin >> n;
    221 
    222     m.clear();
    223     used.clear();
    224     used.resize(n + 1, false);
    225 
    226     bool fault = false;
    227     forn(i, n) {
    228         cin >> x >> y;
    229         m[x].push_back(y);
    230         m[y].push_back(x);
    231         if (x == y || m[x].size() > 2 || m[y].size() > 2) fault = true;
    232     }
    233 
    234     if (fault) {
    235         cout << "NO\n";
    236         return;
    237     }
    238 
    239     forn(i, n) {
    240         if (!used[i + 1]) {
    241             if (go(i + 1) % 2) {
    242                 cout << "NO\n";
    243                 return;
    244             }
    245         }
    246     }
    247 
    248     cout << "YES\n";
    249 }
    250 int main() {
    251     int tests;
    252     cin >> tests;
    253     forn(tt, tests) {
    254         solve();
    255     }
    256 }
    257 ```
    258 
    259 [1702F - Equate Multisets](/contest/1702/problem/F "Codeforces Round 805 (Div. 3)")
    260 
    261 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    262 
    263 **Tutorial**
    264 
    265 Tutorial is loading...
    266 
    267 **Solution**
    268 
    269 ```
    270 #include <bits/stdc++.h>
    271 
    272 using namespace std;
    273 
    274 #define forn(i, n) for (int i = 0; i < int(n); i++)
    275 #define sz(v) (int)v.size()
    276 #define all(v) v.begin(),v.end()
    277 #define eb emplace_back
    278 
    279 const int INF = 1e9;
    280 
    281 void solve() {
    282     int n; cin >> n;
    283     multiset<int> a, b;
    284 
    285     forn(i, n) {
    286         int x; cin >> x;
    287         while (x % 2 == 0) {
    288             x /= 2;
    289         }
    290         a.insert(x);
    291     }
    292 
    293     forn(i, n) {
    294         int x; cin >> x;
    295         b.insert(x);
    296     }
    297     n = sz(a);
    298 
    299     while (!b.empty()) {
    300         int x = *b.rbegin();
    301         // cout << x << endl;
    302         if (!a.count(x)) {
    303             if (x == 1) break;
    304             b.erase(b.find(x));
    305             b.insert(x / 2);
    306         } else {
    307             b.erase(b.find(x));
    308             a.erase(a.find(x));
    309         }
    310     }
    311 
    312     cout << (b.empty() ? "YES" : "NO") << endl;
    313 
    314 }
    315 
    316 int main() {
    317     int t;
    318     cin >> t;
    319 
    320     forn(tt, t) {
    321         solve();
    322     }
    323 }
    324 ```
    325 
    326 [1702G1 - Passable Paths (easy version)](/contest/1702/problem/G1 "Codeforces Round 805 (Div. 3)")
    327 
    328 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    329 
    330 **Tutorial**
    331 
    332 Tutorial is loading...
    333 
    334 **Solution**
    335 
    336 ```
    337 #include <bits/stdc++.h>
    338 
    339 #define int long long
    340 #define pb emplace_back
    341 #define mp make_pair
    342 #define x first
    343 #define y second
    344 #define all(a) a.begin(), a.end()
    345 #define rall(a) a.rbegin(), a.rend()
    346 
    347 typedef long double ld;
    348 typedef long long ll;
    349 
    350 using namespace std;
    351 
    352 mt19937 rnd(143);
    353 
    354 const int inf = 1e15;
    355 const int M = 1e9 + 7;
    356 const ld pi = atan2(0, -1);
    357 const ld eps = 1e-6;
    358 
    359 void depth(int v, int p, vector<vector<int>> &sl, vector<int> &d){
    360     if(p >= 0) d[v] = d[p] + 1;
    361     for(int u: sl[v]){
    362         if(u == p) continue;
    363         depth(u, v, sl, d);
    364     }
    365 }
    366 
    367 int dfs(int v, int p, vector<vector<int>> &sl, vector<bool> &chosen){
    368     int res = 0;
    369     bool lower = false;
    370     for(int u: sl[v]){
    371         if(u == p) continue;
    372         res += dfs(u, v, sl, chosen);
    373         lower = lower || chosen[u];
    374     }
    375     chosen[v] = chosen[v] || lower;
    376     if(chosen[v] && !lower) res = 1;
    377     return res;
    378 }
    379 
    380 void solve(){
    381     int n;
    382     cin >> n;
    383     vector<vector<int>> sl(n);
    384     for(int i = 1; i < n; ++i){
    385         int u, v;
    386         cin >> u >> v;
    387         sl[--u].push_back(--v);
    388         sl[v].push_back(u);
    389     }
    390     vector<int> d(n);
    391     depth(0, -1, sl, d);
    392     int q;
    393     cin >> q;
    394     for(; q; --q){
    395         int k;
    396         cin >> k;
    397         vector<bool> chosen(n);
    398         int mx = 0;
    399         for(int i = 0; i < k; ++i){
    400             int p;
    401             cin >> p;
    402             --p;
    403             if(d[p] > d[mx]) mx = p;
    404             chosen[p] = true;
    405         }
    406         int leaves = dfs(mx, -1, sl, chosen);
    407         if(leaves == 1) cout << "YES\n";
    408         else cout << "NO\n";
    409     }
    410 }
    411 
    412 bool multi = false;
    413 
    414 signed main() {
    415     int t = 1;
    416     if (multi)cin >> t;
    417     for (; t; --t) {
    418         solve();
    419         //cout << endl;
    420     }
    421     return 0;
    422 }
    423 ```
    424 
    425 [1702G2 - Passable Paths (hard version)](/contest/1702/problem/G2 "Codeforces Round 805 (Div. 3)")
    426 
    427 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    428 
    429 **Tutorial**
    430 
    431 Tutorial is loading...
    432 
    433 **Solution**
    434 
    435 ```
    436 #include <bits/stdc++.h>
    437 
    438 #define int long long
    439 #define pb emplace_back
    440 #define mp make_pair
    441 #define x first
    442 #define y second
    443 #define all(a) a.begin(), a.end()
    444 #define rall(a) a.rbegin(), a.rend()
    445 
    446 typedef long double ld;
    447 typedef long long ll;
    448 
    449 using namespace std;
    450 
    451 mt19937 rnd(143);
    452 
    453 const int inf = 1e15;
    454 const int M = 1e9 + 7;
    455 const ld pi = atan2(0, -1);
    456 const ld eps = 1e-6;
    457 
    458 int n, sz;
    459 vector<vector<int>> sl, up;
    460 vector<int> d;
    461 
    462 void precalc(int v, int p){
    463     d[v] = d[p] + 1;
    464     up[v][0] = p;
    465     for(int i = 1; i <= sz; ++i){
    466         up[v][i] = up[up[v][i - 1]][i - 1];
    467     }
    468     for(int u: sl[v]){
    469         if(u == p) continue;
    470         precalc(u, v);
    471     }
    472 }
    473 
    474 int lca(int u, int v){
    475     if(d[u] < d[v]){
    476         swap(u, v);
    477     }
    478     for(int cur = sz; cur >= 0; --cur){
    479         if (d[u] - (1 << cur) >= d[v]) {
    480             u = up[u][cur];
    481         }
    482     }
    483     for(int cur = sz; cur >= 0; --cur){
    484         if (up[u][cur] != up[v][cur]) {
    485             u = up[u][cur];
    486             v = up[v][cur];
    487         }
    488     }
    489     return u == v ? u : up[u][0];
    490 }
    491 
    492 void solve(){
    493     cin >> n;
    494     sz = 0;
    495     while ((1 << sz) < n) sz++;
    496     d.assign(n, -1);
    497     up.assign(n, vector<int>(sz + 1));
    498     sl.assign(n, vector<int>(0));
    499     for(int i = 1; i < n; ++i){
    500         int u, v;
    501         cin >> u >> v;
    502         sl[--u].push_back(--v);
    503         sl[v].push_back(u);
    504     }
    505     precalc(0, 0);
    506     int q;
    507     cin >> q;
    508     for(; q; --q){
    509         int k;
    510         cin >> k;
    511         vector<int> p(k);
    512         for(int &e: p) {
    513             cin >> e;
    514             --e;
    515         }
    516         sort(all(p), [](int a, int b) {
    517             return d[a] > d[b];
    518         });
    519         vector<bool> used(k);
    520         for(int i = 0; i < k; ++i){
    521             if(lca(p[0], p[i]) == p[i]) used[i] = true;
    522         }
    523         int f = 0;
    524         while (f < k && used[f]) f++;
    525         if(f == k){
    526             cout << "YES\n";
    527             continue;
    528         }
    529         bool ans = true;
    530         for(int i = f; i < k; ++i){
    531             if(lca(p[f], p[i]) == p[i]) used[i] = true;
    532         }
    533         for(bool e: used){
    534             ans &= e;
    535         }
    536         ans &= d[lca(p[0], p[f])] <= d[p.back()];
    537         if(ans) cout << "YES\n";
    538         else cout << "NO\n";
    539     }
    540 }
    541 
    542 bool multi = false;
    543 
    544 signed main() {
    545     int t = 1;
    546     if (multi)cin >> t;
    547     for (; t; --t) {
    548         solve();
    549         //cout << endl;
    550     }
    551     return 0;
    552 }
    553 ```