結果

問題 No.7 プライムナンバーゲーム
ユーザー _matumo__matumo_
提出日時 2018-06-12 13:42:11
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 98 ms / 5,000 ms
コード長 3,259 bytes
コンパイル時間 3,635 ms
コンパイル使用メモリ 105,964 KB
実行使用メモリ 24,088 KB
最終ジャッジ日時 2023-07-24 21:08:44
合計ジャッジ時間 5,420 ms
ジャッジサーバーID
(参考情報)
judge14 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 50 ms
21,736 KB
testcase_01 AC 51 ms
21,900 KB
testcase_02 AC 98 ms
22,100 KB
testcase_03 AC 54 ms
23,860 KB
testcase_04 AC 52 ms
23,804 KB
testcase_05 AC 52 ms
23,772 KB
testcase_06 AC 66 ms
22,080 KB
testcase_07 AC 61 ms
21,916 KB
testcase_08 AC 55 ms
21,812 KB
testcase_09 AC 70 ms
22,048 KB
testcase_10 AC 50 ms
23,744 KB
testcase_11 AC 60 ms
21,928 KB
testcase_12 AC 83 ms
21,920 KB
testcase_13 AC 87 ms
22,044 KB
testcase_14 AC 97 ms
24,088 KB
testcase_15 AC 93 ms
21,912 KB
testcase_16 AC 95 ms
21,992 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;

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)
        {
            //----------------------------------------------------------------------//
            //                      数値Nの読み込み
            //- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - //
            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