Description:
1以上N以下の数を、10進表記し、辞書式順で並び替えた時に、数KがM番目に来るという事を、Q(N,K)=Mと表す。
K,Mが与えられるので、Q(N,K) = Mが成り立つ最小のNを探せ。
存在しないなら、0を表示せよ。
1 <= K,M <= 10^9
Answer:
Nが増加すれば、Q(N,K)の値は増加する。
また、答えは最小でK、最大でも100000000888888879LLである。
以上のことより、Q(N,K)とMを比較しながら、Nをバイナリサーチしてやる事で、解の候補を絞る事が可能。
あとは、計算途中のオーバーフロー(9*10^18はsigned long longに入らない)と、バイナリサーチで残った候補が正しくMを返すかだけ注意してやればよい。
Source: