[yukicoder] No. 8 N言っちゃダメゲーム

2020年10月3日2020年12月12日

問題

方針

\( K \geq N – 1 \) のときは先手必勝です。最終的に \( N – 1 \) を言うことができれば勝ちです。ここで、後手が言うことができる数字を考えます。先手がどのような数字を言ったとしても、\( n \) を自然数として、\( n(K + 1) \) を後手は必ず言うことができます。つまり、先手が加算した値を \( a + 1\) とすると、後手は \( K – a \) を加算した値を言うことで達成できます。したがって、\( (N – 1) \bmod (K + 1)  = 0 \) であれば後手が必勝です。

一方で、\( (N – 1) \bmod (K + 1)  \neq 0 \) のとき、先手は、\( (n – 1)(K + 1) + (N – 1) \bmod (K + 1) \) と言うことができます。また、\( (n – 1)(K + 1) + (N – 1) \bmod (K + 1) = N – 1\) となる \( n \) が存在するので、先手が必勝です。

コード

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

int main() {
    int P;
    cin >> P;
    int N, K;
    for (int i = 0; i < P; i++) {
        cin >> N >> K;
        if (K >= N - 1) {
            cout << "Win\n";
        } else {
            if ((N - 1) % (K + 1) != 0) {
                cout << "Win\n";
            } else {
                cout << "Lose\n";
            }
        }
    }
    return 0;
}

感想

こういう問題苦手です。