結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | はむ吉🐹 |
提出日時 | 2016-01-03 12:12:38 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 310 ms / 5,000 ms |
コード長 | 1,239 bytes |
コンパイル時間 | 128 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-04-09 03:54:25 |
合計ジャッジ時間 | 3,312 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 30 ms
10,880 KB |
testcase_01 | AC | 29 ms
10,880 KB |
testcase_02 | AC | 310 ms
11,008 KB |
testcase_03 | AC | 47 ms
10,880 KB |
testcase_04 | AC | 35 ms
10,880 KB |
testcase_05 | AC | 34 ms
10,880 KB |
testcase_06 | AC | 117 ms
11,008 KB |
testcase_07 | AC | 85 ms
11,008 KB |
testcase_08 | AC | 54 ms
11,008 KB |
testcase_09 | AC | 155 ms
11,008 KB |
testcase_10 | AC | 30 ms
10,880 KB |
testcase_11 | AC | 87 ms
11,136 KB |
testcase_12 | AC | 231 ms
11,008 KB |
testcase_13 | AC | 244 ms
11,008 KB |
testcase_14 | AC | 309 ms
11,008 KB |
testcase_15 | AC | 297 ms
11,008 KB |
testcase_16 | AC | 273 ms
11,136 KB |
ソースコード
#!/usr/bin/env python3 # -*- coding: utf-8 -*- import array import math def primes_by_eratosthenes(limit): """ Generate the sequence of prime numbers by Eratosthenes' method. :param limit: The maximum intenger (> 1) to be examined. :type limit: int :return: the sequence of prime numbers :rtype: an instance of :class:`array.array` """ search_list = array.array("Q", range(2, limit + 1)) primes = array.array("Q") while True: p = search_list.pop(0) primes.append(p) if p > math.sqrt(limit): break else: search_list = array.array("Q", filter( lambda x: x % p != 0, search_list)) primes.extend(search_list) return primes def judge(n): dp = array.array("B", [True, True]) primes = primes_by_eratosthenes(n) for m in range(2, n + 1): for p in primes: if p > m: dp.append(False) break elif not dp[m - p]: dp.append(True) break else: continue else: dp.append(False) return dp[n] if __name__ == "__main__": print("Win" if judge(int(input())) else "Lose")