Codeforces Round 959 (Div. 1 + Div. 2) editorial

Revision en5, by zwezdinv, 2024-07-18 19:22:17

Thanks for participation!

1994A - Diverse Game

Editorial
Code

1994B - Fun Game

Editorial
Code

1994C - Hungry Games

Editorial
Code

1994D - Funny Game

Hint

Editorial

Tutorial is loading...

Code

include<bits/stdc++.h>

using namespace std;

int main() { int tests; cin >> tests; while (tests--) { int n; cin >> n; vector a(n); for (auto& i : a) cin >> i; vector pos(n); iota(pos.begin(), pos.end(), 0); vector<pair<int, int>> ans; for (int i = n — 1; i; --i) { vector occ(i, -1); for (auto j : pos) { if (occ[a[j] % i] != -1) { ans.emplace_back(j, occ[a[j] % i]); pos.erase(find(pos.begin(), pos.end(), j)); break; } occ[a[j] % i] = j; } } reverse(ans.begin(), ans.end()); cout << "YES\n"; for (auto [x, y] : ans) cout << x + 1 << ' ' << y + 1 << '\n'; } } ~~~~~

1994E - Wooden Game

Hint

Hint.answer

Hint.proof

Editorial

Tutorial is loading...

Code

include<bits/stdc++.h>

using namespace std;

void solve() { int k; cin >> k; vector a(k); for (int i = 0; i < k; ++i) { cin >> a[i]; for (int j = 0; j < a[i] — 1; ++j) { int trash; cin >> trash; } } sort(a.begin(), a.end(), greater<>()); int ans = 0; for (auto x : a) { for (int h = 23; h >= 0; --h) { int ca = ans >> h & 1, cx = x >> h & 1; if (cx == 0) continue; if (ca == 0) ans |= 1 << h; else { ans |= (1 << h) — 1; break; } } } cout << ans << '\n'; }

int main() { int t; cin >> t; while (t--) solve(); } ~~~~~

1994F - Stardew Valley

Editorial

Tutorial is loading...

Code

include<bits/stdc++.h>

using namespace std;

int main() { cin.tie(nullptr)->sync_with_stdio(false);

int tests;
cin >> tests;
while (tests--) {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> black(n);
    vector<int> edg(m);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        --x, --y;
        edg[i] = x ^ y;
        g[x].push_back(i);
        g[y].push_back(i);
        if (c == 0) {
            black[x].push_back(i);
            black[y].push_back(i);
        }
    }
    vector<int> deg(n);
    for (int i = 0; i < n; ++i) deg[i] = g[i].size() & 1;
    vector<bool> del(m, false), used(n, false);
    auto dfs = [&](auto dfs, int u) -> void {
        used[u] = true;
        for (auto id : black[u]) {
            int to = edg[id] ^ u;
            if (used[to]) continue;
            dfs(dfs, to);
            if (deg[to]) {
                del[id] = true;
                deg[to] ^= 1;
                deg[u] ^= 1;
            }
        }
    };
    bool ok = true;
    for (int i = 0; i < n; ++i) {
        if (used[i]) continue;
        dfs(dfs, i);
        ok &= !deg[i];
    }
    if (!ok) {
        cout << "NO\n";
        continue;
    }
    auto euler = [&](auto euler, int u) -> void {
        while (!g[u].empty()) {
            int id = g[u].back();
            g[u].pop_back();
            int to = edg[id] ^ u;
            if (del[id]) continue;
            del[id] = true;
            euler(euler, to);
        }
        cout << u + 1 << ' ';
    };
    cout << "YES\n";
    cout << m - accumulate(del.begin(), del.end(), 0) << '\n';
    euler(euler, 0);
    cout << '\n';
}

} ~~~~~

1994G - Minecraft

Hint 1

Hint 2

Hint 3

Editorial

Tutorial is loading...

Code

include <bits/stdc++.h>

using namespace std;

int n, k; vector<vector> memo; string res; vector cnt; string s;

bool rec(int i, int cur) { if (i == k) { if (cur == 0) { return true; } return false; } if (memo[i][cur]) return false; memo[i][cur] = true; for (int c = 0; c < 2; ++c) { int q = cur; if (c == 0) q += cnt[i]; else q += n — cnt[i]; if ((q & 1) == s[i] — '0') { if (rec(i + 1, q / 2)) { res += char(c + '0'); return true; } } } return false; }

int main() { cin.tie(nullptr)->sync_with_stdio(false);

int tests;
cin >> tests;
while (tests--) {
    cin >> n >> k;
    cin >> s;
    reverse(s.begin(), s.end());
    cnt = vector<int>(k);
    for (int i = 0; i < n; ++i) {
        string t;
        cin >> t;
        reverse(t.begin(), t.end());
        for (int j = 0; j < k; ++j) cnt[j] += t[j] - '0';
    }
    memo = vector<vector<bool>>(k, vector<bool>(n, false));
    res = "";
    rec(0, 0);
    if (res.empty()) cout << "-1\n";
    else cout << res << '\n';
}

} ~~~~~

1994H - Fortnite

Editorial

Tutorial is loading...

Code

include <bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() { cout << "? aa" << endl; int p, v[10]; cin >> p; p--; cout << "? zzzzzzzzzz" << endl; int hsh, hsho; ll nom = 0, cnt = 1; cin >> hsh; hsho = hsh; hsh++; for (int i = 0; i < 10; i++) { nom += 26 * cnt; cnt *= p; v[i] = 26 — (hsh % p); hsh /= p; } string s; cnt = 1; ll ch = 0; for (int i = 0; i < 10; i++) { if (v[i] < 1) { v[i] = 26; v[i + 1]--; } ch += cnt * v[i]; cnt *= p; s += 'a' + (v[i] — 1); } cout << "? " << s << endl; int ans; cin >> ans; cout << "! " << p << ' ' << ans + nom — ch — hsho << endl; }

int32_t main() { int t; cin >> t; while (t--) { solve(); } } ~~~~~

Tags editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en13 English zwezdinv 2024-07-18 19:54:18 1 (published)
ru3 Russian zwezdinv 2024-07-18 19:50:24 1 (опубликовано)
ru2 Russian zwezdinv 2024-07-18 19:34:01 574 Первая редакция перевода на Русский
ru1 Russian zwezdinv 2024-07-18 19:31:03 9417 Первая редакция перевода на Русский (сохранено в черновиках)
en12 English zwezdinv 2024-07-18 19:27:01 1
en11 English zwezdinv 2024-07-18 19:26:18 72
en10 English zwezdinv 2024-07-18 19:25:38 1
en9 English zwezdinv 2024-07-18 19:25:03 188
en8 English zwezdinv 2024-07-18 19:23:51 6416
en7 English zwezdinv 2024-07-18 19:22:57 4 Tiny change: 'inciple\n<\spoiler>\n' -> 'inciple\n</spoiler>\n'
en6 English zwezdinv 2024-07-18 19:22:36 6417
en5 English zwezdinv 2024-07-18 19:22:17 6413
en4 English zwezdinv 2024-07-18 19:20:12 6221
en3 English zwezdinv 2024-07-18 19:17:18 807
en2 English zwezdinv 2024-07-18 19:12:32 5535
en1 English zwezdinv 2024-07-18 19:07:57 3137 Initial revision (saved to drafts)