「カウント・スリー」問題

「カウント・スリー」問題

締め切りが 2017/09/28 10:00 AM なので，その 1 分後に投稿されるように予約


自然数を 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) の値を出力するプログラムを書いてください。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

「ある数までに何個の 3 があるか」という関数 g を使って，二分法（挟み撃ち法）で解を求める。

g = function(n) {
    ans = 0
    repeat {
        keta = nchar(n) - 1
        m = n %/% (10 ^ keta)
        ans = ans + m * keta * 10 ^ (keta - 1)
        if (m == 3) {
            ans = ans + n - 3 * 10 ^ keta + 1
        } else if (m > 3) {
            ans = ans + 10 ^ keta
        }
        n = n %% (10 ^ keta)
        if (n == 0) {
            break
        }
    }
    return(ans)
}

f = function(n) {
    left = 1
    right = 1000000000000
    repeat {
        middle = (left+right)%/%2
        middle.value = g(middle)-n
        if (middle.value == 0) {
            cat(middle, "\n")
            break
        }
        left.value = g(left)-n
        if (sign(left.value * middle.value) == 1) {
            left = middle
        } else {
            right = middle
        }
    }
}

# f(scan(file("stdin", "r")))

f(5) # 31
f(61) # 300
f(231) # 636
f(45609) # 88534
f(1122334455) # 1273953249
f(991357924680) # 811439945899