結果

問題 No.7 プライムナンバーゲーム
ユーザー velfare_nagatavelfare_nagata
提出日時 2016-10-07 21:25:28
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 2,737 bytes
コンパイル時間 887 ms
コンパイル使用メモリ 112,860 KB
実行使用メモリ 26,172 KB
最終ジャッジ日時 2024-05-01 15:03:36
合計ジャッジ時間 2,682 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 28 ms
22,068 KB
testcase_01 AC 26 ms
24,076 KB
testcase_02 AC 92 ms
23,852 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 45 ms
23,872 KB
testcase_07 AC 39 ms
23,988 KB
testcase_08 AC 31 ms
23,820 KB
testcase_09 AC 56 ms
26,164 KB
testcase_10 AC 26 ms
24,076 KB
testcase_11 AC 39 ms
23,996 KB
testcase_12 WA -
testcase_13 AC 27 ms
26,060 KB
testcase_14 AC 94 ms
25,944 KB
testcase_15 WA -
testcase_16 AC 85 ms
24,080 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace CodeIq
{
	internal class Program
	{
		/// <summary>
		/// あなたと素数を習ったばかりのEveは、素数のゲームを思いついた。
		/// 
		/// ゲームの内容は以下のとおりです。
		/// ・まず初めに、先攻のプレイヤーに2以上の自然数Nが与えられます。
		/// ・その番のプレイヤーはNに対して、「N以下（N含む）の素数」のどれかで減算する、
		/// その数をN′とすると、N′が0または1になってしまったら、そのプレイヤーの負けである。
		/// ・その後N′を新たなNとし、相手にその数を渡し、以上を繰り返します。
		/// 
		/// まずあなたが先攻となりゲームを始めます。
		/// この時、どちらも負けないように動くと考える。自然数Nが与えられた時、
		/// あなたが勝つことが出来る場合Win、それ以外はLoseを返してください。
		/// </summary>
		private static void Main()
		{
			var n = int.Parse( Console.ReadLine().Split( ' ' )[0] );
			//var n = 5;

			// Nまでの素数を全て算出しておく
			var primeNumbers = new List<int>();
			var isPrimeNumber = new Func<int, bool>( 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" );
		}
	}
}
0