C = [1i64, 0i64, 0i64, 0i64, 1i64, 0i64, 1i64, 0i64, 2i64, 1i64] CS = [0i64] C.size.times do |i| CS << CS[i] + C[i] end CNT = [0i64, CS[-1]] 1.upto(16) do |i| CNT << CNT[i] + (CS[-1] - 1) * (10i64 ** i) + CS[-1] * 9 * (10i64 ** (i - 1)) * i end k = read_line.to_i64 + 1 lo = 0i64 hi = 100000000000000000i64 while hi - lo > 1 mid = (lo + hi) // 2 # puts [mid, cnt(mid, mid.to_s.size - 1, 1)] if cnt(mid, mid.to_s.size - 1, 1) > k hi = mid else lo = mid end end puts cnt(lo, lo.to_s.size - 1, 1) == k ? lo : -1 def cnt(v, len, first) if len == 0 return CS[v + 1] end hi = v // (10i64 ** len) rest = v - hi * (10i64 ** len) ret = 0i64 if first == 1 ret += CNT[len] end ret += (CS[hi] - first) * (10i64 ** len) ret += (hi - first) * CS[-1] * (10i64 ** (len - 1)) * len ret += C[hi] * (rest + 1) ret += cnt(rest, len - 1, 0) # puts [v, len, ret] return ret end