记录编号	231745	评测结果	AAAAAAAAAAAWAWWWWEWE
题目名称	1620.[ZOJ 2599]高级字典序	最终得分	60
用户昵称	张灵犀不和我一般见识真可怕呢（笑	是否通过	未通过
代码语言	C++	运行时间	0.321 s
提交时间	2016-02-27 17:49:13	内存使用	0.28 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int SIZEL=20,SIZEN=200;
typedef long long LL;
int f[SIZEL][SIZEN]={0};//长度为L，数位和为N的数的个数
LL n,k;
LL Pow10[SIZEN]={0};
void prepare()
{
	f[0][0]=1;
	for(int i=1;i<=19;i++)
	{
		f[i][0]=1;
		for(int j=1;j<=200;j++)
		{
			f[i][j]=0;
			for(int k=0;k<=9;k++)
			{
				if(j<k) break;
				f[i][j]+=f[i-1][j-k];
			}
		}
	}
	Pow10[0]=1;
	for(int i=1;i<=19;i++) Pow10[i]=10*Pow10[i-1];
}
int digsum(LL x)
{
	int ans=0;
	while(x)
	{
		ans+=x%10;
		x/=10;
	}
	return ans;
}
int dignum(LL x)
{
	int ans=0;
	while(x)
	{
		ans++;
		x/=10;
	}
	return ans;
}
LL clac(LL N,int s)//数位之和小于s且数的大小小于N
{
	int len=dignum(N);
	LL ans=0;
	if(digsum(N)==s) ans++;
	for(int i=len;i>=1;i--)
	{
		int now=N/Pow10[i-1]%10;
		for(int j=0;j<now&&j<=s;j++)
		{
			ans+=f[i-1][s-j];
		}
		if(s<now) break;
		else s-=now;
	}
	return ans;
}
LL sum(LL N,LL K,int s)//如你所见，数位之和小于s且字典序小于K
{
	LL ans=0;
	//cout<<s<<endl;
	for(int i=1;i<s;i++) ans+=clac(N,i);
	int LK=dignum(K),LN=dignum(N);
	LL tem=K;
	for(int i=LK;i>=1;i--)
	{
		ans+=clac(tem,s)-f[i-1][s];
		tem/=10;
	}
	tem=K*10;
	for(int i=LK+1;i<=LN;i++)
	{
		ans+=clac(min(N,tem-1),s)-f[i-1][s];
		tem*=10;
	}
	return ans;
}
int getnumber(LL N,LL K)
{
	int i=1;
	LL tem=0;
	while(true)
	{
		LL now=clac(N,i);
		if(tem+now<K) tem+=now;
		else break;
		i++;
	}
	LL ans=0;
	int s=i;
	while(true)
	{
		int j=0;
		ans*=10;
		while(j<=9)
		{
			if(sum(N,ans+j,s)>=K) break;
			j++;
		}
		ans+=j;
		if(sum(N,ans,digsum(ans))==K) break;
		ans--;
	}
	return ans;
}
int main()
{
	freopen("Lexicographical.in","r",stdin);
	freopen("Lexicographical.out","w",stdout);
	prepare();
	scanf("%lld%lld",&n,&k);
	printf("%lld\n",sum(n,k,digsum(k)));
	printf("%lld",getnumber(n,k));
	return 0;
}