結果
問題 |
No.7 プライムナンバーゲーム
|
ユーザー |
![]() |
提出日時 | 2015-10-06 23:34:43 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 598 ms / 5,000 ms |
コード長 | 684 bytes |
コンパイル時間 | 126 ms |
コンパイル使用メモリ | 6,912 KB |
実行使用メモリ | 73,344 KB |
最終ジャッジ日時 | 2024-10-01 15:37:35 |
合計ジャッジ時間 | 7,478 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
# coding: utf-8 import sys #再帰の深さを設定するよ! sys.setrecursionlimit(100000) N = int(raw_input()) prime_num = [[] for _ in range(10001)] #n以下の素数を求める def primeCheck(n): res = list(prime_num[n-1]) for pr in res: if n % pr == 0: return res res.append(n) return res for i in range(2, 10001): prime_num[i] = list(primeCheck(i)) dp=[0 for _ in range(N+1)] dp[0] = 1 dp[1] = 1 def dfs(n): if dp[n] != 0: return dp[n] res = -1 for i in prime_num[n]: if dfs(n-i)==-1: res=1 break dp[n]=res return dp[n] if dfs(N)==1: print 'Win' else: print 'Lose'