結果

問題 No.219 巨大数の概算
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:08:10
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,006 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 103,808 KB
最終ジャッジ日時 2025-06-12 14:08:23
合計ジャッジ時間 6,174 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

from decimal import Decimal, getcontext, ROUND_FLOOR

getcontext().prec = 35  # Sufficient precision for all cases

# Precompute the log10 values for X.Y where X ranges from 1-9 and Y from 0-9
log_table = []
for X in range(1, 10):
    row = []
    for Y in range(0, 10):
        value = Decimal(X) + Decimal(Y) / Decimal(10)
        log_val = value.log10()
        row.append(log_val)
    # Append log10(X+1) for the upper bound of Y=10
    row.append(Decimal(X + 1).log10())
    log_table.append(row)

def find_X(f):
    # Binary search to find X such that log10(X) <= f < log10(X+1)
    left, right = 1, 9
    while left <= right:
        mid = (left + right) // 2
        lower = Decimal(mid).log10()
        upper = Decimal(mid + 1).log10()
        if lower <= f < upper:
            return mid
        if f < lower:
            right = mid - 1
        else:
            left = mid + 1
    return None

def find_Y(X, f):
    row = log_table[X - 1]
    left, right = 0, 9
    while left <= right:
        mid = (left + right) // 2
        lower = row[mid]
        upper = row[mid + 1]
        if lower <= f < upper:
            return mid
        if f < lower:
            right = mid - 1
        else:
            left = mid + 1
    return None

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    results = []
    for _ in range(N):
        A = int(input[idx])
        B = int(input[idx + 1])
        idx += 2
        
        log_A = Decimal(A).log10()
        log_val = B * log_A
        
        # Calculate m and f accurately
        m = int(log_val.to_integral(rounding=ROUND_FLOOR))
        f = log_val - m
        
        X = find_X(f)
        if X is None:
            X = 1  # Fallback, though theoretically impossible
        
        Y = find_Y(X, f)
        if Y is None:
            Y = 0  # Fallback
        
        results.append(f"{X} {Y} {m}")
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()
0