Sprague-Grundy Theorem

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute Grundy numbers on a DAG using DFS + memoization.
5
// Then, given a start node s, report whether it's winning and a winning move if it exists.
6
7
int n, m; // number of nodes and edges
8
vector<vector<int>> adj; // adjacency list: edges u -> v mean you can move from u to v
9
vector<int> grundy;      // memoized Grundy numbers, -1 means uncomputed
10
vector<int> state;       // 0=unvisited, 1=visiting, 2=done (cycle detection)
11
12
int dfs_grundy(int v) {
13
    if (grundy[v] != -1) return grundy[v];
14
    state[v] = 1;
15
    // Collect children's Grundy numbers
16
    // MEX of a set of size d is at most d, so allocate d+1
17
    int d = (int)adj[v].size();
18
    vector<int> childVals; childVals.reserve(d);
19
    for (int u : adj[v]) {
20
        if (state[u] == 1) {
21
            // Cycle detected. For classic SG, cycles are not allowed.
22
            // In contests, input usually guarantees acyclicity or termination.
23
            // We handle it conservatively by exiting.
24
            cerr << "Error: cycle detected (game not finite)." << '\n';
25
            exit(0);
26
        }
27
        int gu = dfs_grundy(u);
28
        childVals.push_back(gu);
29
    }
30
    vector<char> seen(d + 1, false);
31
    for (int g : childVals) if (g <= d) seen[g] = true;
32
    int mex = 0;
33
    while (mex <= d && seen[mex]) ++mex;
34
    state[v] = 2;
35
    return grundy[v] = mex;
36
}
37
38
int main() {
39
    ios::sync_with_stdio(false);
40
    cin.tie(nullptr);
41
42
    // Input format:
43
    // n m
44
    // m lines: u v (0-indexed), edge u -> v is a legal move
45
    // s (start node)
46
47
    if (!(cin >> n >> m)) return 0;
48
    adj.assign(n, {});
49
    for (int i = 0; i < m; ++i) {
50
        int u, v; cin >> u >> v; adj[u].push_back(v);
51
    }
52
    int s; cin >> s;
53
54
    grundy.assign(n, -1);
55
    state.assign(n, 0);
56
57
    for (int v = 0; v < n; ++v) if (grundy[v] == -1) dfs_grundy(v);
58
59
    cout << "Grundy(s) = " << grundy[s] << '\n';
60
    if (grundy[s] == 0) {
61
        cout << "Losing position for the first player.\n";
62
        return 0;
63
    }
64
65
    // Winning move: in a single component, aim for child with Grundy 0.
66
    for (int u : adj[s]) {
67
        if (grundy[u] == 0) {
68
            cout << "Winning move: " << s << " -> " << u << " (to Grundy 0)\n";
69
            return 0;
70
        }
71
    }
72
    // By SG theory, there must be a child with every t in [0, grundy[s)-1].
73
    // Fallback search for the smallest such t.
74
    for (int t = 0; t < grundy[s]; ++t) {
75
        for (int u : adj[s]) if (grundy[u] == t) {
76
            cout << "Winning move: " << s << " -> " << u << " (to Grundy " << t << ")\n";
77
            return 0;
78
        }
79
    }
80
81
    // Should not reach here in a well-formed finite impartial game.
82
    cout << "No winning move found (unexpected).\n";
83
    return 0;
84
}
85

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Given heap sizes, compute nim-sum, decide winner, and print one winning move.
5
int main() {
6
    ios::sync_with_stdio(false);
7
    cin.tie(nullptr);
8
9
    int n; // number of heaps
10
    if (!(cin >> n)) return 0;
11
    vector<long long> a(n);
12
    for (int i = 0; i < n; ++i) cin >> a[i];
13
14
    long long x = 0; // nim-sum (XOR of heap sizes)
15
    for (auto v : a) x ^= v;
16
17
    if (x == 0) {
18
        cout << "Second\n"; // losing for first player
19
        return 0;
20
    }
21
22
    cout << "First\n"; // winning for first player
23
24
    // Find a heap to reduce so that total XOR becomes 0.
25
    for (int i = 0; i < n; ++i) {
26
        long long target = a[i] ^ x; // desired new size for heap i
27
        if (target < a[i]) {
28
            long long remove = a[i] - target;
29
            cout << "Move: heap " << i << ", remove " << remove
30
                 << " (" << a[i] << " -> " << target << ")\n";
31
            return 0;
32
        }
33
    }
34
35
    // Should not happen if x != 0
36
    cout << "No winning move found (unexpected).\n";
37
    return 0;
38
}
39

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Game {
5
    int n, m, s;                // nodes, edges, start node
6
    vector<vector<int>> adj;    // adjacency list
7
    vector<int> grundy, state;  // memo and cycle detection
8
9
    int dfs(int v) {
10
        if (grundy[v] != -1) return grundy[v];
11
        state[v] = 1;
12
        int d = (int)adj[v].size();
13
        vector<int> child; child.reserve(d);
14
        for (int u : adj[v]) {
15
            if (state[u] == 1) {
16
                cerr << "Error: cycle detected in a component (not finite)." << '\n';
17
                exit(0);
18
            }
19
            child.push_back(dfs(u));
20
        }
21
        vector<char> seen(d + 1, false);
22
        for (int g : child) if (g <= d) seen[g] = true;
23
        int mex = 0; while (mex <= d && seen[mex]) ++mex;
24
        state[v] = 2;
25
        return grundy[v] = mex;
26
    }
27
28
    void compute_all() {
29
        grundy.assign(n, -1);
30
        state.assign(n, 0);
31
        for (int v = 0; v < n; ++v) if (grundy[v] == -1) dfs(v);
32
    }
33
};
34
35
int main() {
36
    ios::sync_with_stdio(false);
37
    cin.tie(nullptr);
38
39
    // Input format:
40
    // k (number of components)
41
    // For each component i=1..k:
42
    //   n m
43
    //   m lines: u v (0-indexed), edge u->v
44
    //   s (start node for that component)
45
46
    int k; if (!(cin >> k)) return 0;
47
    vector<Game> games(k);
48
    for (int i = 0; i < k; ++i) {
49
        cin >> games[i].n >> games[i].m;
50
        games[i].adj.assign(games[i].n, {});
51
        for (int e = 0; e < games[i].m; ++e) {
52
            int u, v; cin >> u >> v; games[i].adj[u].push_back(v);
53
        }
54
        cin >> games[i].s;
55
        games[i].compute_all();
56
    }
57
58
    // Compute XOR of start positions
59
    int X = 0;
60
    for (int i = 0; i < k; ++i) X ^= games[i].grundy[games[i].s];
61
62
    if (X == 0) {
63
        cout << "Second\n"; // losing for first player
64
        return 0;
65
    }
66
67
    cout << "First\n";
68
69
    // Find a component to move in: need g_i' = g_i XOR X < g_i
70
    for (int i = 0; i < k; ++i) {
71
        int gi = games[i].grundy[games[i].s];
72
        int target = gi ^ X;
73
        if (target < gi) {
74
            // Find a child s' of s with grundy = target
75
            int from = games[i].s;
76
            for (int u : games[i].adj[from]) {
77
                if (games[i].grundy[u] == target) {
78
                    cout << "Move in component " << i << ": " << from << " -> " << u
79
                         << " (Grundy " << gi << " -> " << target << ")\n";
80
                    return 0;
81
                }
82
            }
83
            // Should exist by SG theory; if not found due to input oddity, continue searching
84
        }
85
    }
86
87
    cout << "No winning move found (unexpected).\n";
88
    return 0;
89
}
90

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Game: Start with integer N. A move subtracts s in S if current >= s. Terminal at 0.
5
// Compute Grundy up to N and decide winner for given start N. Output a winning move if exists.
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int N, K; // maximum number and size of move set
12
    // Input: N K
