C++에서 숫자를 선택하여 합계의 절대 차이를 기반으로 게임의 승자를 예측

이 문제에서는 n개의 숫자 배열이 제공됩니다. 그리고 두 명의 플레이어 X와 Y가 있습니다. 우리의 임무는 게임의 승자를 예측하는 것입니다.

플레이어 X가 이기려면 X와 Y의 합계의 절대 차이가 4의 배수여야 합니다. 4로 나누어 떨어지지 않으면 Y가 승리합니다. 플레이어 X가 게임을 시작합니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

Input: a[] = {3 6 9 12}
Output: X
Explaination:
X selects 3 and 6
Y selects 12 and 9
|3+6 - 12+9| = 12, 12 is a multiple of 4.

이 문제를 해결하기 위해 배열의 모든 요소가 4로 나누어 떨어지는지 확인하고 숫자를 4로 나눌 때 찾은 나머지를 추적합니다. 모든 나머지의 발생이 짝수이면 X가 승리합니다. 즉, 절대 차이는 4로 나눌 수 있습니다.

모든 값 0, 1, 2,3에 대한 arr[i]%4의 개수는 짝수여야 합니다.

알고리즘 구현을 보여주는 프로그램,

예시

#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<<"Game Started!\n";
   if (playGame(a, n) == 1)
      cout << "X wins the Game";
   else
      cout << "Y wins the Game";
   return 0;
}

출력

Game Started!
X wins the Game