codeforces-scrape

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

2245.md (12428B)


      1 Source: https://codeforces.com/blog/entry/155232
      2 
      3 We hope you enjoyed the problems!
      4 
      5 **Rate the contest!**
      6 
      7 **Quality**
      8 
      9 * Excellent contest
     10 * Good contest
     11 * Average contest
     12 * Bad contest
     13 * Horrible contest
     14 
     15 **Difficulty**
     16 
     17 * Trivial contest
     18 * Easy contest
     19 * Average contest
     20 * Hard contest
     21 * Impossible contest
     22 
     23 [2245A - Кто сторожит свиносторожей?](/contest/2245/problem/A)
     24 
     25 **Solution**
     26 
     27 Tutorial is loading...
     28 
     29 **Code**
     30 
     31 ```
     32 for _ in range(int(input())):
     33     n, k = map(int, input().split())
     34     s = input()
     35     if k * 2 > n:
     36         print(-1)
     37         continue
     38     ans = 0
     39     for i in range(k):
     40         ans += int(s[i] != 'R') + int(s[n - i - 1] != 'L')
     41     print(ans)
     42 ```
     43 
     44 **Rate the problem!**
     45 
     46 **Quality**
     47 
     48 * Excellent problem
     49 * Good problem
     50 * Average problem
     51 * Bad problem
     52 * Horrible problem
     53 
     54 **Difficulty**
     55 
     56 * Trivial problem
     57 * Easy problem
     58 * Average problem
     59 * Hard problem
     60 * Impossible problem
     61 
     62 [2245B - Удалить и сконкатенировать](/contest/2245/problem/B)
     63 
     64 **Solution**
     65 
     66 Tutorial is loading...
     67 
     68 **Code**
     69 
     70 ```
     71 for _ in range(int(input())):
     72     n, c = map(int, input().split())
     73     a = list(map(int, input().split()))
     74     a.sort()
     75     for i in range(n):
     76         a[i] -= c
     77     for i in range(n // 2):
     78         a[i] = max(a[i], 0)
     79     print(sum(a))
     80 ```
     81 
     82 **Rate the problem!**
     83 
     84 **Quality**
     85 
     86 * Excellent problem
     87 * Good problem
     88 * Average problem
     89 * Bad problem
     90 * Horrible problem
     91 
     92 **Difficulty**
     93 
     94 * Trivial problem
     95 * Easy problem
     96 * Average problem
     97 * Hard problem
     98 * Impossible problem
     99 
    100 [2245C - MEXOR](/contest/2245/problem/C)
    101 
    102 **Solution**
    103 
    104 Tutorial is loading...
    105 
    106 **Code**
    107 
    108 ```
    109 for _ in range(int(input())):
    110     n, k = map(int, input().split())
    111     if n == 1:
    112         if k == 1:
    113             print("YES")
    114             print(0)
    115         else:
    116             print("NO")
    117         continue
    118     k ^= n
    119     if k.bit_length() > (n - 1).bit_length():
    120         print("NO")
    121         continue
    122     s = list()
    123     if 0 < k <= n - 1:
    124         s.append(k)
    125     elif k:
    126         s.append(n - 1)
    127         s.append((n - 1) ^ k)
    128     s.append(0)
    129     a = s[:]
    130     for i in range(n):
    131         if i not in s:
    132             a.append(i)
    133     print("YES")
    134     print(*reversed(a))
    135 ```
    136 
    137 **Rate the problem!**
    138 
    139 **Quality**
    140 
    141 * Excellent problem
    142 * Good problem
    143 * Average problem
    144 * Bad problem
    145 * Horrible problem
    146 
    147 **Difficulty**
    148 
    149 * Trivial problem
    150 * Easy problem
    151 * Average problem
    152 * Hard problem
    153 * Impossible problem
    154 
    155 [2245D1 - Построение массива (простая версия)](/contest/2245/problem/D1)
    156 
    157 **Solution**
    158 
    159 Tutorial is loading...
    160 
    161 **Code**
    162 
    163 ```
    164 #include <bits/stdc++.h>
    165 
    166 void solve() {
    167     int n, m;
    168     std::cin >> n >> m;
    169     std::vector b(n, std::vector<int>(n));
    170     while (m--) {
    171         int o, i, j;
    172         std::cin >> o >> i >> j;
    173         i--;
    174         j--;
    175         b[i][j] = b[j][i] = o;
    176     }
    177     std::vector<std::vector<int>> g(n);
    178     for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
    179         if (b[i][i] == 1 && b[j][j] == 2) {
    180             if (b[i][j] == 1) g[j].push_back(i);
    181             else g[i].push_back(j);
    182         }
    183     }
    184     std::vector<int> d(n), ans(n);
    185     for (int u = 0; u < n; u++) for (auto v : g[u]) d[v]++;
    186     int cnt = 0;
    187     std::queue<int> q;
    188     for (int u = 0; u < n; u++) if (!d[u]) q.push(u);
    189     while (!q.empty()) {
    190         int u = q.front();
    191         q.pop();
    192         if (b[u][u] == 1) ans[u] = ++cnt;
    193         else ans[u] = -(++cnt);
    194         for (auto v : g[u]) if (!--d[v]) q.push(v);
    195     }
    196     if (cnt == n) {
    197         for (int i = 0; i < n; i++) for (int j = i; j < n; j++) {
    198             if (b[i][j] == 1 && ans[i] + ans[j] < 0) return void(std::cout << "NO\n");
    199             if (b[i][j] == 2 && ans[i] + ans[j] >= 0) return void(std::cout << "NO\n");
    200         }
    201         std::cout << "YES\n";
    202         for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];
    203     } else {
    204         std::cout << "NO\n";
    205     }
    206 }
    207 
    208 int main() {
    209     std::ios::sync_with_stdio(0);
    210     std::cin.tie(0);
    211 
    212     int t;
    213     std::cin >> t;
    214     while (t--) solve();
    215 }
    216 ```
    217 
    218 **Rate the problem!**
    219 
    220 **Quality**
    221 
    222 * Excellent problem
    223 * Good problem
    224 * Average problem
    225 * Bad problem
    226 * Horrible problem
    227 
    228 **Difficulty**
    229 
    230 * Trivial problem
    231 * Easy problem
    232 * Average problem
    233 * Hard problem
    234 * Impossible problem
    235 
    236 [2245D2 - Построение массива (сложная версия)](/contest/2245/problem/D2)
    237 
    238 **Solution**
    239 
    240 Tutorial is loading...
    241 
    242 **Code**
    243 
    244 ```
    245 #include <bits/stdc++.h>
    246 
    247 void solve() {
    248     int n, m;
    249     std::cin >> n >> m;
    250     std::vector d(2, std::vector<int>(n));
    251     std::vector<std::vector<std::pair<int, int>>> g(n);
    252     while (m--) {
    253         int o, i, j;
    254         std::cin >> o >> i >> j;
    255         o--;
    256         i--;
    257         j--;
    258         g[i].emplace_back(j, o);
    259         g[j].emplace_back(i, o);
    260         d[o][i]++;
    261         d[o][j]++;
    262     }
    263     std::queue<int> q;
    264     std::vector<bool> vis(n);
    265     for (int i = 0; i < n; i++) if (d[0][i] == 0 || d[1][i] == 0) q.push(i), vis[i] = true;
    266     std::vector<std::pair<int, int>> t;
    267     while (!q.empty()) {
    268         int u = q.front();
    269         q.pop();
    270         if (d[0][u] == 0) t.emplace_back(u, -1);
    271         else t.emplace_back(u, 1);
    272         for (auto [v, o] : g[u]) if (!--d[o][v] && !vis[v]) {
    273             vis[v] = true;
    274             q.push(v);
    275         }
    276     }
    277     if (t.size() < n) return void(std::cout << "NO\n");
    278     std::cout << "YES\n";
    279     std::vector<int> ans(n);
    280     std::reverse(t.begin(), t.end());
    281     for (int i = 0; i < n; i++) ans[t[i].first] = (i + 1) * t[i].second;
    282     for (int i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];
    283 }
    284 
    285 int main() {
    286     std::ios::sync_with_stdio(0);
    287     std::cin.tie(0);
    288 
    289     int t;
    290     std::cin >> t;
    291     while (t--) solve();
    292 }
    293 ```
    294 
    295 **Rate the problem!**
    296 
    297 **Quality**
    298 
    299 * Excellent problem
    300 * Good problem
    301 * Average problem
    302 * Bad problem
    303 * Horrible problem
    304 
    305 **Difficulty**
    306 
    307 * Trivial problem
    308 * Easy problem
    309 * Average problem
    310 * Hard problem
    311 * Impossible problem
    312 
    313 [2245E - Том и Джерри](/contest/2245/problem/E)
    314 
    315 **Solution**
    316 
    317 Tutorial is loading...
    318 
    319 **Code**
    320 
    321 ```
    322 #include <bits/stdc++.h>
    323 
    324 void solve() {
    325     int n;
    326     std::cin >> n;
    327     std::vector<std::vector<int>> g(n);
    328     for (int i = 0; i < n - 1; i++) {
    329         int u, v;
    330         std::cin >> u >> v;
    331         u--;
    332         v--;
    333         g[u].push_back(v);
    334         g[v].push_back(u);
    335     }
    336     std::vector<bool> vis(n);
    337     long long ans = 0;
    338     int c = 0;
    339     auto dfs = [&](auto&& self, int u) -> void {
    340         vis[u] = true;
    341         for (auto v : g[u]) {
    342             if (g[v].size() & 1) ans += c++;
    343             else if (!vis[v]) self(self, v);
    344         }
    345     };
    346     for (int u = 0; u < n; u++) if (~g[u].size() & 1 && !vis[u]) {
    347         c = 0;
    348         dfs(dfs, u);
    349     }
    350     for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) ans += g[u].size() & g[v].size() & 1;
    351     std::cout << ans << "\n";
    352 }
    353 
    354 int main() {
    355     std::ios::sync_with_stdio(0);
    356     std::cin.tie(0);
    357 
    358     int t;
    359     std::cin >> t;
    360     while (t--) solve();
    361 }
    362 ```
    363 
    364 **Rate the problem!**
    365 
    366 **Quality**
    367 
    368 * Excellent problem
    369 * Good problem
    370 * Average problem
    371 * Bad problem
    372 * Horrible problem
    373 
    374 **Difficulty**
    375 
    376 * Trivial problem
    377 * Easy problem
    378 * Average problem
    379 * Hard problem
    380 * Impossible problem
    381 
    382 [2245F - Знакомо?](/contest/2245/problem/F)
    383 
    384 **Solution**
    385 
    386 Tutorial is loading...
    387 
    388 **Code**
    389 
    390 ```
    391 M = 998244353
    392 N = 501
    393 fac = [0] * N
    394 fac[0] = 1
    395 for i in range(1, N):
    396     fac[i] = fac[i - 1] * i % M
    397 inv = [0] * N
    398 inv[-1] = pow(fac[-1], M - 2, M)
    399 for i in range(N - 2, -1, -1):
    400     inv[i] = inv[i + 1] * (i + 1) % M
    401 def comb(n, k):
    402     if k < 0 or k > n:
    403         return 0
    404     return fac[n] * inv[k] % M * inv[n - k] % M
    405 
    406 for _ in range(int(input())):
    407     n = int(input())
    408     a = list(map(int, input().split()))
    409     if sum(max(0, v) for v in a) >= n:
    410         print(0)
    411         continue
    412     a.append(-1)
    413     f = [[[0] for _ in range(n)] for _ in range(n + 1)]
    414     g = [[0] * n for _ in range(n + 1)]
    415     for r in range(n):
    416         if a[r + 1] != -1:
    417             for l in range(n):
    418                 f[l][r] = [0] * (a[r + 1] + 1)
    419     for i in range(1, n + 1):
    420         f[i][i - 1][0] = 1
    421         g[i][i - 1] = 1
    422     def w(i, k):
    423         if i == k:
    424             return 1 if a[k] <= 0 else 0
    425         else:
    426             return f[i][k - 1][a[k]] if a[k] != -1 else g[i][k - 1]
    427     for l in range(n - 1, -1, -1):
    428         for r in range(l, n):
    429             if a[r + 1] == -1:
    430                 for k in range(l, r + 1):
    431                     g[l][r] = (g[l][r] + comb(r - l, k - l) * w(l, k) % M * g[k + 1][r] % M) % M
    432             else:
    433                 for c in range(1, a[r + 1] + 1):
    434                     for k in range(l, r + 1):
    435                         f[l][r][c] = (f[l][r][c] + comb(r - l, k - l) * w(l, k) % M * f[k + 1][r][c - 1] % M) % M
    436     print(w(0, n))
    437 ```
    438 
    439 **Rate the problem!**
    440 
    441 **Quality**
    442 
    443 * Excellent problem
    444 * Good problem
    445 * Average problem
    446 * Bad problem
    447 * Horrible problem
    448 
    449 **Difficulty**
    450 
    451 * Trivial problem
    452 * Easy problem
    453 * Average problem
    454 * Hard problem
    455 * Impossible problem
    456 
    457 [2245G - NPC-челлендж](/contest/2245/problem/G)
    458 
    459 **Solution**
    460 
    461 Tutorial is loading...
    462 
    463 **Code**
    464 
    465 ```
    466 #include <bits/stdc++.h>
    467 
    468 std::string query(const std::vector<int>& a) {
    469     std::cout << "? " << a.size();
    470     for (auto v : a) std::cout << " " << v + 1;
    471     std::cout << std::endl;
    472     std::string s;
    473     std::cin >> s;
    474     return s;
    475 }
    476 
    477 std::vector<int> work(const std::vector<int>& a, const std::vector<int>& b) {
    478     if (a.empty() || b.empty()) return {};
    479     std::vector<int> s;
    480     for (auto v : a) s.push_back(v);
    481     for (auto v : b) s.push_back(v);
    482     std::string t = query(s);
    483     std::vector<int> r;
    484     for (int i = 0; i < b.size(); i++) if (t[i + a.size()] == '0') r.push_back(b[i]);
    485     return r;
    486 }
    487 
    488 void solve() {
    489     int n;
    490     std::cin >> n;
    491     std::vector<std::vector<int>> g(n);
    492     auto find = [&](auto&& self, std::vector<int> a, std::vector<int> b) -> void {
    493         if (a.empty() || b.empty()) return;
    494         if (a.size() == 1) {
    495             for (auto v : b) g[v].push_back(a[0]), g[a[0]].push_back(v);
    496             return;
    497         }
    498         int m = a.size() / 2;
    499         std::vector a1(a.begin(), a.begin() + m), a2(a.begin() + m, a.end());
    500         auto p1 = work(a1, b);
    501         std::set<int> vis(p1.begin(), p1.end());
    502         std::vector<int> nb, p2;
    503         for (auto v : b) {
    504             if (vis.count(v)) nb.push_back(v);
    505             else p2.push_back(v);
    506         }
    507         self(self, a1, p1);
    508         for (auto v : work(a2, nb)) p2.push_back(v);
    509         self(self, a2, p2);
    510     };
    511     auto dfs = [&](auto&& self, std::vector<int> a) -> void {
    512         if (a.size() <= 1) return;
    513         std::string t = query(a);
    514         std::vector<int> p1, p2;
    515         for (int i = 0; i < a.size(); i++) {
    516             if (t[i] == '0') p2.push_back(a[i]);
    517             else p1.push_back(a[i]);
    518         }
    519         self(self, p2);
    520         std::vector<int> col(n, -1);
    521         std::vector<std::vector<int>> b(2);
    522         for (auto w : p2) if (col[w] == -1) {
    523             std::queue<int> q;
    524             q.push(w);
    525             col[w] = 0;
    526             while (!q.empty()) {
    527                 int u = q.front();
    528                 q.pop();
    529                 b[col[u]].push_back(u);
    530                 for (auto v : g[u]) if (col[v] == -1) {
    531                     col[v] = col[u] ^ 1;
    532                     q.push(v);
    533                 }
    534             }
    535         }
    536         for (int i = 0; i < 2; i++) {
    537             find(find, b[i], work(b[i], p1));
    538         }
    539     };
    540     std::vector<int> a(n);
    541     std::iota(a.begin(), a.end(), 0);
    542     dfs(dfs, a);
    543     std::cout << "!" << std::endl;
    544     for (int u = 0; u < n; u++) for (auto v : g[u]) if (v > u) std::cout << u + 1 << " " << v + 1 << std::endl;
    545 }
    546 
    547 int main() {
    548     std::ios::sync_with_stdio(0);
    549     std::cin.tie(0);
    550 
    551     int t;
    552     std::cin >> t;
    553     while (t--) solve();
    554 }
    555 ```
    556 
    557 **Rate the problem!**
    558 
    559 **Quality**
    560 
    561 * Excellent problem
    562 * Good problem
    563 * Average problem
    564 * Bad problem
    565 * Horrible problem
    566 
    567 **Difficulty**
    568 
    569 * Trivial problem
    570 * Easy problem
    571 * Average problem
    572 * Hard problem
    573 * Impossible problem
    574 
    575 [2245H - Видимые соединения](/contest/2245/problem/H)
    576 
    577 **Solution**
    578 
    579 Tutorial will be added after the first official (human) solve.
    580 
    581 **Code**
    582 
    583 **Rate the problem!**
    584 
    585 **Quality**
    586 
    587 * Excellent problem
    588 * Good problem
    589 * Average problem
    590 * Bad problem
    591 * Horrible problem
    592 
    593 **Difficulty**
    594 
    595 * Trivial problem
    596 * Easy problem
    597 * Average problem
    598 * Hard problem
    599 * Impossible problem