Editorial for ptit054: Nhặt sỏi

Hiểu bài toán

Trò chơi là một biến thể của Nim (Misère Nim) với 3 piles sỏi ban đầu có số lượng lần lượt là 3, 4, 5. Người chơi thua cuộc nếu họ là người lấy đi viên sỏi cuối cùng. Người chơi trước (Daisy hoặc Louis) sẽ thực hiện một nước đi cụ thể (chọn pile và số lượng sỏi lấy đi). Dựa vào trạng thái sau nước đi đó, ta cần xác định người chơi nào sẽ giành chiến thắng nếu cả hai chơi tối ưu.

Quy tắc trò chơi:

• Mỗi lượt, người chơi chọn một pile và lấy từ 1 đến toàn bộ số sỏi trong pile đó.
• Người lấy viên sỏi cuối cùng thua.

Đầu vào:

• Tên người chơi trước.
• Chỉ số pile và số sỏi lấy đi.

Đầu ra:

• Tên người chiến thắng.

Các cách tiếp cận

Cách Xử lý Logic Trực tiếp (Luật Misère Nim)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    string first;
    cin >> first;
    int group, take;
    cin >> group >> take;

    // Trạng thái ban đầu của 3 piles
    int piles[4] = {0, 3, 4, 5};
    piles[group] -= take;

    // Xác định người chơi tiếp theo
    string next_player = (first == "Daisy" ? "Louis" : "Daisy");

    // Kiểm tra điều kiện thắng/thua cho người chơi tiếp theo
    int count_ones = 0;
    bool has_gt_1 = false;
    for (int i = 1; i <= 3; i++) {
        if (piles[i] == 1) count_ones++;
        if (piles[i] > 1) has_gt_1 = true;
    }

    bool next_win = false;

    if (!has_gt_1) {
        // Trường hợp Misère đặc biệt: Tất cả pile đều <= 1
        // Người chơi thắng nếu số số pile có sỏi là số lẻ (vì sẽ ép đối thủ lấy cuối)
        // Thực chất logic chuẩn của Misère Nim:
        // Nếu tất cả pile đều 0 hoặc 1:
        //   - Nếu số pile lẻ -> người sắp đi THẮG (đối thủ phải đi vào thế cuối)
        //   - Nếu số pile chẵn -> người sắp đi THUA
        if (count_ones % 2 != 0) next_win = true;
        else next_win = false;
    } else {
        // Trường hợp Nim thường: Tính Nim-sum
        int nim_sum = piles[1] ^ piles[2] ^ piles[3];
        if (nim_sum != 0) next_win = true;
        else next_win = false;
    }

    if (next_win) cout << next_player;
    else cout << first;

    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp dựa trên định lý toán học về trò chơi Misère Nim.

1. Khởi tạo mảng 3 piles: {3, 4, 5}.
2. Cập nhật pile được chọn dựa trên input.
3. Kiểm tra xem có pile nào có số lượng lớn hơn 1 hay không.
4. Nếu KHÔNG có pile nào > 1 (tức là tất cả đều 0 hoặc 1):
   • Đếm số pile có 1 viên sỏi.
   • Nếu số đó là số lẻ, người chơi sắp tới (next_player) sẽ thắng.
   • Nếu số đó là số chẵn, người chơi sắp tới sẽ thua.
5. Nếu CÓ pile > 1:
   • Tính Nim-sum (phép XOR) của cả 3 piles.
   • Nếu Nim-sum khác 0, người chơi sắp tới thắng.
   • Nếu Nim-sum bằng 0, người chơi sắp tới thua.
6. In ra tên người thắng cuộc.

Cách Giả lập (Simulate) - Sơ sài (Dựa vào code mẫu)

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    vector<int> soi = {3, 4, 5};
    vector<string> ten = {"Daisy", "Louis"};
    string x; cin >> x;
    string y = (x == ten[0]) ? ten[1] : ten[0];
    int a, b; cin >> a >> b;
    soi[a - 1] -= b;

    // Logic trong code mẫu bị thiếu phần else, nhưng ngụ ý xử lý
    int cnt_big = 0;
    for (int v : soi) if (v >= 2) cnt_big++;

    bool y_thua = false;
    if (cnt_big == 0) {
        int cnt_nonzero = 0;
        for (int v : soi) if (v == 1) cnt_nonzero++;
        if (cnt_nonzero % 2 == 0) y_thua = true;
    } 
    // Code mẫu bị truncate, nhưng logic chung là:
    // Nếu cnt_big > 0, dùng XOR.
    // Nếu XOR == 0, y_thua = true.

    // Giả lập logic hoàn chỉnh:
    int xr = 0;
    if (cnt_big > 0) {
        for (int v : soi) xr ^= v;
        if (xr == 0) y_thua = true;
    }

    if (y_thua) cout << x;
    else cout << y;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này về cơ bản là giống cách 1, chỉ khác cách tổ chức code. Tác giả sử dụng vector và tên biến tiếng Việt để dễ hiểu. Logic vẫn xoay quanh việc kiểm tra 'đơn giản hóa' (Misère) hay 'Nim thường' (Standard).

Điểm khác biệt:

• Sử dụng vector thay vì mảng cố định.
• Biến cnt_big dùng để phân loại trường hợp.

Phương pháp này vẫn hiệu quả vì độ phức tạp là hằng số, nhưng code mẫu ban đầu bị thiếu phần else (else xử lý XOR) nên có thể gây lỗi nếu copy y chang.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán này là biến thể Misère Nim. Trong Nim thường, người chơi muốn để lại thế XOR = 0 cho đối thủ. Trong Misère Nim (cuối cùng người lấy viên cuối thua), logic thay đổi khi tất cả các pile đều có kích thước 1 hoặc 0.
• Cần phân biệt rõ hai trường hợp chính:
  1. Có ít nhất một pile > 1: Áp dụng luật Nim thường (XOR khác 0 thì thắng).
  2. Tất cả pile đều <= 1: Áp dụng luật đếm số lượng pile (lẻ thì thắng, chẵn thì thua).

Lỗi thường gặp

• Quên kiểm tra trường hợp đặc biệt của Misère Nim (tất cả pile đều 1). Nếu chỉ dùng XOR không, kết quả sẽ sai (ví dụ: piles={1,1,1}, XOR=1 -> người sắp đi thắng, nhưng thực tế người sắp đi thua vì phải lấy 1 trong 3 pile, để lại 2 pile cho đối thủ).
• Sai lệch chỉ số pile: Input thường là 1-based (1, 2, 3), nhưng mảng code là 0-based. Cần trừ 1 khi truy cập mảng, hoặc khai báo mảng phụ.