Game Theory - Nim

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given pile sizes, print who wins under perfect play.
5
// If the first player is winning, also output an optimal move: (pile_index, stones_to_remove).
6
// Indices are 1-based in output.
7
8
int main() {
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    int n;
13
    if (!(cin >> n)) return 0;
14
    vector<unsigned long long> a(n);
15
    for (int i = 0; i < n; ++i) cin >> a[i];
16
17
    unsigned long long S = 0;
18
    for (auto v : a) S ^= v; // nim-sum
19
20
    if (S == 0) {
21
        cout << "Second\n"; // P-position: losing for player to move
22
        return 0;
23
    }
24
25
    // Find highest set bit of S
26
    int msb = 63 - __builtin_clzll(S); // valid for S != 0
27
28
    // Choose a pile with that bit set and compute target a[i]' = a[i] ^ S
29
    for (int i = 0; i < n; ++i) {
30
        if ( (a[i] >> msb) & 1ULL ) {
31
            unsigned long long target = a[i] ^ S; // strictly less than a[i]
32
            // Sanity: target must be < a[i]
33
            if (target < a[i]) {
34
                unsigned long long remove = a[i] - target; // positive
35
                cout << "First\n";
36
                cout << (i + 1) << " " << remove << "\n"; // remove 'remove' stones from pile (i+1)
37
                return 0;
38
            }
39
        }
40
    }
41
42
    // Control should never reach here if S != 0 and inputs are valid
43
    cout << "First\n";
44
    cout << 1 << " " << (a[0] ? a[0] : 0) << "\n";
45
    return 0;
46
}
47

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Supports Q updates of the form: set pile i to value x, and after each update prints the winner.
5
// Maintains global XOR S in O(1) per update.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int n, q;
12
    if (!(cin >> n >> q)) return 0;
13
    vector<unsigned long long> a(n);
14
    unsigned long long S = 0;
15
    for (int i = 0; i < n; ++i) {
16
        cin >> a[i];
17
        S ^= a[i];
18
    }
19
20
    while (q--) {
21
        int i;
22
        unsigned long long x;
23
        cin >> i >> x; // 1-based index
24
        --i;
25
        // Update S efficiently: remove old contribution, add new
26
        S ^= a[i];
27
        a[i] = x;
28
        S ^= a[i];
29
        cout << (S == 0 ? "Second" : "First") << '\n';
30
    }
31
32
    return 0;
33
}
34

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Misère Nim: last move loses. Rule:
5
// - If all piles are size 1, First wins iff number of piles is even.
6
// - Otherwise, use normal Nim rule (nim-sum != 0 => First wins).
7
8
int main() {
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    int T; cin >> T;
13
    while (T--) {
14
        int n; cin >> n;
15
        vector<unsigned long long> a(n);
16
        bool allOnes = true;
17
        unsigned long long S = 0;
18
        int cntOnes = 0;
19
        for (int i = 0; i < n; ++i) {
20
            cin >> a[i];
21
            S ^= a[i];
22
            if (a[i] != 1ULL) allOnes = false;
23
            if (a[i] == 1ULL) cntOnes++;
24
        }
25
        bool firstWins;
26
        if (allOnes) {
27
            // Special parity flip
28
            firstWins = (cntOnes % 2 == 0);
29
        } else {
30
            firstWins = (S != 0);
31
        }
32
        cout << (firstWins ? "First" : "Second") << '\n';
33
    }
34
35
    return 0;
36
}
37

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given a directed acyclic game graph (positions = nodes, edges = legal moves),
5
// and k tokens placed on starting nodes (independent subgames), compute the XOR
6
// of Grundy numbers to decide the winner under normal play.
7
8
// mex helper: returns smallest nonnegative integer not in the set
9
unsigned int mex(const vector<unsigned int>& vals) {
10
    // Using a boolean array sized to vals.size()+1 is enough
11
    vector<char> seen(vals.size() + 2, 0);
12
    for (auto v : vals) if (v < seen.size()) seen[v] = 1;
13
    for (unsigned int g = 0; g < seen.size(); ++g) if (!seen[g]) return g;
14
    return (unsigned int)seen.size();
15
}
16
17
int main() {
18
    ios::sync_with_stdio(false);
19
    cin.tie(nullptr);
20
21
    int n, m; // nodes, edges
22
    if (!(cin >> n >> m)) return 0;
23
    vector<vector<int>> adj(n);
24
    for (int i = 0; i < m; ++i) {
25
        int u, v; cin >> u >> v; // edge u -> v, 0-based
26
        adj[u].push_back(v);
27
    }
28
29
    int k; cin >> k;
30
    vector<int> start(k);
31
    for (int i = 0; i < k; ++i) cin >> start[i];
32
33
    // Compute Grundy numbers with DFS + memoization (DAG assumed)
34
    vector<int> state(n, 0); // 0=unvis,1=visiting,2=done
35
    vector<unsigned int> g(n, 0);
36
37
    function<unsigned int(int)> dfs = [&](int u) -> unsigned int {
38
        if (state[u] == 2) return g[u];
39
        if (state[u] == 1) {
40
            // In practice, handle cycles carefully; here we assume DAG.
41
            // Fallback: return 0 if unexpected cycle.
42
            return 0;
43
        }
44
        state[u] = 1;
45
        vector<unsigned int> nxt;
46
        nxt.reserve(adj[u].size());
47
        for (int v : adj[u]) nxt.push_back(dfs(v));
48
        unsigned int gu = mex(nxt);
49
        g[u] = gu;
50
        state[u] = 2;
51
        return gu;
52
    };
53
54
    unsigned int X = 0;
55
    for (int s : start) X ^= dfs(s);
56
57
    cout << (X ? "First" : "Second") << '\n';
58
    return 0;
59
}
60