結果

問題 No.915 Plus Or Multiple Operation
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:45:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 1,702 bytes
コンパイル時間 257 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 60,828 KB
最終ジャッジ日時 2025-03-31 17:46:15
合計ジャッジ時間 1,481 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    input = sys.stdin.read().split()
    idx = 0
    Q = int(input[idx])
    idx += 1
    for _ in range(Q):
        A = int(input[idx])
        B = int(input[idx+1])
        C = int(input[idx+2])
        idx +=3
        
        if C ==1:
            if A ==0:
                print(0)
            else:
                print(-1)
            continue
        
        if A ==0:
            print(0)
            continue
        
        # Compute max_k
        max_k_val = 0
        current = 1
        while True:
            next_val = current * C
            if next_val > A:
                break
            current = next_val
            max_k_val +=1
        
        min_cost = float('inf')
        
        for current_k in range(0, max_k_val +1):
            remaining = A
            cost =0
            valid = True
            for i in range(current_k +1):
                power = current_k -i
                base = C ** power
                s_i = remaining // base
                remaining -= s_i * base
                if i ==0:
                    if s_i <1:
                        valid = False
                        break
                # Calculate cost_i
                if s_i ==0:
                    cost_i =0
                else:
                    cost_i = (s_i + C-2) // (C-1)  # ceiling(s_i / (C-1))
                cost += cost_i
            if valid and remaining ==0:
                total = (cost + current_k) * B
                if total < min_cost:
                    min_cost = total
        
        if min_cost != float('inf'):
            print(min_cost)
        else:
            print(-1)

if __name__ == '__main__':
    solve()
0