AOJ 2177 : Champernowne Constant

問題リンク：Champernowne Constant | Aizu Online Judge

問題概要：
int型の変数N,K(1<= N <= 10^9 , 1 <= K <= 100)が与えられる
数字を１から順に並べた文字列(1234567891011・・・)のN番からK個を出力せよ

使用した言語：C++

解法：
N付近の数字を探し、stringにいれて出力した
まず各桁の数字の数を数えてlong longの配列に保存した
long long型の変数totalがN未満であるなら(桁の数字の総数)*(桁数)を加えていった
(桁の数字の総数)*(桁数)を加えるとNを越える場所まできたら、(N-total)/(桁)に桁を掛けたぶんだけ加えていった
一度(N-total)/(桁)で個数を数えたのはその値がその桁に存在する数より大きくないか確かめるため
もしその桁に存在する数より大きいならばその桁に存在する数の総数を代わりに使う

コード：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cassert>
#include<sstream>
using namespace std;

long long d[] = {0,10,90,900,9000,90000,900000,9000000,90000000,900000000,9000000000,90000000000};
int getD(int g){return !g?1:(int)log10(g)+1;}
string itos(int x){stringstream ss; ss << x; return ss.str();}

void print(int now,int K,int dif)
{
  string s;
  for(int i=now;s.size() <= K+dif;i++)
    s += itos(i);
  
  for(int i=dif;i<dif+K;i++)
    cout << s[i];   
  cout << endl;
}

void DO(int N,int K)
{
  long long total = 0;
  int now = 0;
  for(int kt = getD(now);total+kt < N;kt = getD(now))
    {
      if(kt <= 10 && total+kt*d[kt] <= N)
	{
	  total += kt*d[kt];
	  now += d[kt];
	  continue;
	}
      int use = (N-total)/kt;
      if(use > d[kt])
	use = d[kt];
      total += kt*use;
      now+=use;
    } 
  print(now,K,N-total);
}

int main()
{
  int N,K;
  while(cin >> N >> K,N|K)
        DO(N,K);  
 
  return 0;
}