Advertisement
Josif_tepe

Untitled

Nov 24th, 2021
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.99 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int dp[100005];
  5. vector<int>p;
  6.  int E;
  7. int rec(int s1){
  8.     if(s1==E){
  9.         return 0;
  10.     }
  11.  
  12.     if(dp[s1]!=-1){
  13.         return(dp[s1]);
  14.     }
  15.  
  16. int result=2e9;
  17.  
  18.     for(int i=0; i<p.size(); i++){
  19.             if((p[i]<s1)and(p[i]+s1<=E)){
  20.                 result=min(result, rec(s1+p[i])+1);
  21.  
  22.             }
  23.     }
  24.     dp[s1]=result;
  25.     return(result);
  26. }
  27. int main()
  28. {
  29.     int S;
  30.     cin>>S>>E;
  31.     for(int i=0; i<100005; i++){
  32.         dp[i]=-1;
  33.     }
  34.  
  35.     for(int i=1; i<=100000; i++){
  36.             vector<int>v;
  37.             int n=i;
  38.             int n1=0;
  39.  
  40.             while(n>0){
  41.             int a=0;
  42.             a=n%10;
  43.             n/=10;
  44.             v.push_back(a);
  45.  
  46.             }
  47.  
  48.             for(int j=0; j<=v.size()-1; j++){
  49.             n1*=10;
  50.             n1+=v[j];
  51.             }
  52.  
  53.             if(n1==i){
  54.                 p.push_back(n1);
  55.             }
  56.  
  57.  
  58.     }
  59.     cout<<rec(S);
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement