package main import . "fmt" func main() { var m, k int Scan(&m,&k) secondWin := (m-1)/(k+1) firstWin := (m-1) - secondWin var anataWin,grantWin int if firstWin % 2 != 0 { anataWin = (firstWin+1)/2+secondWin grantWin = firstWin/2 } else { anataWin = firstWin/2 grantWin = firstWin/2+secondWin } switch { case anataWin > grantWin: Println("Win") case anataWin == grantWin: Println("Draw") case anataWin < grantWin: Println("Lose") } } /* 考察 ゲーム問題、超苦手すぎるのでまるで解ける気がしない ゲームは N,K のとき (N - 1) ≡ 0 (mod (K + 1)) のとき後手必勝、それ以外は先手必勝 2~Mの範囲で 後手必勝は floor( (M - 1) / (K + 1) ) 個 それ以外は先手必勝 プレーヤーは交互に先手必勝のゲームを選んでいくのが最善 最後に負けになったプレーヤーは先手必敗(後手必勝)ひたすら引き続ける地獄 先手必勝が 奇数個のとき アナタ Grant アナタ 後手必勝が残っていればGrantが引き続ける(Grantが負け試合を総取り…) 勝利数は  アナタ ceil(先手必勝/2) + 後手必勝  Grant floor(先手必勝/2) 先手必勝が 偶数個のとき アナタ Grant アナタ Grant 後手必勝が残っていればアナタが引き続ける(アナタが負け試合を総取り…) 勝利数は  アナタ 先手必勝/2  Grant 先手必勝/2 + 後手必勝 */ func init() { k := 8 win := 0 lose := 0 for n := 2; n <= k*k*7; n++ { if !check(n, k) { lose++ println( "n=",n, ",k=",k, ",n%k=",n%k, ",?*k+?=", n/k,"*k+",n%k, " [LOSE]", ", ",n/k%(k+1), ", win/lose",win,"/",lose, ) if check2(n, k) || check3(n, k) { panic("WRONG!") } } else { win++ if !check2(n, k) || !check3(n, k) { println( "n=",n, ",k=",k, ",n%k=",n%k, ",?*k+?=", n/k,"*k+",n%k, " [WIN]", ", ",n/k%(k+1), ", win/lose",win,"/",lose, ) panic("WRONG!") } } } /* 法則性の推測 P = floor(N / K) とおく P % (K + 1) == K - 1 のとき 先手必勝 P % (K + 1) == N % K - 1 のとき 後手必勝 P % (K + 1) == K && N % K == 0 のとき 後手必勝 上記以外 先手必勝 2 <= N <= 1 + C * (K + 1) の範囲で 先手必勝 C * K 個 後手必勝 C 個 後手必勝は K+1 回ごとに現れる 後手必勝かは N - 1 ≡ 0 (mod (K + 1)) ぽい? */ } func check3(n, k int) bool { return (n - 1) % (k + 1) != 0 } func check2(n, k int) bool { p := n / k if p % (k + 1) == k - 1 { return true } if p % (k + 1) == n % k - 1 { return false } if p % (k + 1) == k && n % k == 0 { return false } return true } var memo = map[int]bool{} func check(n, k int) bool { if n == 1 { return false } if r, found := memo[n]; found { return r } for i := 1; i <= min(n-1,k); i++ { if !check(n-i,k) { memo[n] = true return true } } memo[n] = false return false }