結果
問題 |
No.7 プライムナンバーゲーム
|
ユーザー |
|
提出日時 | 2016-04-18 12:19:57 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 588 bytes |
コンパイル時間 | 463 ms |
コンパイル使用メモリ | 54,616 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 15:42:48 |
合計ジャッジ時間 | 968 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <iostream> #include <cstring> using namespace std; #define N 10000 int n; int p[N+1]; int dpm[N+1]; void pf() { int k = 0; for ( int i = 2; i <= n; i++ ) { if ( p[i] != 0 ) { continue; } for ( int j = i; j < n; j += i ) { p[j] = 1; } p[k++] = i; } p[k] = 0; } int dp() { for ( int i = 2; i <= n; i++ ) { for ( int j = 0; p[j] != 0 && p[j] < i; j++ ) { int x = i - p[j]; if ( x > 1 && dpm[x] == 0 ) { dpm[i] = 1; break; } } } return 0; } int main() { cin >> n; pf(); dp(); cout << (dpm[n] ? "Win" : "Lose") << endl; return 0; }