codeforces-scrape

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

1994.md (8643B)


      1 Source: https://codeforces.com/blog/entry/131666
      2 
      3 Thanks for participation!
      4 
      5 [1994A - Diverse Game](/contest/1994/problem/A)
      6 
      7 **Editorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 using namespace std;
     16 
     17 int main() {
     18     cin.tie(nullptr)->sync_with_stdio(false);
     19 
     20     int tests;
     21     cin >> tests;
     22     while (tests--) {
     23         int n, m;
     24         cin >> n >> m;
     25         vector<vector<int>> a(n, vector<int>(m));
     26         for (auto &i: a) {
     27             for (auto &j: i) cin >> j;
     28         }
     29         if (n * m == 1) cout << "-1\n";
     30         else {
     31             for (int i = 0; i < n; ++i) {
     32                 for (int j = 0; j < m; ++j) {
     33                     cout << a[(i + 1) % n][(j + 1) % m] << ' ';
     34                 }
     35                 cout << '\n';
     36             }
     37         }
     38     }
     39 }
     40 ```
     41 
     42 [1994B - Fun Game](/contest/1994/problem/B)
     43 
     44 **Editorial**
     45 
     46 Tutorial is loading...
     47 
     48 **Code**
     49 
     50 ```
     51 #include<bits/stdc++.h>
     52 using namespace std;
     53 
     54 void solve() {
     55     int n;
     56     cin >> n;
     57     string s, t;
     58     cin >> s >> t;
     59     for (int i = 0; i < s.size() && s[i] == '0'; ++i) {
     60         if (t[i] != '0') {
     61             cout << "NO\n";
     62             return;
     63         }
     64     }
     65     cout << "YES\n";
     66 }
     67 
     68 int main() {
     69     int t;
     70     cin >> t;
     71     while (t--) solve();
     72 }
     73 ```
     74 
     75 [1994C - Hungry Games](/contest/1994/problem/C)
     76 
     77 **Editorial**
     78 
     79 Tutorial is loading...
     80 
     81 **Code**
     82 
     83 ```
     84 #include<bits/stdc++.h>
     85 using namespace std;
     86 
     87 using ll = long long;
     88 
     89 int main() {
     90     cin.tie(nullptr)->sync_with_stdio(false);
     91 
     92     int tests;
     93     cin >> tests;
     94     while (tests--) {
     95         int n;
     96         ll x;
     97         cin >> n >> x;
     98         vector<ll> a(n + 1);
     99         for (int i = 1; i <= n; ++i) cin >> a[i];
    100         partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
    101         vector<int> dp(n + 2);
    102         for (int i = n - 1; i >= 0; --i) {
    103             int q = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin();
    104             dp[i] = dp[q] + q - i - 1;
    105         }
    106         cout << accumulate(dp.begin(), dp.end(), 0ll) << '\n';
    107     }
    108 }
    109 ```
    110 
    111 [1994D - Funny Game](/contest/1994/problem/D)
    112 
    113 **Hint**
    114 
    115 Pigeonhole principle
    116 
    117 **Editorial**
    118 
    119 Tutorial is loading...
    120 
    121 **Code**
    122 
    123 ```
    124 #include<bits/stdc++.h>
    125 using namespace std;
    126 
    127 int main() {
    128     int tests;
    129     cin >> tests;
    130     while (tests--) {
    131         int n;
    132         cin >> n;
    133         vector<int> a(n);
    134         for (auto& i : a) cin >> i;
    135         vector<int> pos(n);
    136         iota(pos.begin(), pos.end(), 0);
    137         vector<pair<int, int>> ans;
    138         for (int i = n - 1; i; --i) {
    139             vector<int> occ(i, -1);
    140             for (auto j : pos) {
    141                 if (occ[a[j] % i] != -1) {
    142                     ans.emplace_back(j, occ[a[j] % i]);
    143                     pos.erase(find(pos.begin(), pos.end(), j));
    144                     break;
    145                 }
    146                 occ[a[j] % i] = j;
    147             }
    148         }
    149         reverse(ans.begin(), ans.end());
    150         cout << "YES\n";
    151         for (auto [x, y] : ans) cout << x + 1 << ' ' << y + 1 << '\n';
    152     }
    153 }
    154 ```
    155 
    156 [1994E - Wooden Game](/contest/1994/problem/E)
    157 
    158 **Hint**
    159 
    160 Solve for one tree
    161 
    162 **Hint.answer**
    163 
    164 Answer is size of tree
    165 
    166 **Hint.proof**
    167 
    168 Let sizes of deleted subtrees be $a_1, a_2, \ldots a_m$. We know that $a_1 + a_2 + \ldots + a_m = n$. Then we know that $a_1 | a_2 \ldots a_m \leq n$. To proof that lets see bits separately. It will add $1$ to result, if one of bits is $1$, $0$ otherwise, but this is not more than their sum.
    169 
    170 **Editorial**
    171 
    172 Tutorial is loading...
    173 
    174 **Code**
    175 
    176 ```
    177 #include<bits/stdc++.h>
    178 using namespace std;
    179 
    180 void solve() {
    181     int k;
    182     cin >> k;
    183     vector<int> a(k);
    184     for (int i = 0; i < k; ++i) {
    185         cin >> a[i];
    186         for (int j = 0; j < a[i] - 1; ++j) {
    187             int trash;
    188             cin >> trash;
    189         }
    190     }
    191     sort(a.begin(), a.end(), greater<>());
    192     int ans = 0;
    193     for (auto x : a) {
    194         for (int h = 23; h >= 0; --h) {
    195             int ca = ans >> h & 1, cx = x >> h & 1;
    196             if (cx == 0) continue;
    197             if (ca == 0) ans |= 1 << h;
    198             else {
    199                 ans |= (1 << h) - 1;
    200                 break;
    201             }
    202         }
    203     }
    204     cout << ans << '\n';
    205 }
    206 
    207 int main() {
    208     int t;
    209     cin >> t;
    210     while (t--) solve();
    211 }
    212 ```
    213 
    214 [1994F - Stardew Valley](/contest/1994/problem/F)
    215 
    216 **Editorial**
    217 
    218 Tutorial is loading...
    219 
    220 **Code**
    221 
    222 ```
    223 #include<bits/stdc++.h>
    224 using namespace std;
    225 
    226 int main() {
    227     cin.tie(nullptr)->sync_with_stdio(false);
    228 
    229     int tests;
    230     cin >> tests;
    231     while (tests--) {
    232         int n, m;
    233         cin >> n >> m;
    234         vector<vector<int>> black(n);
    235         vector<int> edg(m);
    236         vector<vector<int>> g(n);
    237         for (int i = 0; i < m; ++i) {
    238             int x, y, c;
    239             cin >> x >> y >> c;
    240             --x, --y;
    241             edg[i] = x ^ y;
    242             g[x].push_back(i);
    243             g[y].push_back(i);
    244             if (c == 0) {
    245                 black[x].push_back(i);
    246                 black[y].push_back(i);
    247             }
    248         }
    249         vector<int> deg(n);
    250         for (int i = 0; i < n; ++i) deg[i] = g[i].size() & 1;
    251         vector<bool> del(m, false), used(n, false);
    252         auto dfs = [&](auto dfs, int u) -> void {
    253             used[u] = true;
    254             for (auto id : black[u]) {
    255                 int to = edg[id] ^ u;
    256                 if (used[to]) continue;
    257                 dfs(dfs, to);
    258                 if (deg[to]) {
    259                     del[id] = true;
    260                     deg[to] ^= 1;
    261                     deg[u] ^= 1;
    262                 }
    263             }
    264         };
    265         bool ok = true;
    266         for (int i = 0; i < n; ++i) {
    267             if (used[i]) continue;
    268             dfs(dfs, i);
    269             ok &= !deg[i];
    270         }
    271         if (!ok) {
    272             cout << "NO\n";
    273             continue;
    274         }
    275         auto euler = [&](auto euler, int u) -> void {
    276             while (!g[u].empty()) {
    277                 int id = g[u].back();
    278                 g[u].pop_back();
    279                 int to = edg[id] ^ u;
    280                 if (del[id]) continue;
    281                 del[id] = true;
    282                 euler(euler, to);
    283             }
    284             cout << u + 1 << ' ';
    285         };
    286         cout << "YES\n";
    287         cout << m - accumulate(del.begin(), del.end(), 0) << '\n';
    288         euler(euler, 0);
    289         cout << '\n';
    290     }
    291 }
    292 ```
    293 
    294 [1994G - Minecraft](/contest/1994/problem/G)
    295 
    296 **Hint 1**
    297 
    298 Think of the most stupid solution you can do
    299 
    300 **Hint 2**
    301 
    302 Do memorization and some cuts
    303 
    304 **Hint 3**
    305 
    306 Done!
    307 
    308 **Editorial**
    309 
    310 Tutorial is loading...
    311 
    312 **Code**
    313 
    314 ```
    315 #include <bits/stdc++.h>
    316 
    317 using namespace std;
    318 
    319 int n, k;
    320 vector<vector<bool>> memo;
    321 string res;
    322 vector<int> cnt;
    323 string s;
    324 
    325 bool rec(int i, int cur) {
    326     if (i == k) {
    327         if (cur == 0) {
    328             return true;
    329         }
    330         return false;
    331     }
    332     if (memo[i][cur]) return false;
    333     memo[i][cur] = true;
    334     for (int c = 0; c < 2; ++c) {
    335         int q = cur;
    336         if (c == 0) q += cnt[i];
    337         else q += n - cnt[i];
    338         if ((q & 1) == s[i] - '0') {
    339             if (rec(i + 1, q / 2)) {
    340                 res += char(c + '0');
    341                 return true;
    342             }
    343         }
    344     }
    345     return false;
    346 }
    347 
    348 int main() {
    349     cin.tie(nullptr)->sync_with_stdio(false);
    350 
    351     int tests;
    352     cin >> tests;
    353     while (tests--) {
    354         cin >> n >> k;
    355         cin >> s;
    356         reverse(s.begin(), s.end());
    357         cnt = vector<int>(k);
    358         for (int i = 0; i < n; ++i) {
    359             string t;
    360             cin >> t;
    361             reverse(t.begin(), t.end());
    362             for (int j = 0; j < k; ++j) cnt[j] += t[j] - '0';
    363         }
    364         memo = vector<vector<bool>>(k, vector<bool>(n, false));
    365         res = "";
    366         rec(0, 0);
    367         if (res.empty()) cout << "-1\n";
    368         else cout << res << '\n';
    369     }
    370 }
    371 ```
    372 
    373 [1994H - Fortnite](/contest/1994/problem/H)
    374 
    375 **Editorial**
    376 
    377 Tutorial is loading...
    378 
    379 **Code**
    380 
    381 ```
    382 #include <bits/stdc++.h>
    383 using namespace std;
    384 
    385 using ll = long long;
    386 
    387 void solve() {
    388     cout << "? aa" << endl;
    389     int p, v[10];
    390     cin >> p; p--;
    391     cout << "? zzzzzzzzzz" << endl;
    392     int hsh, hsho;
    393     ll nom = 0, cnt = 1;
    394     cin >> hsh;
    395     hsho = hsh;
    396     hsh++;
    397     for (int i = 0; i < 10; i++) {
    398         nom += 26 * cnt;
    399         cnt *= p;
    400         v[i] = 26 - (hsh % p);
    401         hsh /= p;
    402     }
    403     string s;
    404     cnt = 1;
    405     ll ch = 0;
    406     for (int i = 0; i < 10; i++) {
    407         if (v[i] < 1) {
    408             v[i] = 26;
    409             v[i + 1]--;
    410         }
    411         ch += cnt * v[i];
    412         cnt *= p;
    413         s += 'a' + (v[i] - 1);
    414     }
    415     cout << "? " << s << endl;
    416     int ans;
    417     cin >> ans;
    418     cout << "! " << p << ' ' << ans + nom - ch - hsho << endl;
    419 }
    420 
    421 int32_t main() {
    422     int t;
    423     cin >> t;
    424     while (t--) {
    425         solve();
    426     }
    427 }
    428 ```