結果

問題 No.7 プライムナンバーゲーム
ユーザー TaK7907TaK7907
提出日時 2018-02-03 23:47:25
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 2,174 bytes
コンパイル時間 2,320 ms
コンパイル使用メモリ 108,420 KB
実行使用メモリ 77,540 KB
最終ジャッジ日時 2023-09-03 22:19:59
合計ジャッジ時間 5,437 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 58 ms
21,716 KB
testcase_01 AC 61 ms
21,456 KB
testcase_02 AC 431 ms
75,736 KB
testcase_03 AC 71 ms
23,956 KB
testcase_04 AC 63 ms
21,752 KB
testcase_05 WA -
testcase_06 AC 165 ms
39,604 KB
testcase_07 AC 73 ms
24,568 KB
testcase_08 AC 81 ms
30,388 KB
testcase_09 WA -
testcase_10 AC 59 ms
21,524 KB
testcase_11 AC 98 ms
32,452 KB
testcase_12 AC 98 ms
31,872 KB
testcase_13 AC 63 ms
21,532 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 106 ms
35,468 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.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