結果

問題 No.636 硬貨の枚数2
ユーザー sjiki
提出日時 2024-08-05 09:58:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 922 bytes
コンパイル時間 505 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 80,768 KB
最終ジャッジ日時 2024-08-05 09:58:43
合計ジャッジ時間 7,034 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2 TLE * 2
other -- * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

def min_coins(N):
    # 硬貨の額面を列挙
    coins = set()
    i = 0
    while (2 ** i) <= N:
        coins.add(2 ** i)
        i += 1
    j = 0
    while (3 ** j) <= N:
        coins.add(3 ** j)
        j += 1
    coins = sorted(coins, reverse=True)
    
    def count_coins(amount):
        count = 0
        for coin in coins:
            if amount == 0:
                break
            count += amount // coin
            amount %= coin
        return count
    
    min_count = float('inf')
    for X in range(N + 1):
        Y = X - N
        count_X = count_coins(X)
        count_Y = count_coins(abs(Y))
        min_count = min(min_count, count_X + count_Y)
    
    return min_count

# 入力の読み込み
if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    N = int(input().strip())
    
    # 結果の計算
    result = min_coins(N)
    
    # 結果の出力
    print(result)
0