yukicoder No.8 N言っちゃダメゲーム 解説

問題文

解説

N言っちゃダメゲームの勝利はある条件によって決まる
・$N$%$(K+1)=1$なら後手の勝ち
・そうでないなら先手の勝ち
この方法で実際に確かめればOK

自分なりの証明

例えば、K=5とする。
先手：1 後手：23456
先手：12 後手：3456
先手：123 後手：456
先手：1234 後手：56
こんな感じで後手はK+1-(前に行った数)いうことができる。
この時、N%(K+1)==1ならこれを繰り返すだけで勝てる。
また、N%(K+1)!=1なら最初に先手がN%(K+1)-1個言えばあとは後手に合わせてうまく言うだけで勝てる。
もしこれで後手が（先手+後手）!=K+1という感じにしたら相手にチャンスが渡るだけ。

C++での解答例

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

int main(){
  int p;cin>>p;
  for(int i=0;i<p;i++){
    int n,k;cin>>n>>k;
    cout<<(n%(k+1)==1 ? "Lose\n":"Win\n");
  }
}