codeforces-scrape

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

1521.md (8991B)


      1 Source: https://codeforces.com/blog/entry/90477
      2 
      3 Thanks for participating!
      4 
      5 [1521A - Nastia and Nearly Good Numbers](/contest/1521/problem/A "Codeforces Round 720 (Div. 2)")
      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     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 a, b; cin >> a >> b;
     27         if (b == 1) {
     28             cout << "NO" << endl;
     29         } else {
     30             cout << "YES" << endl;
     31             cout << a << ' ' << a * (long long)b << ' ' << a * (long long)(b + 1) << endl;
     32         }
     33     }
     34 }
     35 ```
     36 
     37 [1521B - Nastia and a Good Array](/contest/1521/problem/B "Codeforces Round 720 (Div. 2)")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution**
     44 
     45 ```
     46 #include "bits/stdc++.h"
     47 
     48 using namespace std;
     49 
     50 int main() {
     51     ios_base::sync_with_stdio(false);
     52     cin.tie(nullptr); cout.tie(nullptr);
     53 
     54     int q;
     55     cin >> q;
     56 
     57     while (q--) {
     58         int n; cin >> n;
     59         int x = 1e9 + 7, pos = -1;
     60         for (int i = 0; i < n; ++i) {
     61             int a; cin >> a;
     62             if (a < x) x = a, pos = i;
     63         }
     64         cout << n - 1 << endl;
     65         for (int i = 0; i < n; ++i) {
     66             if (i == pos) continue;
     67             cout << pos + 1 << ' ' << i + 1 << ' ' << x << ' ' << x + abs(i - pos) << "\n";
     68         }
     69     }
     70 }
     71 ```
     72 
     73 [1521C - Nastia and a Hidden Permutation](/contest/1521/problem/C "Codeforces Round 720 (Div. 2)")
     74 
     75 **Tutorial**
     76 
     77 Tutorial is loading...
     78 
     79 **Solution 1**
     80 
     81 ```
     82 #include "bits/stdc++.h"
     83 
     84 using namespace std;
     85 
     86 int ask(int t, int i, int j, int x) {
     87     cout << "? " << t << ' ' << i + 1 << ' ' << j + 1 << ' ' << x << endl;
     88     int val; cin >> val;
     89     if (val == -1) exit(0);
     90     return val;
     91 }
     92 
     93 int main() {
     94     ios_base::sync_with_stdio(false);
     95     cin.tie(nullptr); cout.tie(nullptr);
     96 
     97     int q;
     98     cin >> q;
     99 
    100     while (q--) {
    101         int n; cin >> n;
    102         vector<int> p(n, -1);
    103         for (int i = 1; i < n; i += 2) {
    104             int pos1 = i - 1, pos2 = i;
    105             int val = ask(1, pos1, pos2, n - 1);
    106             if (val == n - 1) {
    107                 val = ask(1, pos2, pos1, n - 1);
    108                 if (val == n) {
    109                     p[pos1] = val;
    110                     p[pos2] = ask(2, pos2, pos1, 1);
    111                     continue;
    112                 }
    113             }
    114             int get = ask(1, pos1, pos2, val - 1);
    115             if (get == val) {
    116                 p[pos2] = val;
    117                 p[pos1] = ask(2, pos1, pos2, 1);
    118             }
    119             if (get == val - 1) {
    120                 p[pos1] = val;
    121                 p[pos2] = ask(2, pos2, pos1, 1);
    122             }
    123         }
    124         if (p.back() == -1) {
    125             vector<bool> us(n + 1);
    126             for (int i = 0; i < n - 1; ++i) {
    127                 us[p[i]] = true;
    128             }
    129             for (int i = 1; i <= n; ++i) {
    130                 if (!us[i]) {
    131                     assert(p[p.size() - 1] == -1);
    132                     p[p.size() - 1] = i;
    133                 }
    134             }
    135         }
    136         cout << "! ";
    137         for (int i = 0; i < n; ++i) {
    138             cout << p[i] << ' ';
    139         } cout << endl;
    140     }
    141 }
    142 ```
    143 
    144 [1521D - Nastia Plays with a Tree](/contest/1521/problem/D "Codeforces Round 720 (Div. 2)")
    145 
    146 **Tutorial**
    147 
    148 Tutorial is loading...
    149 
    150 **Solution**
    151 
    152 ```
    153 #include <bits/stdc++.h>
    154 
    155 using namespace std;
    156 
    157 const int N = 1e5 + 7;
    158 
    159 struct edge {
    160     int v, u;
    161 };
    162 
    163 vector<pair<edge, edge>> operations;
    164 
    165 int dp[N], answer = 0;
    166 
    167 bool isDeleted[N];
    168 
    169 vector<pair<int, int>> g[N];
    170 
    171 void dfs(int v, int p = -1) {
    172     int sz = (int)g[v].size() - (p != -1);
    173     for (auto to : g[v]) {
    174         if (to.first == p) continue;
    175         dfs(to.first, v);
    176         if (dp[to.first]) {
    177             --sz; ++answer;
    178             isDeleted[to.second] = true;
    179         }
    180     }
    181     if (sz >= 2) {
    182         dp[v] = true;
    183         for (auto to : g[v]) {
    184             if (to.first == p) continue;
    185             if (sz <= 2) break;
    186             if (!dp[to.first]) {
    187                 --sz; ++answer;
    188                 isDeleted[to.second] = true;
    189             }
    190         }
    191     }
    192 }
    193 
    194 vector<pair<int, int>> bamboos;
    195 
    196 bool used[N];
    197 
    198 vector<int> leaves;
    199 
    200 void dfs2(int v, int root) {
    201     used[v] = true;
    202     int numberOfChildren = 0;
    203     for (auto to : g[v]) {
    204         if (used[to.first] || isDeleted[to.second]) continue;
    205         ++numberOfChildren; dfs2(to.first, root);
    206     }
    207     if (v == root && numberOfChildren == 1) {
    208         leaves.push_back(v);
    209     } else if (!numberOfChildren) {
    210         leaves.push_back(v);
    211     }
    212 }
    213 
    214 void clear(int n) {
    215     answer = 0;
    216     for (int i = 0; i < n; ++i) {
    217         dp[i] = 0;
    218         g[i].clear();
    219         used[i] = isDeleted[i] = false;
    220     }
    221     bamboos.clear();
    222     operations.clear();
    223 }
    224 
    225 signed main() {
    226     ios_base::sync_with_stdio(false);
    227     cin.tie(nullptr); cout.tie(nullptr);
    228 
    229     int q;
    230     cin >> q;
    231 
    232     while (q--) {
    233         int n; cin >> n;
    234 
    235         for (int i = 0; i < n - 1; ++i) {
    236             int a, b; cin >> a >> b;
    237             --a; --b;
    238             g[a].push_back({b, i});
    239             g[b].push_back({a, i});
    240         }
    241 
    242         dfs(0);
    243         for (int i = 0; i < n; ++i) {
    244             if (!used[i]) {
    245                 dfs2(i, i);
    246                 assert((int)leaves.size() <= 2);
    247                 if ((int)leaves.size() == 2) {
    248                     bamboos.push_back({leaves[0], leaves[1]});
    249                 }
    250                 if ((int)leaves.size() == 1) {
    251                     bamboos.push_back({leaves.back(), leaves.back()});
    252                 }
    253                 leaves.clear();
    254             }
    255         }
    256 
    257         vector<edge> deletedEdges, addedEdges;
    258         for (int v = 0; v < n; ++v) {
    259             for (auto to : g[v]) {
    260                 if (isDeleted[to.second]) {
    261                     if (v < to.first) {
    262                         deletedEdges.push_back({v, to.first});
    263                     }
    264                 }
    265             }
    266         }
    267         for (int i = 1; i < (int)bamboos.size(); ++i) {
    268             addedEdges.push_back({bamboos[i - 1].second, bamboos[i].first});
    269         }
    270 
    271         assert(answer == (int)deletedEdges.size());
    272         assert((int)deletedEdges.size() == (int)addedEdges.size());
    273 
    274         for (int i = 0; i < answer; ++i) {
    275             operations.push_back({deletedEdges[i], addedEdges[i]});
    276         }
    277 
    278         assert(answer == (int)operations.size());
    279 
    280         cout << answer << endl;
    281         for (pair<edge, edge> to : operations) {
    282             cout << to.first.v + 1 << ' ' << to.first.u + 1 << ' ';
    283             cout << to.second.v + 1 << ' ' << to.second.u + 1 << endl;
    284         }
    285 
    286         clear(n);
    287     }
    288 }
    289 ```
    290 
    291 [1521E - Nastia and a Beautiful Matrix](/contest/1521/problem/E "Codeforces Round 720 (Div. 2)")
    292 
    293 **Tutorial**
    294 
    295 Tutorial is loading...
    296 
    297 **Solution**
    298 
    299 ```
    300 #include "bits/stdc++.h"
    301 
    302 using namespace std;
    303 
    304 int main() {
    305     ios_base::sync_with_stdio(false);
    306     cin.tie(nullptr); cout.tie(nullptr);
    307 
    308     int q;
    309     cin >> q;
    310 
    311     while (q--) {
    312         int m, k; cin >> m >> k;
    313 
    314         pair<int, int> a[k];
    315         for (int i = 0; i < k; ++i) {
    316             cin >> a[i].first, a[i].second = i + 1;
    317         } sort(a, a + k, greater<pair<int, int>>());
    318 
    319         int mx = a[0].first;
    320         for (int n = 1; n <= m; ++n) {
    321             // mx <= n * ceil(n / 2)
    322             if (mx > n * (long long)((n + 1) / 2)) continue;
    323             // m <= n ^ 2 - floor(n / 2) ^ 2
    324             if (m > n * (long long)n - (n / 2) * (long long)(n / 2)) continue;
    325 
    326             // answer = n
    327             vector<pair<int, int>> x, y, z;
    328             for (int i = 0; i < n; ++i) {
    329                 for (int j = 0; j < n; ++j) {
    330                     if ((i + j) % 2 == 1) {
    331                         if (i % 2 == 0) x.push_back({i, j});
    332                         else y.push_back({i, j});
    333                     } else {
    334                         if (i % 2 == 0) z.push_back({i, j});
    335                     }
    336                 }
    337             }
    338 
    339             int ans[n][n];
    340             for (int i = 0; i < n; ++i) {
    341                 for (int j = 0; j < n; ++j) {
    342                     ans[i][j] = 0;
    343                 }
    344             }
    345 
    346             for (int i = 0; i < k; ++i) {
    347                 vector<pair<int, int>> &cur = (x.empty() ? y : x);
    348                 while (a[i].first && !cur.empty()) {
    349                     pair<int, int> pos = cur.back();
    350                     ans[pos.first][pos.second] = a[i].second;
    351                     cur.pop_back(); --a[i].first;
    352                 }
    353                 while(a[i].first--) {
    354                     assert((int)z.size() > 0);
    355                     pair<int, int> pos = z.back();
    356                     ans[pos.first][pos.second] = a[i].second;
    357                     z.pop_back();
    358                 }
    359             }
    360 
    361             // print answer
    362             cout << n << endl;
    363             for (int i = 0; i < n; ++i) {
    364                 for (int j = 0; j < n; ++j) {
    365                     cout << ans[i][j] << ' ';
    366                 } cout << endl;
    367             }
    368 
    369             break;
    370         }
    371     }
    372 }
    373 ```