Hiểu bài toán

Trò chơi giữa Dr. Patel và con gái bắt đầu với một số nguyên dương N. Dr. Patel đi trước. Mỗi người chơi đến lượt mình sẽ làm một trong hai việc:

1. Nếu N là lũy thừa của 2 (tức là N = 2^X), họ chia N cho 2 (N = N / 2).
2. Nếu N không phải là lũy thừa của 2, họ trừ đi số 2^Y lớn nhất sao cho 2^Y < N (N = N - 2^Y). Người chơi thực hiện hành động khiến N trở bằng 1 sẽ giành chiến thắng ngay lập tức. Yêu cầu: Với số N ban đầu, hãy xác định xem người chơi thứ nhất (Dr. Patel) có thể thắng cuộc nếu chơi tối ưu hay không.

Phân tích trò chơi:

• Nếu N = 1: Dr. Patel đã thắng ngay (theo điều kiện 'ra 1').
• Nếu N là số chẵn và là lũy thừa của 2 (N = 2^k, k >= 1): Khi chia cho 2, ta được N' = 2^{k-1}. Nếu k=1, N'=1 và thắng ngay. Nếu k>1, trò chơi tiếp tục.
• Nếu N là số lẻ (nên không phải lũy thừa của 2): Phép toán là N = N - 2^Y. Vì N lẻ, bit 0 là 1, nên phép trừ không gây borrows vào các bit cao hơn. 2^Y là số chẵn (với Y>=1), nên N - 2^Y vẫn là số lẻ.
• Nếu N là số chẵn nhưng không phải lũy thừa của 2 (ví dụ 12 = 1100b): Phép toán là N = N - 2^Y. 2^Y là số chẵn. N - 2^Y có thể chia hết cho 2 hoặc không, tùy thuộc vào bit 1 bị xóa.

Quy luật chiến thắng (W/L Analysis):

• Gọi người chơi thua nếu ở lượt của họ, họ chỉ có thể đi đến thế cờ thắng cho đối thủ.
• N = 1: Thắng (Win).
• N = 2: Là 2^1. Phép chia cho 2 => 1 (Thắng). => Win.
• N = 3: Lẻ. Phép trừ 2 => 1 (Thắng cho người hiện tại). => Win.
• N = 4: 2^2. Phép chia => 2 (Thắng). => Win.
• N = 5: Lẻ. Phép trừ 2 => 3 (Win). Nếu đi tới 3, đối thủ thắng. => Lose.
• N = 6: Chẵn, không lũy thừa 2. 6 - 4 = 2 (Win). Nếu đi tới 2, đối thủ thắng. => Lose.
• N = 7: Lẻ. 7 - 4 = 3 (Win). => Lose.
• N = 8: 2^3. Chia => 4 (Win). => Win.

Mẫu hình xuất hiện:

• Các số 1, 2, 4, 8,... (lũy thừa của 2) đều là Win.
• Các số 5, 6, 7 là Lose.
• Các số 9, 10, 11, 12, 13, 14, 15: Ta cần kiểm tra.
• N = 9 (Lẻ): 9-8=1 (Win) => Win.
• N = 10 (Chẵn): 10-8=2 (Win) => Lose.
• N = 11 (Lẻ): 11-8=3 (Win) => Lose.
• N = 12 (Chẵn): 12-8=4 (Win) => Lose.
• N = 13 (Lẻ): 13-8=5 (Lose). Nếu đi tới 5, đối thủ thua => Mình thắng. => Win.
• N = 14 (Chẵn): 14-8=6 (Lose) => Win.
• N = 15 (Lẻ): 15-8=7 (Lose) => Win.

Kết luận: Vùng Lose nằm ở các số ngay trước lũy thừa của 2 và bao trùm một khoảng nhất định. Cụ thể:

• [5, 7] Lose (trước 8).
• [10, 12] Lose (trước 16).
• [13, 15] Win.

Công thức: Tìm k sao cho 2^k <= N < 2^{k+1}. Nếu N = 2^k: Win. Nếu N = 2^{k+1} - 1: Win. Nếu N là số lẻ: Win nếu N >= 2^k + 2^{k-1} + 1. Nếu N là số chẵn: Win nếu N >= 2^k + 2^{k-1}. Vùng Lose: Từ 2^k + 1 đến 2^k + 2^{k-1} - 1 (nếu chẵn) hoặc 2^k + 2^{k-1} (nếu lẻ). Tóm lại: Nếu N nằm trong khoảng [2^k + 1, 2^k + 2^{k-1}], người chơi sẽ thua (Lose). Ngoại lệ: Nếu N là số lẻ nằm tại 2^k + 2^{k-1} + 1, người chơi thắng (Win).

Tóm tắt ngắn gọn:

• Tìm k sao cho 2^k <= N < 2^{k+1}.
• Nếu N == 2^k hoặc N == 2^{k+1} - 1: YES (Thắng).
• Nếu N là số lẻ và N == 2^k + 2^{k-1} + 1: YES.
• Nếu N nằm trong khoảng [2^k + 1, 2^k + 2^{k-1}]: NO (Thua).
• Các trường hợp còn lại: YES.

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

Cách Mô phỏng (Simulation)

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

