私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「カウント・スリー」（CodeIQ）を参照してください。
自然数を 1 から順に書き並べていきます。
このとき、3 の数字が現れる回数を数えます。
自然数 n に対し、ちょうど n 個目の 3 の数字が現れたときに書いている数を F(n) と定義します。
例えば F(10)＝35 です。
下の通り、10 個目の 3 は、35 を書いているときに現れます。
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, …
同様に、F(3)＝23, F(7)＝33, F(8)＝33, F(1000)＝3081 となることが確かめられます。
（「33」には 3 が 2 回現れるため、それぞれの 3 を別々に数える点に注意してください。）
標準入力から、自然数 n （1 ≦ n ≦ 1012）が与えられます。
標準出力に F(n) の値を出力するプログラムを書いてください。
Rubyで解答しています。
#!/usr/bin/ruby
def countPlace(n, pl)
mask = 10**pl
now = (n / mask) % 10 # 現在の桁の値
left = n - n % (mask*10) # 現在よりも上の桁の値
if now < 3 then return left / 10
elsif 3 < now then return (left + (mask * 10)) / 10
else return left/10 + (n % mask) + 1
end
end
def count(n)
ret = 0
for i in 0...n.to_s.size
ret += countPlace(n, i)
end
return ret
end
def solve(n)
mn = 1
mx = 10
loop{
break if count(mx) > n
mn *= 10
mx *= 10
}
loop {
ret = (mx + mn) / 2
c = count(ret)
# printf("mn=%d, mx=%d, ret=%d, c=%d\n", mn, mx, ret, c)
if c < n then mn = ret + 1
else
if mx == mn then return ret
else mx = ret
end
end
}
end
# main
while line = gets
line.strip!
next if line.empty?
p solve(line.to_i)
end
★★★の問題ですが、問題の半分は過去にやったことがあったのでそれほどでもありませんでした。その経験がなければ難しかったと思います。
入力値を数値にしてsolve()に渡し、結果を印字します。
mnは探索の下限、mxは探索の上限で、初期値はそれぞれ1と10です。
28〜32行目のループでmn,mxを10倍しながらmx以下の3の個数をcount()でチェックし、入力値を超えたところでmn,mxを確定します。
34〜46行目のループが二分探索です。mn,mxの真ん中の値をチェックし、結果が入力値より小さかったらmnを探索した値にします。それ以外の場合でmx=mnの場合はその場所が答えになるのでretを返却し、そうでなければmxを更新します。
入力値が7や8の場合、33が答えになるので探索対象の数が33の時はcount()は8を返し、32の時は6を返すのでちょうど7を返す場合を探索すると探索が終わらなくなります。なのでmn=mxを終了条件とする必要があります。
「「7」の数を数えよう」の実装と同じですのでそちらの説明を参照してください。
この出題者の問題の傾向からゆくと計算だけで答えを求める方法があるのではないか、と思いますが私にはわかりません。多分、もっとうまい方法があるのでは、と思います。