Hướng giải của Nim có gộp đống

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải: Nim có gộp đống

Phân tích

Đây là trò chơi Nim mở rộng. Khi có thể gộp đống, Grundy của đống kích thước \(a\) là \(a\) nếu \(a\) lẻ, \(a-1\) nếu \(a\) chẵn (hoặc ngược lại tùy biến thể). Phân tích: nếu có \(N\) lẻ và tất cả \(a_i = 1\) thì First thắng. Tổng quát: XOR các \(a_i\) sau khi biến đổi.

Code mẫu C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    long long x = 0;
    for (int i = 0; i < N; i++) {
        long long a; cin >> a;
        // Grundy cho trò chơi có gộp đống: a lẻ -> a, a chẵn -> a-1
        if (a % 2 == 0) a--;
        x ^= a;
    }
    cout << (x ? "First" : "Second") << endl;
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.