13
    // Next line: K distinct positive integers s in S
14
    if (!(cin >> N >> K)) return 0;
15
    vector<int> S(K);
16
    for (int i = 0; i < K; ++i) cin >> S[i];
17
    sort(S.begin(), S.end());
18
19
    vector<int> g(N + 1, 0); // g[0] = 0 by definition
20
    // DP from 1..N
21
    for (int x = 1; x <= N; ++x) {
22
        // Child Grundy values from x - s for all s in S with s <= x
23
        int d = 0; // at most K moves contribute
24
        // For MEX, allocate size up to number of children + 1
25
        vector<int> child;
26
        child.reserve(S.size());
27
        for (int s : S) {
28
            if (s > x) break;
29
            child.push_back(g[x - s]);
30
        }
31
        vector<char> seen((int)child.size() + 1, false);
32
        for (int val : child) if (val <= (int)child.size()) seen[val] = true;
33
        int mex = 0; while (mex <= (int)child.size() && seen[mex]) ++mex;
34
        g[x] = mex;
35
    }
36
37
    cout << "Grundy[" << N << "] = " << g[N] << '\n';
38
    if (g[N] == 0) {
39
        cout << "Second\n"; // losing for first player
40
    } else {
41
        cout << "First\n";
42
        // Find winning move: aim for child with Grundy 0
43
        for (int s : S) {
44
            if (s <= N && g[N - s] == 0) {
45
                cout << "Winning move: subtract " << s << " (" << N << " -> " << (N - s) << ")\n";
46
                break;
47
            }
48
        }
49
    }
50
51
    return 0;
52
}
53