Advertisement
Josif_tepe

Untitled

Mar 20th, 2024
713
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 s,e;
  5. vector <int> v;
  6. int dp[100000];
  7. int rek(int x)
  8. {
  9.     if(x==e)
  10.     {
  11.         return 0;
  12.     }
  13.     if(dp[x]!=-1)
  14.     {
  15.         return dp[x];
  16.     }
  17.     int rez=1e5;
  18.     for(int i=0;i<v.size();i++)
  19.     {
  20.         if(v[i]<x && v[i]+x<=e)
  21.         {
  22.             rez=min(rez,rek(x+v[i])+1);
  23.         }
  24.     }
  25.     dp[x]=rez;
  26.     return rez;
  27. }
  28.  
  29. int main()
  30. {
  31.     cin>>s>>e;
  32.    
  33.     for (int i=0;i<100000;i++)
  34.     {
  35.         dp[i]=-1;
  36.     }
  37.     for(int i=1;i<100000;i++)
  38.     {
  39.         int cifri[6]={-1};
  40.         int j=0;
  41.         int il=i;
  42.         while(il>0)
  43.         {
  44.             cifri[j]=il%10;
  45.             j++;
  46.             il/=10;
  47.         }
  48.         int k=0;
  49.         for(int y=0;y<j;y++)
  50.         {
  51.             if(cifri[y]!=cifri[j-y-1])
  52.             {
  53.                k=-1;
  54.             }
  55.         }
  56.         if(k==0)
  57.         {
  58.             v.push_back(i);
  59.         }
  60.     }
  61.     cout<<rek(s);
  62.     return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement