結果

問題 No.381 名声値を稼ごう Extra
ユーザー gew1fw
提出日時 2025-06-12 19:51:23
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,112 bytes
コンパイル時間 162 ms
コンパイル使用メモリ 82,716 KB
実行使用メモリ 528,976 KB
最終ジャッジ日時 2025-06-12 19:51:35
合計ジャッジ時間 9,609 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def divide_by_two(s):
    if s == "0":
        return "0"
    result = []
    carry = 0
    for c in s:
        num = carry * 10 + int(c)
        q = num // 2
        r = num % 2
        carry = r
        result.append(str(q))
    while len(result) > 0 and result[0] == '0':
        result.pop(0)
    if not result:
        return "0"
    return ''.join(result)

def add_strings(a, b):
    result = []
    carry = 0
    i = len(a) - 1
    j = len(b) - 1
    while i >= 0 or j >= 0 or carry > 0:
        num_a = int(a[i]) if i >= 0 else 0
        num_b = int(b[j]) if j >= 0 else 0
        total = num_a + num_b + carry
        carry = total // 10
        digit = total % 10
        result.append(str(digit))
        i -= 1
        j -= 1
    return ''.join(reversed(result))

def multiply_by_two(s):
    result = []
    carry = 0
    for c in reversed(s):
        num = int(c) * 2 + carry
        carry = num // 10
        digit = num % 10
        result.append(str(digit))
    if carry > 0:
        result.append(str(carry))
    return ''.join(reversed(result))

def subtract_strings(a, b):
    a_len = len(a)
    b_len = len(b)
    max_len = max(a_len, b_len)
    a_zf = a.zfill(max_len)
    b_zf = b.zfill(max_len)
    result = []
    borrow = 0
    for i in reversed(range(max_len)):
        a_digit = int(a_zf[i])
        b_digit = int(b_zf[i])
        a_digit -= borrow
        if a_digit < b_digit:
            a_digit += 10
            borrow = 1
        else:
            borrow = 0
        digit = a_digit - b_digit
        result.append(str(digit))
    res_str = ''.join(reversed(result)).lstrip('0')
    return res_str if res_str != '' else '0'

def compare_strings(a, b):
    if len(a) > len(b):
        return 1
    elif len(a) < len(b):
        return -1
    else:
        for i in range(len(a)):
            if a[i] > b[i]:
                return 1
            elif a[i] < b[i]:
                return -1
        return 0

def mod_string(s, mod):
    result = 0
    for c in s:
        result = (result * 10 + int(c)) % mod
    return result

def main():
    N = input().strip()
    MOD = 1004535809
    if N == '0':
        print(0)
        return
    
    a_list = []
    current = N
    a_list.append(current)
    current = divide_by_two(current)
    while current != "0":
        a_list.append(current)
        current = divide_by_two(current)
    
    n = len(a_list)
    suffix_sum = [None] * (n + 1)
    suffix_sum[n] = "0"
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = add_strings(a_list[i], suffix_sum[i + 1])
    
    max_delta = "0"
    for k in range(1, n + 1):
        idx = k - 1
        a_k_minus_1 = a_list[idx]
        doubled = multiply_by_two(a_k_minus_1)
        sum_suffix = suffix_sum[idx]
        delta = subtract_strings(doubled, sum_suffix)
        if compare_strings(delta, '0') < 0:
            delta = '0'
        if compare_strings(delta, max_delta) > 0:
            max_delta = delta
    
    if max_delta == '0':
        print(0)
    else:
        mod_result = mod_string(max_delta, MOD)
        print(mod_result)

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