#28155 Splitting Pairs

 

핵심은 홀 -> 홀/짝 으로 나누어 진다는 점이다. 즉 모두 홀수인 상태로 상대에게 넘겨주게 되면, 상대는 임의의 개수의 홀수를 다시 홀/짝으로 분해해서 줄 텐데, 홀수의 개수 >= 짝수의 개수 이다.

 

따라서 다시 항상 홀수인 상태로 상대에게 넘겨줄 수 있다.

 

따라서 내 차례에서 모든 짝수를 없앨 수 있다면 승리한다. 

이에 생각을 확장해보면

• 모두 홀수인 게임판은 후공이 이긴다.
• 홀수와 짝수가 동시에 존재하는 게임판은 선공이 이긴다.
• 짝수만 존재하면서 짝수가 짝수개인 게임판은 선공이 이긴다.

결국 짝수만 있는, 짝수가 홀수개인 게임판이 문제가 된다.

그런데 2번 상태 때문에, 홀수를 하나라도 넘겨주면 진다...

따라서 이제 상대 차례에 모든 수를 짝수로 넘겨줄 수 있어야만 내가 이긴다.

이 문제는 어떻게 풀까?

 

전체를 2로 나누면 원본 문제랑 동일하다.

따라서 재귀적으로 풀 수 있다.

 

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
const ll n_ = 2e5 + 10;
ll n;
ll go(vector<ll> &v) {
    ll a = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (v[i] % 2) a++;
        else b++;
    }
    if (a == n) return 0;
    if ((b % 2) && b == n) {
        for (auto &nxt : v) nxt /= 2;
        return go(v);
    }
    return 1;
}
void solve() {
    cin >> n;
    vector<ll> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    cout << go(v) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int tc;
    cin >> tc;
    while (tc--) solve();
};