Advertisement
Josif_tepe

Untitled

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