結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | 37zigen |
提出日時 | 2016-03-09 19:44:16 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 359 ms / 5,000 ms |
コード長 | 1,574 bytes |
コンパイル時間 | 2,614 ms |
コンパイル使用メモリ | 79,044 KB |
実行使用メモリ | 56,440 KB |
最終ジャッジ日時 | 2024-04-09 03:56:42 |
合計ジャッジ時間 | 7,459 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 143 ms
53,772 KB |
testcase_01 | AC | 133 ms
53,988 KB |
testcase_02 | AC | 359 ms
56,440 KB |
testcase_03 | AC | 168 ms
54,580 KB |
testcase_04 | AC | 162 ms
54,104 KB |
testcase_05 | AC | 159 ms
53,980 KB |
testcase_06 | AC | 228 ms
54,368 KB |
testcase_07 | AC | 202 ms
54,580 KB |
testcase_08 | AC | 177 ms
54,448 KB |
testcase_09 | AC | 246 ms
54,672 KB |
testcase_10 | AC | 131 ms
54,004 KB |
testcase_11 | AC | 207 ms
54,748 KB |
testcase_12 | AC | 291 ms
54,880 KB |
testcase_13 | AC | 316 ms
54,872 KB |
testcase_14 | AC | 355 ms
54,948 KB |
testcase_15 | AC | 344 ms
55,100 KB |
testcase_16 | AC | 335 ms
54,932 KB |
ソースコード
import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { static ArrayList<Integer> PrimeList=new ArrayList<>(); static int[] judge; public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); judge=new int[n+1]; Arrays.fill(judge, 0);//0は未探索とする boolean isPrime[]=new boolean[n+1]; isPrime=isPrime(n); //for(int i=0;i<=n;i++){ //System.out.println("isPrime["+i+"]="+isPrime[i]); //} PrimeList=PrimeList(n); if(judge(n)){ System.out.println("Win"); }else{ System.out.println("Lose"); } } public static boolean[] isPrime(int n){ boolean isPrime[]=new boolean[n+1]; Arrays.fill(isPrime, true); isPrime[0]=false; isPrime[1]=false; for(int i=2;i<n;i++){ if(isPrime[i]){ for(int j=2;j*i<=n;j++){ isPrime[i*j]=false; } } } return isPrime; } public static ArrayList<Integer> PrimeList(int n){ ArrayList<Integer> PrimeList=new ArrayList<>(); boolean[] isPrime=new boolean[n+1]; isPrime=isPrime(n); for(int i=2;i<=n;i++){ if(isPrime[i]){ PrimeList.add(i); } } return PrimeList; } //judge(n)の数字で回って来た時の自分の勝ち負けを調べる。 public static boolean judge(int n){ boolean j=false; int p; if(judge[n]==1)return true; if(judge[n]==-1)return false; for(int i=0;i<PrimeList.size()&&PrimeList.get(i)<=n;i++){ p=PrimeList.get(i); if(!judge(n-p)){ j=true; } } if(n==1||n==0)return true; if(j)judge[n]=1; if(!j)judge[n]=-1; return j; } }