[今日の見出し]辞書順

1562 ワード

    
									

  n m, 1 n n , m 。 n = 11,m = 4, 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 4 2。
 
入力入力には2つの整数nとmのみが含まれます. 
サンプル入力11 4
出力出力は、求めた配列のm番目の数字の1行のみを含む. 
サンプル出力2
時間制限C/C++言語:1000 MSその他言語:3000 MS
メモリ制限C/C++言語:65536 KBその他言語:589824 KB
 
 
ディクショナリシーケンスである以上,自然にディクショナリツリーを用いて実現することが考えられるが,ここでは本当にこのディクショナリツリーを生成する必要はなく,対応するブランチのノード数を計算するだけでよい.1.まず1から、1分岐のノード数>mであれば、m番目の数は必ず1で始まる、さらにそのサブノードを検索し、サブノードを検索する際に1を検索する必要はないので、1分岐のm-1番目のノードを検索する.2.1ブランチのノード数
 
#include
#include
using namespace std;

long long getCountOfstart(long long start, long long n)//    n , ret       
{
    long long base =1,count = 0;
    while(n>=(start+1)*base -1)
    {
        count += base;
        base = base*10;
    }
    if(n >= start*base )
        count += n-start*base+1;
    return count;
}


long long getNum(long long m,long long n)
{
    long long k = 1;
    while(m!=0)
    {
       long long count = getCountOfstart(k, n);
       if(count >= m)//         m , m          ,res*10        ,m  1,  m=0        
       {
           m--;
           if(m==0)
               break;
           k = k*10;
       }
       else//       m , m                ,m        ,   1           
       {
           k++;
           m = m -count;
       }
    }
    return k;
}
int main()
{
    long long n,m;
    cin>>n>>m;
    cout<