結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
|
提出日時 | 2017-09-09 00:21:31 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 39 ms / 5,000 ms |
コード長 | 885 bytes |
コンパイル時間 | 616 ms |
コンパイル使用メモリ | 72,200 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 16:06:56 |
合計ジャッジ時間 | 1,475 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
//https://yukicoder.me/problems/25 //https://yukicoder.me/submissions/194289 #include <iostream> #include <math.h> #include <cstdio> #include <algorithm> #include <string> #include <string.h> using namespace std; const int MAX_N=10000; int n; bool IsWin[MAX_N+1]; //lose(0), win(1) bool p[MAX_N+1]; //not prime(0), prime(1) int main(){ cin >> n; memset(p, true, sizeof(p)); for(int i=0;i<2;i++) p[i]=false; for(int i=0;i<4;i++) IsWin[i]=false; p[2]=true; for(int i=3;i<=n;i++){ for(int j=2;j*j<=i;j++){ if(p[j]){ if(i%j){ continue; }else{ p[i]=false; } } } } for(int i=4;i<=n;i++){ for(int j=2;j<=i-2;j++){ if(p[j] && !IsWin[i-j]){ //j減らした時にIsWin[i-j]がfalseなら相手が勝てないので自分は勝てる IsWin[i]=true; break; } } } cout << (IsWin[n]?"Win":"Lose") << endl; return 0; }