Dự đoán người thắng trò chơi dựa trên hiệu tuyệt đối của tổng bằng cách chọn số trong C++

Trong bài toán này, chúng ta được cho một mảng n số. Và có hai người chơi X và Y. Nhiệm vụ của chúng ta là dự đoán người thắng của trò chơi.

Để người chơi X thắng, hiệu tuyệt đối của tổng các số do X và Y chọn phải là bội số của 4. Nếu không chia hết cho 4, thì Y thắng. Người chơi X bắt đầu trò chơi.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào: a[] = {3 6 9 12}
Đầu ra: X
Giải thích: X chọn 3 và 6
Y chọn 12 và 9
|3+6 - 12+9| = 12, 12 là bội số của 4.

Để giải quyết bài toán này, chúng ta sẽ kiểm tra xem mọi phần tử của mảng có chia hết cho 4 không và theo dõi dư tìm được khi chia một số cho 4. Nếu số lần xuất hiện của mọi dư là chẵn, thì X thắng. Tức là hiệu tuyệt đối chia hết cho 4.

Số lượng arr[i]%4 cho mọi giá trị 0, 1, 2, 3 phải là chẵn.

Chương trình minh họa triển khai thuật toán của chúng ta:

Ví dụ

#include <iostream>
using namespace std;
int playGame(int a[], int n) {
    int count[4] = {0,0,0,0};
    for (int i = 0; i < n; i++) {
        for(int j = 0; j<4;j++){
            if(a[i]%4 == j)
                count[j]++;
        }
    }
    if (count[0] % 2 == 0 && count[1] % 2 == 0 && count[2] % 2 == 0 && count[3] == 0)
        return 1;
    else
        return 2;
}
int main() {
    int a[] = { 4, 8, 5, 9 };
    int n = sizeof(a) / sizeof(a[0]);
    cout<<"Trò chơi bắt đầu!\n";
    if (playGame(a, n) == 1)
        cout << "X thắng trò chơi";
    else
        cout << "Y thắng trò chơi";
    return 0;
}

Kết quả

Trò chơi bắt đầu! X thắng trò chơi