結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2017-12-10 22:42:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 39 ms / 5,000 ms |
コード長 | 743 bytes |
コンパイル時間 | 579 ms |
コンパイル使用メモリ | 66,980 KB |
最終ジャッジ日時 | 2025-01-05 05:07:41 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include<iostream> using namespace std; int p[10000], dp[10000], i, j; void prime(int n) //エラトステネスの篩で配列pに対して、素数の時1とする { for (i = 1; i <= n; i++) { p[i] = 1; } p[1] = 0; for (i = 2; i <= n / 2; i++) { for (j = 2; i * j <= n; j++) { p[i * j] = 0; } } } int main() { int n; cin >> n; prime(n); for (i = 0; i < 10000; i++) { dp[i] = -1; } dp[2] = 1; dp[3] = 1; dp[4] = 0; dp[5] = 0; for (int i = 6; i <= n; i++) { dp[i] = 1; for (int j = 1; j < i; j++) { if (p[j] != 1)continue; if (dp[i - j] == 1) { dp[i] = 0; break; } } } if (dp[n] == 0) //dp[n]==0と同じ { cout << "Win" << endl; } else { cout << "Lose" << endl; } }