結果
問題 |
No.634 硬貨の枚数1
|
ユーザー |
![]() |
提出日時 | 2022-09-09 02:05:46 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 615 bytes |
コンパイル時間 | 391 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 64,564 KB |
最終ジャッジ日時 | 2024-11-24 23:26:40 |
合計ジャッジ時間 | 6,543 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 WA * 58 |
ソースコード
from bisect import bisect_right as br from collections import deque n = [] for i in range(1, 10000): if i*(i+1)//2>pow(10, 7): break else: n.append(i*(i+1)//2) cnt = [0]*5000 num = deque() nn = [] for i in range(len(n)): if n[i]<5000: cnt[n[i]] = 1 num.append(n[i]) nn.append(n[i]) while num: v = num.popleft() for a in nn: if v+a>=5000: break else: if cnt[v+a]==0: cnt[v+a] = cnt[v]+1 num.append(v+a) N = int(input()) if N in n: print(1) else: print(cnt[N-n[br(n, N)-1]]+1)