結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2015-10-26 23:01:56 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 5,000 ms |
コード長 | 1,121 bytes |
コンパイル時間 | 1,312 ms |
コンパイル使用メモリ | 160,112 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 15:37:40 |
合計ジャッジ時間 | 1,784 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define lp(i, a, b) for (int i = (int)(a); i < (int)(b); i++) #define rep(i, n) lp(i, 0, n) #define rlp(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); i--) #define rrep(i, n) rlp(i, 0, n) #define mp make_pair #define mt make_tuple #define pb push_back #define eb emplace_back #define all(c) begin(c), end(c) typedef long long ll; typedef unsigned long long ull; const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, -1, 0, 1}; const int MOD = 1e9 + 7; const int INF = 1 << 28; const ll INFLL = 1ll << 60; template<typename T> inline void unique(T &c){ sort(all(c)); c.erase(unique(all(c)), end(c)); } int n; vector<int> ps; int dp[10010]; bool isprime(int x) { if (x <= 1) return false; for (int i = 2; i * i <= x; i++){ if (x % i == 0) return false; } return true; } int calc(int x) { if (x <= 1) return 1; if (~dp[x]) return dp[x]; for (int p : ps){ if (!calc(x - p)) return dp[x] = 1; } return dp[x] = 0; } int main() { cin >> n; rep(i, n + 1) if (isprime(i)) ps.pb(i); memset(dp, -1, sizeof(dp)); cout << (calc(n) ? "Win\n" : "Lose\n"); }