結果

問題 No.7 プライムナンバーゲーム
ユーザー _matumo_
提出日時 2018-06-12 13:42:11
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 69 ms / 5,000 ms
コード長 3,259 bytes
コンパイル時間 1,100 ms
コンパイル使用メモリ 115,476 KB
実行使用メモリ 19,200 KB
最終ジャッジ日時 2024-10-01 16:12:10
合計ジャッジ時間 2,355 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;

namespace YukiCoder
{
    class Program
    {
        static sbyte[] dpN = new sbyte[10001];                                          // 動的計画法
        static List<int> pnR;                                                           // 素数
        //==========================================================================//
        //                          myWin()
        //--------------------------------------------------------------------------//
        static int myWin(int N)
        {
            int n = dpN[N];
            if (n != 0)             return n;

            for (int i = 0; i<pnR.Count(); i++)
            {
                if (pnR[i] >= N) break;
                if ((n = myWin(N - pnR[i])) < 0) return dpN[N] = 1;
            }
            return dpN[N] = -1;
        }
        
        //==========================================================================//
        //                          main()
        //--------------------------------------------------------------------------//

        static void Main(string[] args)
        {
            //----------------------------------------------------------------------//
            //                      数値Ｎの読み込み
            //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
            var nN = int.Parse(Console.ReadLine());
            //----------------------------------------------------------------------//
            //                      素数の計算
            //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
            int k = 0;
            pnR = new List<int>();
            var pna = Enumerable.Range(2, nN - 1).ToList();
            //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
            while (k * k < nN)
            {
                k = pna[0];
                pnR.Add(k);
                pna.RemoveAll(x => x % k == 0);
            }
            pnR.AddRange(pna);
            //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
            //pnR.ToList().ForEach(x => Console.WriteLine(x));
            //----------------------------------------------------------------------//
            //                      動的計画法の準備
            //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
            for (int i = 0; i < 100; i++) dpN[i] = 1;
            List<int> pnX = new List<int> { 2, 3, 11, 12, 27, 36, 37, 51, 57, 87, 93 }; // 負け値
            foreach (var n in pnX) dpN[n] = -1;
            //----------------------------------------------------------------------//
            //                      実行と結果表示
            //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
            if (myWin(nN) > 0)      Console.WriteLine("Win");
            else                    Console.WriteLine("Lose");

            //for (int i = 0; i < nN; i++)  Console.WriteLine(i + "=" + dpN[i] + " ");
            //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
            Console.ReadLine();
        }
    }
}
0