結果
問題 | No.2744 Power! or +1 |
ユーザー | Nzt3 |
提出日時 | 2024-04-15 23:44:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,146 bytes |
コンパイル時間 | 139 ms |
コンパイル使用メモリ | 82,404 KB |
実行使用メモリ | 67,756 KB |
最終ジャッジ日時 | 2024-04-17 18:33:01 |
合計ジャッジ時間 | 1,051 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 45 ms
67,652 KB |
testcase_01 | AC | 44 ms
65,536 KB |
testcase_02 | AC | 37 ms
61,700 KB |
testcase_03 | AC | 34 ms
60,492 KB |
testcase_04 | AC | 36 ms
61,436 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 31 ms
53,072 KB |
testcase_08 | AC | 42 ms
67,756 KB |
testcase_09 | AC | 34 ms
54,668 KB |
testcase_10 | AC | 36 ms
53,672 KB |
ソースコード
import heapq N,A,B,C=map(int,input().split()) fac=[1]*N fac_over=[0]*N for i in range(1,N): fac[i]=fac[i-1]*i fac_over[i]=fac_over[i-1] if fac[i]>=N: fac[i]%=N fac_over[i]=1 dist=[N*A]*N*2 dist[1]=0 q=[(0,1)] while len(q)>0: d,v=heapq.heappop(q) ov=v//N v%=N if dist[v]<d: continue # 操作1 if dist[(v+1)%N+N*ov]>d+A: dist[(v+1)%N+N*ov]=d+A if (v+1)%N==0: break heapq.heappush(q,(d+A,(v+1)%N+N*ov)) # 操作2 b,v2=B,v ov2=ov while d+b<N*A: if ov2: if dist[v2+N]>d+b: dist[v2+N]=d+b heapq.heappush(q,(d+b,v2+N)) else: if dist[v2]>d+b: dist[v2]=d+b heapq.heappush(q,(d+b,v2)) b*=B v2*=v if v2>=N: ov2=1 v2%=N # 操作3 if ov: if dist[0]>d+C: dist[0]=d+C break else: if fac_over[v]: if dist[fac[v]+N]>d+C: dist[fac[v]+N]=d+C if fac[v]==0: break heapq.heappush(q,(d+C,fac[v]+N)) else: if dist[fac[v]]>d+C: dist[fac[v]]=d+C if fac[v]==0: break heapq.heappush(q,(d+C,fac[v])) print(min(dist[0],dist[N]))