1 条题解

  • 1
    @ 2022-8-25 9:42:48
    #include <iostream>
    #include <stdio.h>
    #include <cstring>
    #define ll long long
    #define filein(a) freopen(a".cpp","r",stdin)
    #define fileout(a) freopen(a".cpp","w",stdout);
    using namespace std;
    
    inline int read(){
    	int sum=0,f=1;char c=getchar();
    	while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
    	while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
    	return sum*f;
    }
    
    const int N=101;
    int K,P,S,D;
    bool f[N][N*9][N][10];
    
    int main(){
    	K=read();S=read();P=read();D=read();
    	if(S>K*9||P>K*9||((S*D%9)^(P%9))){puts("-1");return 0;}
    	f[0][S][P/9][0]=1;
    	for(int i=1;i<K;i++){
    		int S_st=max(S-i*9,0),P_st=max(P-i*9,0);
    		for(int j=S_st;j<=S;j++){
    			for(int l=0;l<D;l++){
    				int mod=(j*D+l)%9;
    				for(int k=P_st/9,realk=k*9+mod;realk<=P;k++,realk+=9){
    					for(int d=0;!f[i][j][k][l]&&d<10;d++){
    						if(f[i-1][j+(l*10+d)/D][(realk+d)/9][(l*10+d)%D]) f[i][j][k][l]=1;
    					}
    				}
    			}
    		}
    	}
    	int st=D;
    	while(st<D*10&&!f[K-1][st/D][(st/10+st%10)/9][st%D]) st++;
    	if(st==D*10){puts("-1");return 0;}
    	printf("%d",st/D);
    	int I=K-1,J=st/D,K=(st/10+st%10),L=st%D;
    	while(I){
    		int d=0;
    		while(!f[I-1][J+(L*10+d)/D][(K+d)/9][(L*10+d)%D]) d++;
    		printf("%d",(L*10+d)/D);
    		I--;J+=(L*10+d)/D;K+=d;L=(L*10+d)%D;
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    4188
    时间
    1000ms
    内存
    250MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者