「カウント・スリー」問題
締め切りが 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
