No.8 N言っちゃダメゲーム
n=20,k=4の場合を考えてみることにする。
他のかたの解説にもある通り、先攻が勝つためには最後のターンでn-1(ここでは19)を言うのが望ましい。なぜなら、先攻がn-1を言ったとき、次に後攻はn-1にkを足した値(kは1以上)を言わなければならず、必ずn以上(ここでは20以上)を言うことになるからである。
19を言うためには、先攻はその前のターンで14を言うのが望ましい。なぜなら、先攻が14を言えば、後攻は次の自分のターンで決して19を言えないからである(言える数の範囲は1~4なので、どう言っても15~18にしかならない)。同様に、14を先攻が言うためには、その前のターンで9を言うのが望ましい。同様に先攻が9を言うためにはその前のターンで4を言うのが望ましい。ここで先攻は、4という数字を最初のターンから言うことができる(言える数の範囲は1~4なので)。先攻は最初のターンに4を言える=先攻は最後のターンに19を言える、よって、n=20,k=4のときは先攻が必ず勝つ。
次に、n=21,k=4の場合を考えてみる。
先攻が勝つためには最後のターンで20を言うのが望ましい。20を言うためには15。15を言うためには10。10を言うためには5。5を言うためには0。ここで先攻は、0という数字を最初のターンに言うことができない(言える数の範囲は1~4なので)。先攻は最初のターンに0を言えない=先攻は最後のターンに20を言えない、よって、n=21,k=4のときは後攻が必ず勝つ。後攻の立場でもこれを確かめてみたい。
後攻が勝つためには最後のターンで20を言わなければならない。20を言うためには15。15を言うためには10。10を言うためには5。ここで後攻は、最初のターンに必ず5という数字を言うことができる。なぜなら、先攻は最初のターンに1~4の数字を言わなければならず、後攻は先攻が言った数字に合わせて自由に5を作ることができるからだ(1なら4を言い、3なら2を言うというふうに)。後攻は最初のターンに5を言える=後攻は最後のターンに20を言える、よって、n=21,k=4のときは後攻が必ず勝つ。
このようにして、この問題では、nとkが与えられた時点で、戦略に関係なく、先攻と後攻のどちらが勝つかはすでに決まっている。先攻が勝つ条件は、n-1からk+1をk以下になるまで引いていったときに、0にならない場合である。つまり、n-1がk+1で割り切れないときは先攻の勝利となる。逆に先攻が負ける条件は、n-1がk+1で割り切れる場合である。そのような処理は簡単な条件分岐で実装できる。
import java.util.*; import static java.lang.System.*; public class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int p = sc.nextInt(); int n,k; for (int i=0; i<p; i++) { n = sc.nextInt(); k = sc.nextInt(); out.println((n-1)%(k+1)==0?"Lose":"Win"); } } }