結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | not_522 |
提出日時 | 2015-07-16 19:15:59 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 83 ms / 5,000 ms |
コード長 | 3,363 bytes |
コンパイル時間 | 1,275 ms |
コンパイル使用メモリ | 167,292 KB |
実行使用メモリ | 23,168 KB |
最終ジャッジ日時 | 2024-10-01 15:34:32 |
合計ジャッジ時間 | 2,408 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,820 KB |
testcase_02 | AC | 81 ms
23,168 KB |
testcase_03 | AC | 7 ms
6,820 KB |
testcase_04 | AC | 3 ms
6,816 KB |
testcase_05 | AC | 3 ms
6,816 KB |
testcase_06 | AC | 27 ms
9,472 KB |
testcase_07 | AC | 19 ms
7,296 KB |
testcase_08 | AC | 9 ms
6,820 KB |
testcase_09 | AC | 37 ms
12,160 KB |
testcase_10 | AC | 1 ms
6,816 KB |
testcase_11 | AC | 17 ms
7,296 KB |
testcase_12 | AC | 57 ms
16,512 KB |
testcase_13 | AC | 61 ms
17,536 KB |
testcase_14 | AC | 83 ms
22,784 KB |
testcase_15 | AC | 78 ms
22,016 KB |
testcase_16 | AC | 69 ms
20,352 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; class Prime { private: vector<long long> div; public: Prime(long long n = 0) { for (long long i = 0; i < n; ++i) div.emplace_back(i); for (long long i = 2; i <= n / i; ++i) if (div[i] == i) { for (long long j = i * i; j < n; j += i) div[j] = i; } } bool isPrime(long long n) const { if (n <= 1) return false; if (n < (long long)div.size()) return div[n] == n; for (long long i = 2; i <= n / i; ++i) if (n % i == 0) return false; return true; } vector<long long> factor(long long n) const { vector<long long> res; for (long long i = 2; i <= n / i && n >= (long long) div.size(); ++i) { while (n % i == 0) { res.emplace_back(i); n /= i; } } if (n >= (long long)div.size()) { res.emplace_back(n); } else { while (n > 1) { res.emplace_back(div[n]); n /= div[n]; } } sort(res.begin(), res.end()); return res; } vector<long long> primeFactor(long long n) const { vector<long long> res; for (long long i = 2; i <= n / i && n >= (long long)div.size(); ++i) { if (n % i) continue; res.emplace_back(i); while (n % i == 0) n /= i; } if (n >= max((long long)div.size(), 2ll)) { res.emplace_back(n); } else { while (n > 1) { long long d = div[n]; res.emplace_back(d); while (n % d == 0) n /= d; } } sort(res.begin(), res.end()); return res; } vector<long long> divisor(long long n) const { vector<long long> res; for (long long i = 1; i <= n / i; ++i) { if (n % i == 0) { res.emplace_back(i); if (i != n / i) res.emplace_back(n / i); } } sort(res.begin(), res.end()); return res; } }; template<typename T, typename State, bool Memoize = false> class MinMax { protected: virtual T eval(const State&) const = 0; virtual vector<State> next(const State&) const = 0; virtual bool isTerminated(const State& state) const {return next(state).empty();} virtual bool used(const State&) const {return false;} virtual T memo(const State&) {return T();} virtual void use(const State&, const T&) {} public: T solve(const State& state) { if (Memoize && used(state)) return memo(state); if (isTerminated(state)) return eval(state); T score = numeric_limits<T>::min() + 1; for (const State& child : next(state)) score = max(score, -solve(child)); if (Memoize) use(state, score); return score; } }; class Game : public MinMax<int, int, true> { private: vector<int> mem; vector<int> primes; int eval(const int&) const { return 1; } vector<int> next(const int& state) const { vector<int> res; for (int p : primes) { if (p > state) break; res.emplace_back(state - p); } return res; } bool used(const int& state) const { return mem[state] != 0; } int memo(const int& state) { return mem[state]; } void use(const int& state, const int& score) { mem[state] = score; } public: Game(int n) : mem(n + 1) { Prime prime; for (int i = 0; i <= n; ++i) { if (prime.isPrime(i)) primes.emplace_back(i); } } }; int main() { int n; cin >> n; Game game(n); cout << (game.solve(n) == 1 ? "Win" : "Lose") << endl; }