結果
問題 | No.7 プライムナンバーゲーム |
ユーザー | 👑 SPD_9X2 |
提出日時 | 2020-01-21 02:24:57 |
言語 | Python3 (3.11.6 + numpy 1.26.0 + scipy 1.11.3) |
結果 |
AC
|
実行時間 | 3,141 ms / 5,000 ms |
コード長 | 1,305 bytes |
コンパイル時間 | 105 ms |
コンパイル使用メモリ | 11,096 KB |
実行使用メモリ | 15,596 KB |
最終ジャッジ日時 | 2023-07-24 21:31:39 |
合計ジャッジ時間 | 21,775 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 16 ms
8,184 KB |
testcase_01 | AC | 16 ms
8,208 KB |
testcase_02 | AC | 3,141 ms
15,560 KB |
testcase_03 | AC | 187 ms
9,896 KB |
testcase_04 | AC | 61 ms
9,120 KB |
testcase_05 | AC | 64 ms
9,180 KB |
testcase_06 | AC | 825 ms
11,924 KB |
testcase_07 | AC | 528 ms
11,380 KB |
testcase_08 | AC | 250 ms
10,308 KB |
testcase_09 | AC | 1,292 ms
12,968 KB |
testcase_10 | AC | 16 ms
8,348 KB |
testcase_11 | AC | 585 ms
11,340 KB |
testcase_12 | AC | 2,294 ms
14,480 KB |
testcase_13 | AC | 2,368 ms
14,684 KB |
testcase_14 | AC | 2,875 ms
15,596 KB |
testcase_15 | AC | 2,890 ms
15,332 KB |
testcase_16 | AC | 2,635 ms
14,932 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")