fork(2) download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<map>
  4. using namespace std;
  5. int mat[10][10];
  6. map<int,int>m;
  7. void update(int a){
  8.      //cout<<"yes"<<a;
  9.      int i;
  10.      for(i=0;i<10;i++)
  11.      {
  12.                       if(m[i]>mat[i][a]+m[a]+1)
  13.                       {
  14.                                              m[i]=1+mat[i][a]+m[a];
  15.                                              update(i);
  16.                       }
  17.      }
  18.      }
  19. int main(){
  20.     for(int o=0;o<10;o++)
  21.     for(int p=0;p<10;p++)
  22.     mat[o][p]=30;
  23.     char carr[100005];
  24.     scanf("%s",carr);
  25.     char ch;
  26.     ch=carr[0];
  27.     int i;
  28.     for(int i=0;i<=9;i++)
  29.     m[i]=40;
  30.     int current=0;
  31.     int a=ch-48;
  32.     m[a]=1;
  33.     ch=carr[1];
  34.     i=0;
  35.     int arr[100000];
  36.     arr[i]=a;
  37.     i++;
  38.     int ind=1;
  39.     while(ch!='\0'){
  40.                     int a=ch-48;
  41.                     if(i>2)
  42.                     if(arr[i-1]==a&&arr[i-2]==a)
  43.                     goto A;
  44.                     else
  45.                     arr[i]=a;
  46.                     else
  47.                     arr[i]=a;
  48.                     current++;
  49.                     if(m[a]<=current){
  50.                     current=m[a];
  51.                     update(a);
  52.                     }
  53.                     else
  54.                     m[a]=current+1;
  55.                     for(int j=1;j<40&&i-j>-1;j++)
  56.                     {
  57.                             if(mat[arr[i-j]][a]>j)
  58.                             {
  59.                                                   mat[arr[i-j]][a]=j;
  60.                                                   mat[a][arr[i-j]]=j;
  61.                             }
  62.                             if(m[arr[i-j]]>(1+current+j))
  63.                             {
  64.                                                          m[arr[i-j]]=(current+j+1);
  65.        //                                                  cout<<"A"<<a<<"IJ"<<i-j;
  66.                                                          update(arr[i-j]);
  67.                             }
  68.                     }i++;
  69.                     A:;
  70.                     ind++;
  71.                     ch=carr[ind];
  72.  
  73.                     }
  74.     printf("%d\n",current);
  75.  
  76.     cin.get();
  77.  
  78.     }
  79. //01982872437567701452
  80. //112233445566778899
  81. //11223344556677-
  82. //988991211223364779911223365482223489-3
  83. //1155334411335533774477226688-11
  84. //99887766446688776655334455697755887554-5
  85. //099887766554433223300885577-5
  86. //016273849567165299885-5
  87. //
  88.  
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
7711965557423006
stdout
copy 
5
https://ideone.com/rcZw8e
language:
C++ 4.3.2 (gcc-4.3.2)
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!