using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; namespace CodeIq { internal class Program { /// /// あなたと素数を習ったばかりのEveは、素数のゲームを思いついた。 /// /// ゲームの内容は以下のとおりです。 /// ・まず初めに、先攻のプレイヤーに2以上の自然数Nが与えられます。 /// ・その番のプレイヤーはNに対して、「N以下(N含む)の素数」のどれかで減算する、 /// その数をN′とすると、N′が0または1になってしまったら、そのプレイヤーの負けである。 /// ・その後N′を新たなNとし、相手にその数を渡し、以上を繰り返します。 /// /// まずあなたが先攻となりゲームを始めます。 /// この時、どちらも負けないように動くと考える。自然数Nが与えられた時、 /// あなたが勝つことが出来る場合Win、それ以外はLoseを返してください。 /// private static void Main() { var n = int.Parse( Console.ReadLine().Split( ' ' )[0] ); //var n = 5; // Nまでの素数を全て算出しておく var primeNumbers = new List(); var isPrimeNumber = new Func( target => { var root = Math.Sqrt( target ); for( var i = 0; i < root; i++ ) if( target % primeNumbers[i] == 0 ) return false; return true; } ); primeNumbers.Add( 2 ); primeNumbers.Add( 3 ); primeNumbers.Add( 5 ); primeNumbers.Add( 7 ); for( var i = 9; i < n; i += 2 ) if( isPrimeNumber( i ) ) primeNumbers.Add( i ); // 現在値からN以下の任意の素数をひいた時、2か3にできれば勝てる // 2か3にできない場合は、次に相手がひく時に2か3にならないようにひく // それが出来ない場合は負ける var isYourTurn = true; var isEnd = false; while( n > 3 && !isEnd ) { // n - (2~3)の値が存在しない場合はどうやっても2~3にすることができない if( primeNumbers.Exists( num => ( n - 3 ) <= num && num <= ( n - 2 ) ) ) { isYourTurn = !isYourTurn; n -= primeNumbers.Find( num => ( n - 3 ) <= num && num <= ( n - 2 ) ); } else { isEnd = true; foreach( var pNum in primeNumbers ) { if( !primeNumbers.Exists( num => ( n - pNum ) <= 3 || ( ( n - pNum ) - 3 ) <= num && num <= ( ( n - pNum ) - 2 ) ) ) { n -= pNum; isEnd = false; isYourTurn = !isYourTurn; break; } } } } Debug.Print( isYourTurn ? "Lose" : "Win" ); Console.WriteLine( isYourTurn ? "Lose" : "Win" ); } } }