結果

問題 No.7 プライムナンバーゲーム
コンテスト
ユーザー nuwasogi
提出日時 2015-11-29 16:56:43
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 82 ms / 5,000 ms
コード長 2,097 bytes
コンパイル時間 878 ms
コンパイル使用メモリ 118,404 KB
実行使用メモリ 19,456 KB
最終ジャッジ日時 2024-10-01 15:38:11
合計ジャッジ時間 2,327 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.Linq;

namespace PrimeNumberGame_CS
{
    class Program
    {
        static void Main(string[] args)
        {
            Solver sol = new Solver();
            Console.WriteLine(sol.Solve() ? "Win" : "Lose");
        }
    }

    class Solver
    {
        int[] PrimeNumber;
        int N;
        bool[] WL;

        public bool Solve()
        {
            if (N <= 3) return false;
            PrimeNumber = SieveOfEratosthenes(N - 2);
            for (int i = 4; i <= N; i++)
            {
                WL[i] = PrimeNumber.Any(n => (n <= i - 2) && !WL[i - n]);
            }
            return WL[N];
        }

        public Solver()
        {
            N = ri();
            WL = new bool[N + 1];
        }

        static String rs() { return Console.ReadLine(); }
        static int ri() { return int.Parse(Console.ReadLine()); }
        static long rl() { return long.Parse(Console.ReadLine()); }
        static double rd() { return double.Parse(Console.ReadLine()); }
        static String[] rsa() { return Console.ReadLine().Split(' '); }
        static int[] ria() { return Console.ReadLine().Split(' ').Select(e => int.Parse(e)).ToArray(); }
        static long[] rla() { return Console.ReadLine().Split(' ').Select(e => long.Parse(e)).ToArray(); }
        static double[] rda() { return Console.ReadLine().Split(' ').Select(e => double.Parse(e)).ToArray(); }

        /* max以下の素数の配列を返す (max は1以上)*/
        public int[] SieveOfEratosthenes(int max)
        {
            bool[] is_prime = new bool[max + 1];
            int cur;
            for (int i = 2; i < is_prime.Length; i++)
            {
                is_prime[i] = true;
            }
            for (cur = 2; cur < is_prime.Length; cur++)
            {
                if (!is_prime[cur]) continue;
                for (int nc = cur * 2; nc <= max; nc += cur)
                {
                    is_prime[nc] = false;
                }
            }
            return Enumerable.Range(2, max - 1).Where(e => is_prime[e]).ToArray();
        }
    }
}
0