Advertisement
Patrickmeme

Removing Digits

Jun 14th, 2023
727
0
Never
2
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.70 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int v[1000001];
  5.  
  6. int se_gaseste(int a,int cif){
  7.     while(a>0 && a%10!=cif)
  8.         a/=10;
  9.     if(a>0)
  10.         return 1;
  11.     else
  12.         return 0;
  13. }
  14.  
  15. int main()
  16. {
  17.     int n,i,j,stop;
  18.     cin>>n;
  19.     v[n]=0;
  20.     for(i=n-1;i>=0;i--)
  21.         v[i]=-1;
  22.     for(i=n-1;i>=0;i--){
  23.         stop=min(9,n-i);
  24.         for(j=1;j<=stop;j++){
  25.             if(v[i+j]>-1 && se_gaseste(i+j,j)==1){
  26.                 if(v[i]==-1){
  27.                     v[i]=v[i+j]+1;
  28.                 }else{
  29.                     v[i]=min(v[i+j]+1,v[i]);
  30.                 }
  31.             }
  32.         }
  33.         ///printf("i:%d v[i]:%d\n",i,v[i]);
  34.     }
  35.     cout<<v[0];
  36.     return 0;
  37. }
Advertisement
Comments
Add Comment
Please, Sign In to add comment
Advertisement