結果

提出番号	2011
提出者	popo
言語	C++
提出日時	2018-08-04 14:55:27
問題名	(72)K-th DigitSum
結果	WA
点数	0%

---

テストケース

ソースコード

#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;

struct X{
  int id,su,di;
  X(){di=-1;}
  X(int a,int c){
    id=a;

    su=c;
    
  }
};


int dp[1002][1009],n,k;
X pre[1002][1009],p[1002][1009];

int prin1(int a,int c){
  string ans="";
  int a1=a,c1=c,d,d1;
  while(a!=1001){
    int A=pre[a][c].id;

    int C=pre[a][c].su;
    int D=abs(c-C);
    a=A;

    c=C;
    d=D;
    ans+=('0'+d);
  }
  //reverse(ans.begin(),ans.end());
  while(1){
    if(c1==0)break;
    int A=p[a1][c1].id;

    int C=p[a1][c1].su;
    int D=abs(c1-C);
    a1=A;

    c1=C;
    d1=D;
    ans+=('0'+d1);
  }
  reverse(ans.begin(),ans.end());
  cout<<ans<<endl;
  exit(0);
}

int dfs1(int idx,int sum=0){
  if(idx==1001)return sum==n;
  int &res=dp[idx][sum];
  if(~res)return res;
  res=0;
  for(int i=0;i<=9;i++){
    if(sum+i>n)continue;
    p[idx+1][sum+i]=X(idx,sum);
    res+=dfs1(idx+1,sum+i);
    pre[idx][sum]=X(idx+1,sum+i);
    if(res==k){
      prin1(idx,sum);
    }
  }
  return dp[idx][sum]=res;
}

int prin(int a,int c){
  string ans="";
  int a1=a,c1=c,d,d1;
  while(a!=1001){
    int A=pre[a][c].id;

    int C=pre[a][c].su;
    int D=abs(c-C);
    a=A;

    c=C;
    d=D;
    ans+=('0'+d);
  }
  //reverse(ans.begin(),ans.end());
  while(1){
    if(c1==0)break;
    int A=p[a1][c1].id;

    int C=p[a1][c1].su;
    int D=abs(c1-C);
    a1=A;

    c1=C;
    d1=D;
    ans+=('0'+d1);
  }
  reverse(ans.begin(),ans.end());
  int idx=0;
  while(ans[idx]=='0')idx++;
  ans=ans.substr(idx);
  k=(int)ans.size()-k+1;
  memset(dp,-1,sizeof(dp));
  dfs1(0);
  exit(0);
}


int dfs(int idx,int sum=0){
  if(idx==1001)return sum==n;
  int &res=dp[idx][sum];
  if(~res)return res;
  res=0;
  for(int i=0;i<=9;i++){
    if(sum+i>n)continue;
    p[idx+1][sum+i]=X(idx,sum);
    res+=dfs(idx+1,sum+i);
    pre[idx][sum]=X(idx+1,sum+i);
    if(res==12+1){
      prin(idx,sum);
    }
  }
  return dp[idx][sum]=res;
}

int main(){
  memset(dp,-1,sizeof(dp));
  cin>>n>>k;
  dfs(0);
}