結果

問題 No.639 An Ordinary Sequence
ユーザー chineristACchineristAC
提出日時 2020-04-06 03:41:45
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 903 ms / 1,000 ms
コード長 1,999 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 86,552 KB
実行使用メモリ 86,532 KB
最終ジャッジ日時 2023-09-18 14:02:21
合計ジャッジ時間 8,047 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 871 ms
86,256 KB
testcase_01 AC 903 ms
86,372 KB
testcase_02 AC 115 ms
84,124 KB
testcase_03 AC 110 ms
84,260 KB
testcase_04 AC 113 ms
84,376 KB
testcase_05 AC 112 ms
84,500 KB
testcase_06 AC 110 ms
84,140 KB
testcase_07 AC 110 ms
84,436 KB
testcase_08 AC 111 ms
84,164 KB
testcase_09 AC 112 ms
84,372 KB
testcase_10 AC 112 ms
84,632 KB
testcase_11 AC 112 ms
84,532 KB
testcase_12 AC 179 ms
85,960 KB
testcase_13 AC 197 ms
85,708 KB
testcase_14 AC 259 ms
86,164 KB
testcase_15 AC 418 ms
86,324 KB
testcase_16 AC 898 ms
86,384 KB
testcase_17 AC 112 ms
84,012 KB
testcase_18 AC 895 ms
86,532 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict
import heapq

ansmin= {2: 1, 3: 3, 4: 5, 5: 9, 7: 15, 8: 25, 9: 27, 12: 45, 15: 75, 16: 81, 17: 125, 21: 135, 27: 225, 28: 243, 32: 375, 37: 405, 38: 625, 48: 675, 49: 729, 59: 1125, 65: 1215, 70: 1875, 85: 2025, 86: 2187, 87: 3125, 107: 3375, 114: 3645, 129: 5625, 150: 6075, 151: 6561, 157: 9375, 192: 10125, 200: 10935, 201: 15625, 236: 16875, 264: 18225, 265: 19683, 286: 28125, 342: 30375, 351: 32805, 358: 46875, 428: 50625, 464: 54675, 465: 59049, 466: 78125, 522: 84375, 606: 91125, 616: 98415, 644: 140625, 770: 151875, 815: 164025, 816: 177147, 824: 234375, 950: 253125, 1070: 273375, 1081: 295245, 1082: 390625, 1166: 421875, 1376: 455625, 1431: 492075, 1432: 531441, 1468: 703125, 1720: 759375, 1885: 820125, 1897: 885735}
ansmax= {2: 2, 3: 4, 4: 8, 5: 14, 7: 24, 8: 26, 9: 44, 12: 74, 15: 80, 16: 124, 17: 134, 21: 224, 27: 242, 28: 374, 32: 404, 37: 624, 38: 674, 48: 728, 49: 1124, 59: 1214, 65: 1874, 70: 2024, 85: 2186, 86: 3124, 87: 3374, 107: 3644, 114: 5624, 129: 6074, 150: 6560, 151: 9374, 157: 10124, 192: 10934, 200: 15624, 201: 16874, 236: 18224, 264: 19682, 265: 28124, 286: 30374, 342: 32804, 351: 46874, 358: 50624, 428: 54674, 464: 59048, 465: 78124, 466: 84374, 522: 91124, 606: 98414, 616: 140624, 644: 151874, 770: 164024, 815: 177146, 816: 234374, 824: 253124, 950: 273374, 1070: 295244, 1081: 390624, 1082: 421874, 1166: 455624, 1376: 492074, 1431: 531440, 1432: 703124, 1468: 759374, 1720: 820124, 1885: 885734, 1897: 1000000}

ans=[0 for i in range(0,1000001)]
for key in ansmin.keys():
    a=ansmin[key]
    b=ansmax[key]
    for j in range(a,b+1):
        ans[j]=key

ans[0]=1

N=int(input())
if N==0:
    print(1)
else:
    q=[N]
    count=0
    while q:
        x=heapq.heappop(q)
        p=x//3
        r=x//5
        if 1000000>=p:
            count+=ans[p]
        else:
            heapq.heappush(q,p)
        if 1000000>=r:
            count+=ans[r]
        else:
            heapq.heappush(q,r)
    
    print(count)
0