GCJ 2016 Qualification Round A: Counting Sheep

問題

与えられた非負整数Nについて、N×1,N×2,…とNの倍数をあげていく。その数の10進表記で見た場合の桁が0~9全て出そろった時の最後の数を出力する。(そろわない場合は”INSOMNIA”を出力)

例:N=2の場合、2×1=2,2×2=4,…,2×35=70,…,2×44=88,2×45=90 で0~9が全て出そろうので、結果は 90 となる。

Error 404 (Page not found)!!1

方針

特に最適な解法というのが思いつかなかったので、単純にNの倍数を上げていきチェックする方法をとった。

なお、INSOMNIA になる条件は N=0 の場合とした。

実装

require 'set'

def solve(n)
    return 0 if n == 0

    digits = Set.new
    i = n
    while(true)
        i.to_s(10).chars { |c| digits.add(c) }
        return i if digits.size == 10
        i += n
    end
end

STDIN.gets

i = 1
STDIN.each_line {|line|
    ret = solve(line.to_i)
    if ret == 0 then
        printf "Case #%d: INSOMNIA\n", i
    else
        printf "Case #%d: %d\n", i, ret
    end
    i += 1
}

コメント

タイトルとURLをコピーしました