codeforces-scrape

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

1714.md (8415B)


      1 Source: https://codeforces.com/blog/entry/105549
      2 
      3 [1714A - Everyone Loves to Sleep](/contest/1714/problem/A "Codeforces Round 811 (Div. 3)")
      4 
      5 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 #define int long long
     17 #define pb emplace_back
     18 #define mp make_pair
     19 #define x first
     20 #define y second
     21 #define all(a) a.begin(), a.end()
     22 #define rall(a) a.rbegin(), a.rend()
     23 
     24 typedef long double ld;
     25 typedef long long ll;
     26 
     27 using namespace std;
     28 
     29 mt19937 rnd(143);
     30 
     31 const int inf = 1e15;
     32 const int M = 1e9 + 7;
     33 const ld pi = atan2(0, -1);
     34 const ld eps = 1e-6;
     35 
     36 void solve(){
     37     int n;
     38     cin >> n;
     39     int time, h, m;
     40     cin >> h >> m;
     41     time = 60 * h + m;
     42     int ans = 24 * 60;
     43     for(int i = 0; i < n; ++i){
     44         cin >> h >> m;
     45         int t = 60 * h + m - time;
     46         if(t < 0) t += 24 * 60;
     47         ans = min(ans, t);
     48     }
     49     cout << ans / 60 << " " << ans % 60;
     50 }
     51 
     52 bool multi = true;
     53 
     54 signed main() {
     55     int t = 1;
     56     if (multi)cin >> t;
     57     for (; t; --t) {
     58         solve();
     59         cout << endl;
     60     }
     61     return 0;
     62 }
     63 ```
     64 
     65 [1714B - Remove Prefix](/contest/1714/problem/B "Codeforces Round 811 (Div. 3)")
     66 
     67 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
     68 
     69 **Tutorial**
     70 
     71 Tutorial is loading...
     72 
     73 **Solution**
     74 
     75 ```
     76 #include <bits/stdc++.h>
     77 
     78 using namespace std;
     79 
     80 #define forn(i, n) for (int i = 0; i < int(n); i++)
     81 
     82 int main() {
     83     int t;
     84     cin >> t;
     85     forn(tt, t) {
     86         int n;
     87         cin >> n;
     88         vector<int> a(n);
     89         forn(i, n)
     90             cin >> a[i];
     91         bool yes = false;
     92         set<int> c;
     93         for (int i = n - 1; i >= 0; i--) {
     94             if (c.count(a[i])) {
     95                 cout << i + 1 << endl;
     96                 yes = true;
     97                 break;
     98             }
     99             c.insert(a[i]);
    100         }
    101         if (!yes)
    102             cout << 0 << endl;
    103     }
    104 }
    105 ```
    106 
    107 [1714C - Minimum Varied Number](/contest/1714/problem/C "Codeforces Round 811 (Div. 3)")
    108 
    109 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    110 
    111 **Tutorial**
    112 
    113 Tutorial is loading...
    114 
    115 **Solution**
    116 
    117 ```
    118 #include <bits/stdc++.h>
    119 
    120 using namespace std;
    121 
    122 #define forn(i, n) for (int i = 0; i < int(n); i++)
    123 
    124 int main() {
    125     int t;
    126     cin >> t;
    127     forn(tt, t) {
    128         int s;
    129         cin >> s;
    130         string result;
    131         for (int d = 9; d >= 1; d--)
    132             if (s >= d) {
    133                 result = char('0' + d) + result;
    134                 s -= d;
    135             }
    136         cout << result << endl;
    137     }
    138 }
    139 ```
    140 
    141 [1714D - Color with Occurrences](/contest/1714/problem/D "Codeforces Round 811 (Div. 3)")
    142 
    143 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution**
    150 
    151 ```
    152 #include<bits/stdc++.h>
    153 #define len(s) (int)s.size()
    154 #define forn(i, n) for (int i = 0; i < int(n); i++)
    155 
    156 using namespace std;
    157 int ans = 0;
    158 bool ok = true;
    159 
    160 void Find(int a, int b, string &t, vector<string>&str, vector<pair<int, int>>&match){
    161     int Max = 0, id = -1, pos = -1;
    162     for(int i = a; i <= b; i++){
    163         for(int j = 0; j < len(str); j++){
    164             string s = str[j];
    165             if(i + len(s) > len(t) || i + len(s) <= b) continue;
    166             if(t.substr(i, len(s)) == s) {
    167                 if(i + len(s) > Max){
    168                     Max = i + len(s);
    169                     id = j;
    170                     pos = i;
    171                 }
    172             }
    173         }
    174     }
    175     if(id == -1) {
    176         ok = false;
    177         return;
    178     }
    179     else{
    180         match.emplace_back(id, pos);
    181         ans++;
    182         if(Max == len(t)) return;
    183         else Find(max(pos + 1, b +1), Max, t, str, match);
    184     }
    185 }
    186 
    187 void solve(){
    188     ans = 0;
    189     ok = true;
    190 
    191     string t;
    192     cin >> t;
    193     int n;
    194     cin >> n;
    195 
    196     vector<string>s(n);
    197     vector<pair<int, int>>match;
    198 
    199     forn(i, n) {
    200         cin >> s[i];
    201     }
    202 
    203     Find(0, 0, t, s, match);
    204     if(!ok) cout << "-1\n";
    205     else{
    206         cout << ans << endl;
    207         for(auto &p : match) cout << p.first + 1 << ' ' << p.second + 1 << endl;
    208     }
    209 
    210 }
    211 
    212 int main(){
    213     int q;
    214     cin >> q;
    215     while(q--){
    216         solve();
    217     }
    218     return 0;
    219 }
    220 ```
    221 
    222 [1714E - Add Modulo 10](/contest/1714/problem/E "Codeforces Round 811 (Div. 3)")
    223 
    224 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy")
    225 
    226 **Tutorial**
    227 
    228 Tutorial is loading...
    229 
    230 **Solution**
    231 
    232 ```
    233 #include <iostream>
    234 #include <vector>
    235 #include <algorithm>
    236 #include <set>
    237 #include <queue>
    238 
    239 using namespace std;
    240 
    241 int next(int x) {
    242     return x + x % 10;
    243 }
    244 
    245 void solve() {
    246     int n;
    247     cin >> n;
    248     vector<int> a(n);
    249     bool flag = false;
    250     for (int i = 0; i < n; ++i) {
    251         cin >> a[i];
    252         if (a[i] % 5 == 0) {
    253             flag = true;
    254             a[i] = next(a[i]);
    255         }
    256     }
    257     if (flag) {
    258         cout << (*min_element(a.begin(), a.end()) == *max_element(a.begin(), a.end()) ? "Yes": "No") << '\n';
    259     } else {
    260         bool flag2 = false, flag12 = false;
    261         for (int i = 0; i < n; ++i) {
    262             int x = a[i];
    263             while (x % 10 != 2) {
    264                 x = next(x);
    265             }
    266             if (x % 20 == 2) {
    267                 flag2 = true;
    268             } else {
    269                 flag12 = true;
    270             }
    271         }
    272         cout << ((flag2 & flag12) ? "No" : "Yes") << '\n';
    273     }
    274 }
    275 
    276 int main() {
    277     int t = 1;
    278     cin >> t;
    279     for (int it = 0; it < t; ++it) {
    280         solve();
    281     }
    282     return 0;
    283 }
    284 ```
    285 
    286 [1714F - Build a Tree and That Is It](/contest/1714/problem/F "Codeforces Round 811 (Div. 3)")
    287 
    288 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    289 
    290 **Tutorial**
    291 
    292 Tutorial is loading...
    293 
    294 **Solution**
    295 
    296 ```
    297 #include <bits/stdc++.h>
    298 
    299 using namespace std;
    300 
    301 #define forn(i, n) for (int i = 0; i < int(n); i++)
    302 
    303 int main() {
    304     int t;
    305     cin >> t;
    306     forn(tt, t) {
    307         int n;
    308         cin >> n;
    309         vector<int> d(3);
    310         forn(i, 3)
    311             cin >> d[i];
    312         int sum = d[0] + d[1] + d[2];
    313         if (sum % 2 == 0) {
    314             vector<int> w(3);
    315             forn(i, 3)
    316                 w[i] = sum / 2 - d[(i + 1) % 3];
    317             vector<int> sw(w.begin(), w.end());
    318             sort(sw.begin(), sw.end());
    319             if (sw[0] >= 0 && sw[1] >= 1) {
    320                 vector<pair<int,int>> edges;
    321                 int num = 3;
    322                 int center;
    323                 if (sw[0] == 0)
    324                     center = min_element(w.begin(), w.end()) - w.begin();
    325                 else
    326                     center = num++;
    327                 forn(i, 3) {
    328                     int before = center;
    329                     forn(j, w[i] - 1) {
    330                         edges.push_back({before, num});
    331                         before = num++;
    332                     }
    333                     if (w[i] > 0)
    334                         edges.push_back({before, i});
    335                 }
    336                 if (num <= n) {
    337                     while (num < n)
    338                         edges.push_back({center, num++});
    339                     cout << "YES" << endl;
    340                     for (auto& [u, v]: edges)
    341                         cout << u + 1 << " " << v + 1 << endl;
    342                     continue;
    343                 }
    344             }
    345         }
    346         cout << "NO" << endl;
    347     }
    348 }
    349 ```
    350 
    351 [1714G - Path Prefixes](/contest/1714/problem/G "Codeforces Round 811 (Div. 3)")
    352 
    353 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov")
    354 
    355 **Tutorial**
    356 
    357 Tutorial is loading...
    358 
    359 **Solution**
    360 
    361 ```
    362 #pragma GCC optimize("O3","unroll-loops")
    363 #pragma GCC target("avx2")
    364 #include <bits/stdc++.h>
    365 
    366 using namespace std;
    367 #define int long long
    368 
    369 const int maxn=2e5+5;
    370 vector<int> ch[maxn];
    371 int a[maxn];
    372 int b[maxn];
    373 int ans[maxn];
    374 vector<int> vb;
    375 int curb=0;
    376 int cura=0;
    377 
    378 void dfs(int x){
    379     curb+=b[x];
    380     cura+=a[x];
    381     vb.push_back(curb);
    382     ans[x]=upper_bound(vb.begin(),vb.end(),cura)-vb.begin();
    383     for(int v:ch[x]){
    384         dfs(v);
    385     }
    386     curb-=b[x];
    387     cura-=a[x];
    388     vb.pop_back();
    389 }
    390 int32_t main(){
    391     ios_base::sync_with_stdio(false);
    392     cin.tie(0);cout.tie(0);
    393     int t;
    394     cin>>t;
    395     while(t--){
    396         int n;cin>>n;
    397         for(int i=0;i<n;++i) ch[i].clear();
    398         for(int i=1;i<n;++i){
    399             int pr,a1,b1;
    400             cin>>pr>>a1>>b1;
    401             --pr;
    402             ch[pr].push_back(i);
    403             a[i]=a1;
    404             b[i]=b1;
    405         }
    406         dfs(0);
    407         for(int i=1;i<n;++i) cout<<ans[i]-1<<' ';
    408         cout<<'\n';
    409     }
    410     return 0;
    411 }
    412 ```