結果

問題 No.1953 ８
ユーザー tomerun
提出日時 2022-05-20 23:43:02
言語 Crystal
(1.14.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 914 bytes
コンパイル時間 14,720 ms
コンパイル使用メモリ 296,348 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-20 10:10:44
合計ジャッジ時間 15,331 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

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
0