Game Theory - Advanced Games

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// We solve Win/Lose/Draw on a game graph that may have cycles and may be partizan.
5
// States are (position, player), player in {0,1}. Edges alternate turns.
6
// Input format (example):
7
// n m0 m1
8
// then m0 edges for player 0: u v meaning from (u,0) you can move to (v,1)
9
// then m1 edges for player 1: u v meaning from (u,1) you can move to (v,0)
10
// Positions are 0..n-1. A state with no outgoing edges is Losing for the player to move.
11
// Output: for each position, outcome for player 0 to move and player 1 to move.
12
13
int main(){
14
    ios::sync_with_stdio(false);
15
    cin.tie(nullptr);
16
17
    int n; int m0, m1; 
18
    if(!(cin >> n >> m0 >> m1)){
19
        return 0;
20
    }
21
    // Build edges on doubled graph: id = pos*2 + player
22
    int N = 2*n;
23
    vector<vector<int>> out(N), in(N);
24
    vector<int> outdeg(N, 0);
25
26
    auto id = [&](int pos, int pl){ return pos*2 + pl; };
27
28
    for(int i=0;i<m0;i++){
29
        int u,v; cin>>u>>v;
30
        int a = id(u,0), b = id(v,1);
31
        out[a].push_back(b);
32
        in[b].push_back(a);
33
    }
34
    for(int i=0;i<m1;i++){
35
        int u,v; cin>>u>>v;
36
        int a = id(u,1), b = id(v,0);
37
        out[a].push_back(b);
38
        in[b].push_back(a);
39
    }
40
    for(int s=0;s<N;s++) outdeg[s] = (int)out[s].size();
41
42
    // -1 unknown, 0 = Lose, 1 = Win, 2 = Draw
43
    vector<int> res(N, -1);
44
    deque<int> dq;
45
46
    // Initialize: states with no outgoing moves are Losing for the player to move
47
    for(int s=0;s<N;s++) if(outdeg[s]==0){ res[s]=0; dq.push_back(s); }
48
49
    // Retrograde propagation
50
    while(!dq.empty()){
51
        int s = dq.front(); dq.pop_front();
52
        for(int p: in[s]){
53
            if(res[p] != -1) continue; // already decided
54
            if(res[s] == 0){
55
                // If you can move to a Losing state for opponent, you are Winning
56
                res[p] = 1;
57
                dq.push_back(p);
58
            } else if(res[s] == 1){
59
                // All your moves lead to Winning states for opponent -> you may become Losing
60
                if(--outdeg[p] == 0){
61
                    res[p] = 0;
62
                    dq.push_back(p);
63
                }
64
            }
65
            // Draws are assigned at the end to undecided states
66
        }
67
    }
68
69
    for(int s=0;s<N;s++) if(res[s]==-1) res[s]=2; // Draw
70
71
    // Print results per position for both players
72
    auto nameOf = [&](int v){ return v==0?"Lose":(v==1?"Win":"Draw"); };
73
74
    for(int pos=0; pos<n; ++pos){
75
        cout << "pos " << pos << ": P0-" << nameOf(res[id(pos,0)])
76
             << ", P1-" << nameOf(res[id(pos,1)]) << "\n";
77
    }
78
    return 0;
79
}
80

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute Grundy numbers on an impartial DAG and the XOR over components.
5
// Input: n m, then m edges u->v (same for both players), and a partition of nodes into c components.
6
// For demonstration, we read a list of component roots and output their SG XOR.
7
8
int main(){
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    int n,m; 
13
    if(!(cin>>n>>m)) return 0;
14
    vector<vector<int>> g(n);
15
    vector<int> indeg(n,0);
16
    for(int i=0;i<m;i++){
17
        int u,v; cin>>u>>v;
18
        g[u].push_back(v);
19
        indeg[v]++;
20
    }
21
    // Topological order (Kahn)
22
    queue<int> q;
23
    for(int i=0;i<n;i++) if(indeg[i]==0) q.push(i);
24
    vector<int> topo; topo.reserve(n);
25
    while(!q.empty()){
26
        int u=q.front(); q.pop(); topo.push_back(u);
27
        for(int v: g[u]) if(--indeg[v]==0) q.push(v);
28
    }
29
    if((int)topo.size()!=n){
30
        cerr << "Graph has cycles; SG requires a DAG.\n";
31
        return 0;
32
    }
33
34
    vector<int> grundy(n,0);
35
    // Compute SG in reverse topological order so children are ready
36
    vector<int> seen; seen.reserve(64);
37
    for(int it=n-1; it>=0; --it){
38
        int u = topo[it];
39
        // gather children's grundy values
40
        int mx = 0;
41
        for(int v: g[u]) mx = max(mx, grundy[v]);
42
        vector<char> used(mx+2, false); // enough to hold mex up to mx+1
43
        for(int v: g[u]) used[grundy[v]] = true;
44
        int gval = 0; while(gval < (int)used.size() && used[gval]) ++gval;
45
        grundy[u] = gval;
46
    }
47
48
    // Read a set of k starting positions that form independent subgames
49
    int k; cin>>k;
50
    int xorsum = 0;
51
    for(int i=0;i<k;i++){ int s; cin>>s; xorsum ^= grundy[s]; }
52
    cout << "xor = " << xorsum << "\n";
53
    cout << (xorsum? "First": "Second") << " player wins\n";
54
55
    return 0;
56
}
57

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Staircase Nim (1-based stairs): you may move any positive number of stones
5
// from stair i (i>=2) to stair i-1. Last move wins (normal play).
6
// The invariant: XOR over odd-indexed stairs alone determines outcome.
7
// We also output a concrete winning move if one exists.
8
9
int main(){
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    int n; if(!(cin>>n)) return 0;
14
    vector<long long> a(n+1); // 1..n
15
    for(int i=1;i<=n;i++) cin>>a[i];
16
17
    long long xorsum = 0;
18
    for(int i=1;i<=n;i+=2) xorsum ^= a[i];
19
20
    if(xorsum==0){
21
        cout << "Second\n";
22
        return 0;
23
    }
24
    cout << "First\n";
25
26
    // Find a winning move: pick an odd i where decreasing a[i] makes XOR zero.
27
    // Let target = a[i] ^ xorsum, with target < a[i]. Move k = a[i]-target stones from i to i-1.
28
    for(int i=1;i<=n;i+=2){
29
        long long target = a[i] ^ xorsum;
30
        if(target < a[i]){
31
            long long k = a[i] - target; // move k stones from i to i-1
32
            cout << "move " << k << " from stair " << i << " to " << (i-1) << "\n";
33
            return 0;
34
        }
35
    }
36
    // Should never reach here if xorsum != 0
37
    return 0;
38
}
39

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Wythoff's Game: two heaps (a,b), a<=b; move: remove any positive from one heap,
5
// or remove the same positive from both. P-positions are (floor(k*phi), floor(k*phi^2)).
6
// We test if (a,b) is P and, if not, output one optimal target P-position.
7
8
static inline long long floordiv_long_double(long double x){
9
    long double fx = floor(x + 1e-12L); // protect against tiny negative eps
10
    return (long long)fx;
11
}
12
13
int main(){
14
    ios::sync_with_stdio(false);
15
    cin.tie(nullptr);
16
17
    long long a,b; if(!(cin>>a>>b)) return 0;
18
    if(a>b) swap(a,b);
19
20
    const long double phi = (1.0L + sqrtl(5.0L)) / 2.0L; // golden ratio
21
    long long k = b - a;
22
    long long ak = floordiv_long_double(k * phi);
23
    long long bk = ak + k; // floor(k*phi^2) but equal to ak + k
24
25
    bool isP = (a == ak && b == bk);
26
    cout << (isP? "Second\n" : "First\n");
27
28
    if(!isP){
29
        // Move to (ak, bk). We can always achieve this in one legal move.
30
        // If a > ak: remove (a - ak) from heap a. If b > bk: remove (b - bk) from heap b.
31
        // Otherwise, remove t from both heaps where t = a - ak = b - bk.
32
        long long ta = (a > ak ? a - ak : 0);
33
        long long tb = (b > bk ? b - bk : 0);
34
        if(ta && tb){
35
            // Should be equal; remove from both
36
            long long t = min(ta, tb);
37
            cout << "remove " << t << " from both\n";
38
        } else if(ta){
39
            cout << "remove " << ta << " from heap A\n";
40
        } else if(tb){
41
            cout << "remove " << tb << " from heap B\n";
42
        } else {
43
            // Rare due to rounding — adjust safely by searching nearby k
44
            // Fallback: try neighbor kb11 to counter rounding.
45
            for(long long dk: {-1LL,1LL}){
46
                long long kk = k + dk;
47
                if(kk<0) continue;
48
                long long a2 = floordiv_long_double(kk * phi);
49
                long long b2 = a2 + kk;
50
                if(a==a2 && b>=b2){ cout << "remove " << (b-b2) << " from heap B\n"; break; }
51
                if(b==b2 && a>=a2){ cout << "remove " << (a-a2) << " from heap A\n"; break; }
52
                long long t = a - a2; if(t>0 && b - b2 == t){ cout << "remove " << t << " from both\n"; break; }
53
            }
54
        }
55
    }
56
    return 0;
57
}
58