记录编号	243517	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]Digit	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	2.689 s
提交时间	2016-03-30 09:17:32	内存使用	126.67 MiB

#include<cstdio>
#include<iostream>
#include<string>
#include<deque>
#include<cstring>
#include <sstream>
using namespace std;
const int MAXN=910;
int d,s1,s2;
int n;
class miku
{
public:
	int s1,s2,r;
	void print()
	{
		cout<<s1<<" "<<s2<<" "<<r<<endl;
	}
};
deque<miku> Q;
int Len[MAXN*2][MAXN*2][10];//A的位数和为i，A*D除第n+1外位数和为j，A*D的第n+1位为k,A的最少位数
void prepare()
{
	memset(Len,0x7F,sizeof(Len));
	miku tem;
	for(int i=0;i<10;i++)
	{
		tem.s1=i;
		tem.s2=i*d%10;
		tem.r=i*d/10;
		Q.push_back(tem);
		Len[tem.s1][tem.s2][tem.r]=1;
	}
	Len[0][0][0]=0;
	while(!Q.empty())
	{
		miku S=Q.front();Q.pop_front();
		for(int i=0;i<=9;i++)
		{
			tem.s1=S.s1+i;
		    tem.s2=S.s2+(S.r+i*d)%10;
		    tem.r=(S.r+i*d)/10;
			//tem.print();
			if(tem.s1>s1||tem.s2>s2) continue;
			if(Len[tem.s1][tem.s2][tem.r]>Len[S.s1][S.s2][S.r]+1)
			{
				Len[tem.s1][tem.s2][tem.r]=Len[S.s1][S.s2][S.r]+1;
				Q.push_back(tem);
			}
		}
	}
}
void get(ostringstream &oss,int len,int S1,int S2,int R)
{
	for(int i=0;i<len;i++)
	{
		bool ok=0;
		for(int j=0;j<=9;j++)
		{
			for(int k=0;k<=9;k++)
			{
				int ns1=S1-j,ns2=S2-k;
				int nr=R*10-j*d+k;
				if(nr<0||nr>9) continue;
				if(ns1<0||ns2<0)continue;
				if(Len[ns1][ns2][nr]>len-i-1)continue;
				S1=ns1,S2=ns2,R=nr;
				//cout<<i<<endl;
				oss<<j;
				ok=1;
				break;
			}
			if(ok==1) break;
		}
		if (ok==0)
		{
			for(int j=i;j<len;j++) oss<<"0";
			return;
		}
	}
}
int getsum(int x)
{
	int re=0;
	while(x)
	{
		re+=x%10;
		x/=10;
	}
	return re;
}
string ans;
void Calc(int i,ostringstream &tem)
{
	string now=tem.str();
	//cout<<now<<endl;
	ostringstream tem2;
	tem2<<i;
	for(int u=0;u<n-now.length()-1;u++) tem2<<"0";
	tem2<<now;
	now=tem2.str();
	if(now.size()<ans.size()||(now.size()==ans.size()&&now<ans)) ans=now;
}
void work()
{
	ans="";
	for(int i=0;i<=MAXN+1;i++) ans+="9";
	//cout<<ans<<endl;
	for(int i=1;i<=9;i++)//枚举首位，因为不能有前导0
	{
		int ns=s1-i;
		if(ns<0) continue;
		for(int j=0;j<=9;j++)
		{
			for(int k=0;k<=s2;k++)
			{
				if(Len[ns][k][j]>n-1) continue;
				if(k+getsum(j+i*d)==s2)
				{
					ostringstream tem;
					//cout<<ns<<" "<<k<<" "<<j<<" "<<Len[ns][k][j]<<endl;
					get(tem,n-1,ns,k,j);
					Calc(i,tem);
				}
				if(Len[ns][k][j]<n-1&&k+j+getsum(i*d)==s2)
				{
					ostringstream tem;
					//cout<<ns<<" "<<k<<" "<<j<<" "<<Len[ns][k][j]<<endl;
					get(tem,Len[ns][k][j],ns,k,j);
					Calc(i,tem);
				}
			}
		}
	}
	if(ans.size()>MAXN) printf("-1\n");
	else cout<<ans<<endl;
}
int main()
{
	freopen("nt2011_digit.in","r",stdin);
	freopen("nt2011_digit.out","w",stdout);
	scanf("%d%d%d%d",&n,&s1,&s2,&d);
	prepare();
	work();
	//cout<<Len[9][9][0]<<endl;
	return 0;
}