結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2017-06-25 20:30:23 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 137 ms / 5,000 ms |
コード長 | 1,975 bytes |
コンパイル時間 | 1,012 ms |
コンパイル使用メモリ | 107,136 KB |
実行使用メモリ | 18,332 KB |
最終ジャッジ日時 | 2024-10-01 16:05:01 |
合計ジャッジ時間 | 3,052 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.IO; using System.Linq; using System.Collections.Generic; using System.Text; public class Program { public void Proc() { int num = int.Parse(Reader.ReadLine()); this.SetPrimeNumber(num); string ans = "Lose"; if(canWin(num)) { ans = "Win"; } Console.WriteLine(ans); } private Dictionary<int, bool> dic = new Dictionary<int, bool>(); private bool canWin(int num) { if(num<=3) { return false; } if(dic.ContainsKey(num)) { return dic[num]; } bool wn = false; for (int i = 0; i < this.PrimeNumberList.Length; i++) { int prime = this.PrimeNumberList[i]; if(prime + 1>= num) { break; } if(!canWin(num-prime)) { wn = true; break; } } dic[num] = wn; return wn; } private int[] PrimeNumberList; private void SetPrimeNumber(int num) { bool[] flags = new bool[num + 1]; List<int> ret = new List<int>(); for (int i = 2; i <= num; i++) { if (flags[i]) { continue; } ret.Add(i); int max = num / i; for (int j = 0; j <= max; j++) { flags[i * j] = true; } } this.PrimeNumberList = ret.ToArray(); } public class Reader { private static StringReader sr; public static bool IsDebug = false; public static string ReadLine() { if (IsDebug) { if (sr == null) { sr = new StringReader(InputText.Trim()); } return sr.ReadLine(); } else { return Console.ReadLine(); } } private static string InputText = @" 10000 "; } public static void Main(string[] args) { #if DEBUG Reader.IsDebug = true; #endif Program prg = new Program(); prg.Proc(); } }