結果

問題 No.528 10^9と10^9+7と回文
ユーザー mai
提出日時 2017-06-09 23:48:03
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 955 bytes
コンパイル時間 341 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 19,236 KB
最終ジャッジ日時 2024-09-22 20:07:33
合計ジャッジ時間 4,166 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 5 TLE * 1 -- * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

def ascan; gets.split.map(&:to_i); end
def scan; gets.to_i; end

@md = 1
# 1以上10^i-1以下の整数
def _kaibunsu_dec(keta)
    return 9 if (keta <= 1)
    r = 1
    ((keta + 1) / 2).times{r*=10}
    return r - (r / 10) + _kaibunsu_dec(keta-1)
end

# dfs列挙
def _kaibunsu_dfs(low, high, kcl, kch, num=0)
    return low <= num && num <= high ? 1 : 0 if kcl > kch
    result = 0
    (kcl == 1 ? 1 : 0).upto(9){|k|
        result = (result + _kaibunsu_dfs(low, high, kcl * 10, kch / 10, num + kcl*k + kch*k*(kcl != kch ? 1 : 0)))%@md
    }
    return result
end

# 1以上val以下の整数で回文数が何個あるか
def kaibunsu(val)
    return val if (val <= 9)
    dec = 1
    keta = 0
    while (val >= dec)
        dec *= 10; ++keta;
    end
    dec /= 10;
    
    return _kaibunsu_dfs(dec, val, 1, dec) + _kaibunsu_dec(keta - 1);
end

# (´・ω・｀)
n = gets.to_i
@md = 10000000007
p kaibunsu(n)%@md
@md = 10000000000
p kaibunsu(n)%@md
0