結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2020-01-03 21:03:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,145 bytes |
コンパイル時間 | 2,003 ms |
コンパイル使用メモリ | 170,828 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-11-22 19:26:20 |
合計ジャッジ時間 | 2,696 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 WA * 5 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i=0;i<(n);++i)#define all(a) (a).begin(),(a).end()#define dunk(a) cout << (a) << endlusing namespace std;typedef long long ll;class Prime{int i, iLimit;public:bool isPrime(int a);};bool Prime::isPrime(int a){if (a == 1) return false;iLimit = (int)sqrt(a);for (i = 2; i <= iLimit; i++) {if (a % i == 0) break;}if (i == iLimit + 1) {return true;}else {return false;}}int main() {ios::sync_with_stdio(false);cin.tie(0);int n;cin >> n;bool elf;Prime p;vector<pair<bool,bool>> dp(1000000);vector<int> jud;for (int i = 1; i <= n; ++i) {elf = p.isPrime(i);if (elf) jud.emplace_back(i);}int k = jud.size();//Winを仮定して考えるdp[0].first = true; dp[1].second = true;dp[1].first = true; dp[1].second = true;for (int i = 0; i <= n; ++i) {if (dp[i].first) {for (int j = 0; j < k; ++j) {dp[i + jud[j]].first = true;dp[i + jud[j]].second = (dp[i + jud[j]].second) ? true :((dp[i].second) ? true : false);}}}if (dp[n].first && dp[n].second) puts("Win");else puts("Lose");return 0;}