bool isPowerOfTwo(unsigned long long n) {
    return (n & (n - 1)) == 0;
}

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        unsigned long long N;
        cin >> N;
        int moves = 0;
        while (N > 1) {
            if (isPowerOfTwo(N)) {
                N /= 2;
            } else {
                // Tìm 2^Y < N
                int shift = 63 - __builtin_clzll(N);
                unsigned long long p = 1ULL << shift;
                N -= p;
            }
            moves++;
        }
        cout << "Case #" << t << ": " << (moves % 2 == 1 ? "yes" : "no") << "\n";
    }
    return 0;
}

• Time Complexity: O(log^2 N) mỗi test case.
• Space Complexity: O(1)

Cách tiếp cận này mô phỏng chính xác quy trình chơi game.

1. Kiểm tra xem N có phải là lũy thừa của 2 không.
2. Nếu có, chia N cho 2.
3. Nếu không, tìm số 2^Y lớn nhất nhỏ hơn N (có thể dùng hàm _builtinclzll hoặc bit scan reverse) và trừ nó đi.
4. Lặp lại cho đến khi N bằng 1.
5. Đếm số bước (moves). Nếu số bước là lẻ, Dr. Patel (người đi đầu) thắng. Nếu chẵn, thua.

Độ phức tạp: Vòng lặp chạy tối đa O(log N) lần. Mỗi lần tìm 2^Y mất O(log N) hoặc O(1) tùy cách code. Với N đến 2^64, cách này chạy khá nhanh cho một test case, nhưng với T=10^5 thì có thể TLE (Time Limit Exceeded) nếu không tối ưu tốt việc tìm 2^Y (ví dụ dùng loop tìm bit). Tuy nhiên, với _builtinclzll thì độ phức tạp là O(1) cho mỗi bước, tổng thể O(log N) mỗi test case. Với T=10^5 và N lớn, số bước trung bình khoảng 64, tổng thao tác ~6.4 triệu, đủ chạy.

Cách Phân tích quy luật (Mathematical Pattern)

#include <iostream>
#include <cmath>

using namespace std;

void solve() {
    unsigned long long n;
    cin >> n;

    // Tìm k sao cho 2^k <= n < 2^(k+1)
    // __builtin_clzll(n) trả về số bit 0 ở đầu.
    // Với unsigned long long 64-bit, shift = 63 - __builtin_clzll(n)
    int k = 63 - __builtin_clzll(n);
    unsigned long long p2k = 1ULL << k;
    unsigned long long p2k_1 = 1ULL << (k - 1);

    bool ans = true;

    // Nếu n chính xác là 2^k thì thắng
    if (n == p2k) {
        ans = true;
    }
    else if (n == (p2k << 1) - 1) { // n == 2^(k+1) - 1
        ans = true;
    }
    else {
        // Kiểm tra vùng thua [p2k + 1, p2k + p2k_1]
        unsigned long long start_lose = p2k + 1;
        unsigned long long end_lose = p2k + p2k_1;

        if (n >= start_lose && n <= end_lose) {
            ans = false;
        } else {
            ans = true;
        }
    }

    if (ans) cout << "yes\n";
    else cout << "no\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    if (cin >> t) {
        for (int i = 1; i <= t; i++) {
            cout << "Case #" << i << ": ";
            solve();
        }
    }
    return 0;
}

• Time Complexity: O(1) mỗi test case.
• Space Complexity: O(1)

Dựa vào phân tích trò chơi (W/L Analysis), chúng ta quan sát thấy một quy luật rõ ràng. Gọi k là số mũ lớn nhất sao cho 2^k <= N.

• Nếu N là lũy thừa của 2 (N = 2^k), người chơi thắng.
• Nếu N nằm trong khoảng từ 2^k + 1 đến 2^k + 2^{k-1}, người chơi thua.
• Các trường hợp còn lại (N lớn hơn 2^k + 2^{k-1} hoặc N là 2^{k+1}-1), người chơi thắng.

Công thức cụ thể:

1. Tìm k và giá trị 2^k.
2. Nếu N == 2^k -> YES.
3. Nếu N == 2^{k+1} - 1 -> YES.
4. Nếu N nằm trong khoảng [2^k + 1, 2^k + 2^{k-1}] -> NO.
5. Ngược lại -> YES.

Cách tiếp cận này loại bỏ hoàn toàn vòng lặp, chỉ cần vài phép toán bit và số học.

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

Bài học kinh nghiệm

• Trò chơi có thể được chia thành các vùng 'Win' và 'Lose' dựa trên giá trị của N so với các lũy thừa của 2.
• Vùng Lose nằm ở đầu mỗi khoảng [2^k, 2^{k+1}), cụ thể là từ 2^k + 1 đến 2^k + 2^{k-1}.
• Nếu N là số lẻ nằm ngay sau vùng Lose (2^k + 2^{k-1} + 1), người chơi sẽ thắng vì có thể đưa đối thủ vào vùng Lose.

Lỗi thường gặp

• Lầm tưởng rằng tất cả các số chẵn đều thắng hoặc thua theo một quy luật đơn giản.
• Quên kiểm tra điều kiện thắng đặc biệt cho các số lẻ ở ranh giới.
• Sử dụng số có dấu (signed) gây lỗi với các giá trị lớn gần 2^64.