fork download
copy 
  1. #include<stdio.h>
  2. #include<string.h>
  3. # define max 1000002
  4. char a[100005];
  5. long long int jump[100005]; 
  6. int status[10]={0};
  7. long long int indx;
  8. void editarray(long long int n)
  9. { long long int i,j,a1,b,b1;
  10.   j=indx+1;
  11.   //printf("%d",j);
  12.    int c=10;
  13.     while(j<n)
  14.   { for(i=indx+1;i<n;i++)
  15.      { a1=a[i]-'0';
  16.        b1=a[indx]-'0';
  17.        if(a1==b1)  
  18.        break;   
  19.  
  20.      }
  21.     if(i==n)
  22.      { for(j=indx+1;j<i;j++)
  23.        {  if(jump[j]>jump[indx]+j-indx) 
  24.         jump[j]=jump[indx]+j-indx;
  25.        }
  26.       break;
  27.      }
  28.    else
  29.    { for(j=indx+1;j<i;j++) 
  30.       { a1=jump[indx]+j-indx;
  31.          b=jump[i]+i-j;
  32.          if(jump[j]>a1)
  33.          jump[j]=a1;
  34.          if(jump[j]>b)
  35.          jump[j]=b; 
  36.      }
  37.    }
  38.   indx=i; 
  39.  } 
  40.  
  41. }
  42.  
  43. int finddistinct(long long int n)
  44. {  int a1;
  45.   long long int i; 
  46.   for(i=0;i<n;i++)
  47.    { a1=a[i]-'0';
  48.     if(status[a1]==0)
  49.      { a1=a[i]-'0';
  50.         indx=i;
  51.       // printf("%lld ",i); 
  52.        status[a1]=1;
  53.        return a1;
  54.  
  55.      }
  56.    }
  57.  return -1;
  58. }
  59. long long int caldistinct(long long int n,long long int x)
  60. { long long int min=max;
  61.    long long int temp,i; 
  62.   if(x==a[0]-'0')
  63.   return 0;
  64.   for(i=0;i<n;i++) 
  65.      { if(i==indx)
  66.         continue;
  67.        if(i<indx)
  68.        temp=indx-i;
  69.        else
  70.        temp=i-indx;
  71.        if(jump[i]+temp<min)
  72.        min=jump[i]+temp;
  73.      }
  74. return min;
  75. }
  76. long long int caljump()
  77. { long long int a1,c,i,n,min,d,e;
  78.   int b,temp,b1;
  79.   n=strlen(a);
  80.   for(i=0;i<n;i++)
  81.    jump[i]=1000000;
  82.   char *s=a;
  83.   a1=*s-'0';
  84.   if(a[n-1]==a[0])
  85.   return 1;
  86.   int count =10; 
  87.   while(count--)
  88.   { temp=0;
  89.     b=finddistinct(n);
  90.     if(b<0)
  91.     return;
  92.     a1=caldistinct(n,b);
  93.     c=a[n-1]-'0';
  94.     min=max;
  95.     for(i=0;i<n;i++)
  96.     {b1=a[i]-'0';
  97.      if(b1==b&&jump[i]<min)
  98.      min=jump[i];
  99.      if(b1==b&&temp==1)
  100.     { if(jump[i]>a1+1)
  101.          jump[i]=a1+1;
  102.     //  printf("%d ",b1);
  103.     }
  104.    if(b1==b&&!temp)
  105.     { if(jump[i]>a1);
  106.       { jump[i]=a1;
  107.         temp=1;
  108.       }   
  109.     }   
  110.  
  111.     }  
  112.    for(i=0;i<n;i++)
  113.     {b1=a[i]-'0';
  114.      if(b1==b&&jump[i]>min)
  115.      { // printf("%lld %d      ",i,b);
  116.        jump[i]=min+1;
  117.      }   
  118.     } 
  119.   // for(d=0;c<n;d++)
  120.    // printf("%lld\n",jump[d]); 
  121.    editarray(n);
  122.   }
  123.  
  124. }
  125.  int main () 
  126. {
  127. 	long long  int b,c;
  128.  	scanf("%s",a);
  129. 	b=strlen(a);
  130. 	c=caljump();
  131.     if(c==1)
  132.     printf("1\n");
  133. 	else
  134. 	//for(c=0;c<b;c++)
  135.     printf("%lld\n",jump[b-1]);
  136. 	return 0;
  137. }
Success #stdin #stdout 0s 3176KB
comments (?)
stdin
copy 
0123412367
stdout
copy 
6
https://ideone.com/p0KN5v
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!