結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2020-01-21 02:24:57 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 3,466 ms / 5,000 ms |
コード長 | 1,305 bytes |
コンパイル時間 | 189 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 18,048 KB |
最終ジャッジ日時 | 2024-04-09 04:50:04 |
合計ジャッジ時間 | 23,376 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 31 ms
11,008 KB |
testcase_01 | AC | 29 ms
11,008 KB |
testcase_02 | AC | 3,466 ms
18,048 KB |
testcase_03 | AC | 226 ms
12,416 KB |
testcase_04 | AC | 83 ms
11,776 KB |
testcase_05 | AC | 82 ms
11,648 KB |
testcase_06 | AC | 934 ms
14,592 KB |
testcase_07 | AC | 641 ms
13,952 KB |
testcase_08 | AC | 293 ms
12,672 KB |
testcase_09 | AC | 1,439 ms
15,616 KB |
testcase_10 | AC | 29 ms
10,880 KB |
testcase_11 | AC | 658 ms
13,952 KB |
testcase_12 | AC | 2,466 ms
16,768 KB |
testcase_13 | AC | 2,493 ms
17,024 KB |
testcase_14 | AC | 3,209 ms
18,048 KB |
testcase_15 | AC | 3,139 ms
17,792 KB |
testcase_16 | AC | 3,105 ms
17,648 KB |
ソースコード
""" grundy数の計算? 各値についてqを渡しておいてdp """ def Sieve(n): #n以下の素数全列挙(O(nloglogn)) retは素数が入ってる。divlisはその数字の素因数が一つ入ってる ret = [] divlis = [-1] * (n+1) #何で割ったかのリスト(初期値は-1) flag = [True] * (n+1) flag[0] = False flag[1] = False ind = 2 while ind <= n: if flag[ind]: ret.append(ind) ind2 = ind ** 2 while ind2 <= n: flag[ind2] = False divlis[ind2] = ind ind2 += ind ind += 1 return ret,divlis N = int(input()) ret,divs = Sieve(N) lis = [ [] for i in range(N+1) ] dic = {} for i in range(N+1): dic[i] = {} gr = [None] * (N+1) for i in range(N-1): i += 2 if len(lis[i]) == 0: gr[i] = 0 else: num = 0 lis[i].sort() for j in lis[i]: if j != num: gr[i] = num break else: num += 1 if gr[i] == None: gr[i] = num for j in ret: if j + i <= N and gr[i] not in dic[i+j]: dic[i+j][gr[i]] = 1 lis[j+i].append(gr[i]) if gr[-1] == 0: print ("Lose") else: print ("Win")