codeforces-scrape

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

1388.md (11173B)


      1 Source: https://codeforces.com/blog/entry/80828
      2 
      3 [1388A - Captain Flint and Crew Recruitment](/contest/1388/problem/A "Codeforces Round 660 (Div. 2)")
      4 
      5 Idea: [Denisov](/profile/Denisov "Master Denisov")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Karavaev1101)**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 int main(){
     19     ios_base::sync_with_stdio(false);
     20     cin.tie(nullptr); cout.tie(nullptr);
     21 
     22     int q;
     23     cin >> q;
     24 
     25     while(q--){
     26         int n; cin >> n;
     27         if(n <= 30){
     28             cout << "NO" << endl;
     29         }
     30         else{
     31             cout << "YES" << endl;
     32             if(n == 36 || n == 40 || n == 44){
     33                 cout << 6 << ' ' << 10 << ' ' << 15 << ' ' << n - 31 << endl;
     34             }
     35             else{
     36                 cout << 6 << ' ' << 10 << ' ' << 14 << ' ' << n - 30 << endl;
     37             }
     38         }
     39     }
     40 }
     41 ```
     42 
     43 [1388B - Captain Flint and a Long Voyage](/contest/1388/problem/B "Codeforces Round 660 (Div. 2)")
     44 
     45 Idea: [karavaiev](/profile/karavaiev "Candidate Master karavaiev")
     46 
     47 **Tutorial**
     48 
     49 Tutorial is loading...
     50 
     51 **Solution (Karavaev1101)**
     52 
     53 ```
     54 #include <bits/stdc++.h>
     55 
     56 using namespace std;
     57 
     58 int main() {
     59     ios_base::sync_with_stdio(false);
     60     cin.tie(nullptr); cout.tie(nullptr);
     61 
     62     int q;
     63     cin >> q;
     64 
     65     while (q--) {
     66         int n; cin >> n;
     67         int x = (n + 3) / 4;
     68         for (int i = 0; i < n - x; ++i) {
     69             cout << 9;
     70         }
     71         for (int i = 0; i < x; ++i) {
     72             cout << 8;
     73         }
     74         cout << endl;
     75     }
     76 }
     77 ```
     78 
     79 [1388C - Uncle Bogdan and Country Happiness](/contest/1388/problem/C "Codeforces Round 660 (Div. 2)")
     80 
     81 Idea: [karavaiev](/profile/karavaiev "Candidate Master karavaiev")
     82 
     83 **Tutorial**
     84 
     85 Tutorial is loading...
     86 
     87 **Solution (Karavaev1101)**
     88 
     89 ```
     90 #include <bits/stdc++.h>
     91 
     92 using namespace std;
     93 
     94 const int N = 1e5 + 7;
     95 
     96 vector < int > gr[N];
     97 
     98 bool access = true;
     99 
    100 int p[N], h[N], a[N], g[N];
    101 
    102 void dfs(int v, int ancestor = -1) {
    103     a[v] = p[v];
    104     int sum_g = 0;
    105     for (int to : gr[v]) {
    106         if (to == ancestor) continue;
    107         dfs(to, v);
    108         sum_g += g[to];
    109         a[v] += a[to];
    110     }
    111     if ((a[v] + h[v]) % 2 == 0) {} // first
    112     else access = false;
    113     g[v] = (a[v] + h[v]) / 2;
    114     if (g[v] >= 0 && g[v] <= a[v]) {} // second
    115     else access = false;
    116     if (sum_g <= g[v]) {} // third
    117     else access = false;
    118 }
    119 
    120 int main() {
    121     ios_base::sync_with_stdio(false);
    122     cin.tie(nullptr); cout.tie(nullptr);
    123 
    124     int q;
    125     cin >> q;
    126 
    127     while (q--) {
    128         int n, m; cin >> n >> m;
    129         for (int i = 0; i < n; ++i) cin >> p[i];
    130         for (int i = 0; i < n; ++i) cin >> h[i];
    131         for (int i = 0; i < n - 1; ++i) {
    132             int a, b; cin >> a >> b;
    133             --a, --b;
    134             gr[a].push_back(b);
    135             gr[b].push_back(a);
    136         }
    137         dfs(0);
    138         cout << (access ? "YES" : "NO") << endl;
    139         access = true;
    140         for (int i = 0; i < n; ++i) gr[i].clear();
    141     }
    142 }
    143 ```
    144 
    145 [1388D - Captain Flint and Treasure](/contest/1388/problem/D "Codeforces Round 660 (Div. 2)")
    146 
    147 Idea: [Denisov](/profile/Denisov "Master Denisov")
    148 
    149 **Tutorial**
    150 
    151 Tutorial is loading...
    152 
    153 **Solution (Denisov)**
    154 
    155 ```
    156 #include <bits/stdc++.h>
    157 #define ll long long
    158 #define all(a) a.begin(),a.end()
    159 
    160 using namespace std;
    161 
    162 vector <vector <int> > edge;
    163 vector <ll> a;
    164 vector <int> b, used;
    165 vector <int> order[2];
    166 ll ans;
    167 inline void dfs (int v) {
    168     used[v] = 1;
    169     for (int to : edge[v]) {
    170         if (!used[to]) dfs(to);
    171     }
    172     ans += a[v];
    173     if (b[v] != -1 && a[v] > 0) {
    174         a[b[v]] += a[v];
    175     }
    176     if (a[v] > 0) {
    177         order[0].push_back(v);
    178     }
    179     else {
    180         order[1].push_back(v);
    181     }
    182 }
    183 inline void solve () {
    184     for (auto &i : edge) i.clear();
    185     edge.clear();
    186     a.clear();
    187     order[0].clear();
    188     order[1].clear();
    189     b.clear();
    190     used.clear();
    191     int n, x;
    192     cin >> n;
    193     edge.resize(n);
    194     a.resize(n);
    195     b.resize(n);
    196     for (auto &i : a) cin >> i;
    197     for (int i = 0; i < n; i++) {
    198         cin >> x;
    199         if (x != -1) {
    200             --x;
    201             edge[x].push_back(i);
    202         }
    203         b[i] = x;
    204     }
    205     ans = 0;
    206     used.assign(n, 0);
    207     for (int i = 0; i < n; i++) {
    208         if (!used[i]) {
    209             dfs(i);
    210         }
    211     }
    212     cout << ans << '\n';
    213     reverse(all(order[1]));
    214     for (auto &i : order[0]) cout << i + 1 << ' ';
    215     for (auto &i : order[1]) cout << i + 1 << ' ';
    216     cout << '\n';
    217 }
    218 main()
    219 {
    220     ios::sync_with_stdio(0);
    221     ios_base::sync_with_stdio(0);
    222     cin.tie(0);
    223     cout.tie(0);
    224     solve();
    225 }
    226 ```
    227 
    228 **Solution (Karavaev1101)**
    229 
    230 ```
    231 #include <bits/stdc++.h>
    232 
    233 #define Vanya Unstoppable
    234 
    235 using namespace std;
    236 
    237 int main() {
    238     ios_base::sync_with_stdio(false);
    239     cin.tie(nullptr); cout.tie(nullptr);
    240     
    241     int n;
    242     cin >> n;
    243     
    244     long long a[n];
    245     for (int i = 0; i < n; ++i) {
    246         cin >> a[i];
    247     }
    248     
    249     set < int > s;
    250     for (int i = 0; i < n; ++i) {
    251         s.insert(i);
    252     }
    253     
    254     int b[n];
    255     vector < int > sz(n);
    256     for (int i = 0; i < n; ++i) {
    257         cin >> b[i]; --b[i];
    258         if (b[i] == -2) continue;
    259         ++sz[b[i]];
    260         if (sz[b[i]] == 1) {
    261             s.erase(b[i]);
    262         }
    263     }
    264     
    265     long long sum = 0;
    266     vector < int > ans[2];
    267     
    268     while (!s.empty()) {
    269         int v = *s.begin();
    270         s.erase(s.begin());
    271         int w = b[v];
    272         sum += a[v];
    273         if (a[v] >= 0) {
    274             if (w >= 0) {
    275                 a[w] += a[v];
    276             }
    277             ans[0].push_back(v);
    278         } else {
    279             ans[1].push_back(v);
    280         }
    281         if (w >= 0) {
    282             --sz[w];
    283             if (sz[w] == 0) {
    284                 s.insert(w);
    285             }
    286         }
    287     }
    288     
    289     cout << sum << endl;
    290     for (int to : ans[0]) cout << to + 1 << ' ';
    291     
    292     reverse(ans[1].begin(), ans[1].end());
    293     
    294     for (int to : ans[1]) cout << to + 1 << ' ';
    295     cout << endl;
    296 }
    297 ```
    298 
    299 [1388E - Uncle Bogdan and Projections](/contest/1388/problem/E "Codeforces Round 660 (Div. 2)")
    300 
    301 Idea: [perekopskiy](/profile/perekopskiy "International Master perekopskiy")
    302 
    303 **Tutorial**
    304 
    305 Tutorial is loading...
    306 
    307 **Solution (perekopskiy)**
    308 
    309 ```
    310 #include <bits/stdc++.h>
    311 
    312 #define pb push_back
    313 #define x first
    314 #define y second
    315 
    316 using namespace std;
    317 
    318 const int N = 1e5 + 10;
    319 const double eps = 1e-9;
    320 
    321 double xl[N], xr[N], y[N], pi = acos(-1), mn_x, mx_x;
    322 int ind_l, ind_r;
    323 
    324 double point_pr(double x, double y, double ctg) {
    325     return x - y * ctg;
    326 }
    327 
    328 signed main() {
    329     ios_base::sync_with_stdio(0);
    330     cin.tie(0);
    331     cout.tie(0);
    332     int n;
    333     vector<pair<double, int> > q;
    334     vector<pair<double, pair<int, int> > > events, prom_left, prom_right;
    335     cin >> n;
    336     pair<double, double> mx, mn;
    337     mx = {-1.0, -1.0};
    338     mn = {2e9, 2e9};
    339     mn_x = 2e9;
    340     mx_x = -2e9;
    341     for(int i = 0; i < n; ++i) {
    342         cin >> xl[i] >> xr[i] >> y[i];
    343 
    344         if(xl[i] < mn_x) {
    345             mn_x = xl[i];
    346         }
    347         if(xr[i] > mx_x) {
    348             mx_x = xr[i];
    349         }
    350 
    351         if(mx.y < y[i]) {
    352             mx.y = y[i];
    353             mx.x = xl[i];
    354             ind_l = i;
    355         }
    356         else if(mx.y == y[i] && mx.x > xl[i]) {
    357             mx.y = y[i];
    358             mx.x = xl[i];
    359             ind_l = i;
    360         }
    361 
    362         if(mn.y > y[i]) {
    363             mn.y = y[i];
    364             mn.x = xl[i];
    365             ind_r = i;
    366         }
    367         else if(mn.y == y[i] && mn.x < xl[i]) {
    368             mn.y = y[i];
    369             mn.x = xl[i];
    370             ind_r = i;
    371         }
    372     }
    373     double a1, a2;
    374     for(int i = 0; i < n; ++i) {
    375         for(int j = 0; j < n; ++j) {
    376             if(y[i] > y[j]) {
    377                 a1 = (xr[i] - xl[j]) / (y[i] - y[j]);
    378                 a2 = (xl[i] - xr[j]) / (y[i] - y[j]);
    379                 q.pb({a1, 1});
    380                 q.pb({a2, 2});
    381 
    382                 a1 = (xl[i] - xl[j]) / (y[i] - y[j]);
    383                 a2 = (xr[i] - xr[j]) / (y[i] - y[j]);
    384                 events.pb({a1, {i, j}});
    385                 events.pb({a2, {-i - 1, j}});
    386             }
    387         }
    388     }
    389 
    390     if(q.empty()) {
    391         cout << fixed << setprecision(9) << mx_x - mn_x << endl;
    392         return 0;
    393     }
    394 
    395     sort(q.rbegin(), q.rend());
    396     int cnt = 0;
    397     double last = 0;
    398     for(auto i : q) {
    399         if(i.y == 2) {
    400             --cnt;
    401             if(!cnt) {
    402                 events.pb({i.x, {-1e9, -1e9}});
    403             }
    404         }
    405         else {
    406             if(!cnt) {
    407                 events.pb({i.x, {-1e9, -1e9}});
    408             }
    409             ++cnt;
    410         }
    411     }
    412     sort(events.rbegin(), events.rend());
    413     double ans = 1e18, ang;
    414     last = -1e18;
    415     for(auto i : events) {
    416         if(i.y.x == i.y.y) {
    417             unordered_set<int> s;
    418             vector<int> to_check;
    419             for(auto j : prom_left) {
    420                 s.insert(j.y.x);
    421                 if(j.y.x == ind_l) {
    422                     to_check.pb(j.y.y);
    423                 }
    424             }
    425             prom_left.clear();
    426             for(auto j : to_check) {
    427                 if(!s.count(j)) {
    428                     ind_l = j;
    429                     break;
    430                 }
    431             }
    432             s.clear();
    433             to_check.clear();
    434 
    435             for(auto j : prom_right) {
    436                 s.insert(j.y.y);
    437                 if(j.y.y == ind_r) {
    438                     to_check.pb(-j.y.x - 1);
    439                 }
    440             }
    441             prom_right.clear();
    442             for(auto j : to_check) {
    443                 if(!s.count(j)) {
    444                     ind_r = j;
    445                     break;
    446                 }
    447             }
    448             s.clear();
    449             to_check.clear();
    450 
    451             double res = point_pr(xr[ind_r], y[ind_r], i.x) - point_pr(xl[ind_l], y[ind_l], i.x);
    452             if(ans > res) {
    453                 ans = res;
    454                 ang = i.x;
    455             }
    456         }
    457         else if(i.y.x < 0) {
    458             if(abs(i.x - last) > eps) {
    459                 unordered_set<int> s;
    460                 vector<int> to_check;
    461                 for(auto j : prom_right) {
    462                     s.insert(j.y.y);
    463                     if(j.y.y == ind_r) {
    464                         to_check.pb(-j.y.x - 1);
    465                     }
    466                 }
    467                 prom_right.clear();
    468                 for(auto j : to_check) {
    469                     if(!s.count(j)) {
    470                         ind_r = j;
    471                         break;
    472                     }
    473                 }
    474                 s.clear();
    475                 to_check.clear();
    476             }
    477             prom_right.pb(i);
    478         }
    479         else {
    480             if(abs(i.x - last) > eps) {
    481                 unordered_set<int> s;
    482                 vector<int> to_check;
    483                 for(auto j : prom_left) {
    484                     s.insert(j.y.x);
    485                     if(j.y.x == ind_l) {
    486                         to_check.pb(j.y.y);
    487                     }
    488                 }
    489                 prom_left.clear();
    490                 for(auto j : to_check) {
    491                     if(!s.count(j)) {
    492                         ind_l = j;
    493                         break;
    494                     }
    495                 }
    496                 s.clear();
    497                 to_check.clear();
    498             }
    499             prom_left.pb(i);
    500         }
    501         last = i.x;
    502     }
    503     cout << fixed << setprecision(9) << ans << endl;
    504     return 0;
    505 }
    506 ```