結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー TaK7907
提出日時 2018-02-03 23:47:25
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 2,174 bytes
コンパイル時間 1,124 ms
コンパイル使用メモリ 114,312 KB
実行使用メモリ 73,160 KB
最終ジャッジ日時 2024-06-13 02:58:29
合計ジャッジ時間 3,527 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 13 WA * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.Linq;
using System.Text;
using System.Threading.Tasks;

namespace yuki007
{
    public class Game
    {
        List<int> PrimeNumbers_;
        int N_;
        
        public Game(int n) {
            N_ = n;
            PrimeNumbers_ = new List<int>() { 2 };
            for(var k = 2; k <= n; ++k) {
                var isPrimeNumber = true;
                foreach(var primeNumber in PrimeNumbers_) {
                    if(k % primeNumber == 0) {
                        isPrimeNumber = false;
                        break;
                    }
                }
                if(isPrimeNumber) PrimeNumbers_.Add(k);
            }
        }

        private bool ExistPrimeNumberWhichLeavesTwoOrThree(int minuend) {
            return PrimeNumbers_.Where(x => x == minuend - 2 || x == minuend - 3).Any() ? true : false;
        }
        
        public string Solve() {
            var canWin = false;
            var reached = new bool[N_ + 1];
            reached[N_] = true;
            var queue = new Queue<int>();
            queue.Enqueue(N_);
            while(queue.Any()) {
                var myN = queue.Dequeue();

                // 自分の番
                if(ExistPrimeNumberWhichLeavesTwoOrThree(myN)) {
                    canWin = true;
                    break;
                }
                var enemiesNs = PrimeNumbers_.Where(x => x <= myN-3).Select(x => myN - x).ToList();
                foreach(var n in enemiesNs) {
                    // 相手の番
                    if(ExistPrimeNumberWhichLeavesTwoOrThree(n)) {
                        continue;
                    }
                    var myNs = PrimeNumbers_.Where(x => x <= n - 3).Select(x => n - x).ToList();
                    foreach(var i in myNs) {
                        queue.Enqueue(i);
                    }
                }
            }
            return canWin ? "Win" : "Lose";
        }
    }

    class Program
    {
        static void Main(string[] args) {
            var game = new Game(int.Parse(Console.ReadLine()));
            Console.WriteLine(game.Solve());
        }
    }
}
0