結果

問題 No.491 10^9+1と回文
ユーザー lam6er
提出日時 2025-03-20 18:59:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 46 ms / 1,000 ms
コード長 1,489 bytes
コンパイル時間 172 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 53,960 KB
最終ジャッジ日時 2025-03-20 19:00:38
合計ジャッジ時間 7,212 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 103
権限があれば一括ダウンロードができます

ソースコード

diff # 

def count_palindromes(M):
    def generate_palindrome(prefix, is_even):
        s = str(prefix)
        if is_even:
            other = s[::-1]
        else:
            other = s[:-1][::-1]
        combined = s + other
        return int(combined)
    
    s = str(M)
    n = len(s)
    total = 0

    for d in range(1, n + 1):
        if d == 1:
            add = min(9, M)
            if add >= 1:
                total += add
            continue

        is_even = (d % 2 == 0)
        half = d // 2

        prefix_len = half if is_even else half + 1
        min_prefix = 10 ** (prefix_len - 1)
        max_prefix = 10 ** prefix_len - 1

        if min_prefix > max_prefix:
            continue

        max_pali = generate_palindrome(max_prefix, is_even)
        if max_pali <= M:
            count = max_prefix - min_prefix + 1
            total += count
        else:
            low = min_prefix
            high = max_prefix
            best = min_prefix - 1
            while low <= high:
                mid = (low + high) // 2
                pali = generate_palindrome(mid, is_even)
                if pali <= M:
                    best = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if best >= min_prefix:
                count = best - min_prefix + 1
                total += count

    return total

N = int(input())
mod = 10**9 + 1
M = N // mod

if M == 0:
    print(0)
else:
    print(count_palindromes(M))
0