fork download
copy 
  1. #include <iostream>
  2. #include<vector>
  3. #include<string>
  4.  
  5. using namespace std;
  6.  
  7. /*Ham doi cho*/
  8. void Swap(int &a, int &b)
  9. {
  10.     int temp = a;
  11.     a = b;
  12.     b = temp;
  13.     return;
  14. }
  15.  
  16. /*Ham kiem tra 2 chuoi ki tu co bao nhieu lan lap*/
  17. int KtraSolanlap(string str1, string str2)
  18. {
  19.     int dem = 0;
  20.     int j = 0;
  21.     for (int i=0; i<str1.length(); i++)
  22.     {
  23.         while(str2[j]!=str1[i] && j<str2.length())
  24.         {
  25.             j++;
  26.         }
  27.         if (j<str2.length()) dem++;
  28.         j = 0;
  29.     }
  30.     return dem;
  31.     // Ham nay chua hoan hao lam..... Can chinh sua de nhanh hon nua
  32.     // Nhung voi so lieu it, moi sau < 26 ki tu => tam chap nhan.
  33. }
  34.  
  35. /*Ham kiem tra xem co bao nhieu lan lap trong bo test*/
  36. int KtraTEST(vector<string> str, int n)
  37. {
  38.     int dem = 0;
  39.     for (int i=0; i<n-1; i++)
  40.     {
  41.         // Kiem tra chuoi hien tai voi chuoi ke tiep
  42.         int temp = KtraSolanlap(str[i],str[i+1]);
  43.         dem = dem + temp;
  44.     }
  45.     return dem;
  46. }
  47.  
  48. /*Xu li tung hoan vi*/
  49. int XuliHoanVi(int x[], int n, vector<string> str)
  50. {
  51.     int arr[n];
  52.     for (int i=0; i<n; i++)
  53.         arr[i] = x[i+1]-1; // Gan tra lai gia tri arr[0] = 0, arr[1] = 1, arr[2] = 2,...
  54.  
  55.     vector<string> temp;
  56.     for (int i=0; i<n; i++)
  57.         temp.push_back(str[arr[i]]);
  58.  
  59.     int dem = 0;
  60.     dem = KtraTEST(temp,n);
  61.  
  62.     return dem;
  63. }
  64.  
  65. /*ham in cac hoan vi*/
  66. void InHoanVi(int n, vector<string> str)
  67. {
  68.     int x[n+1];
  69.     int i;
  70.     int k;
  71.     int dem = 0, min = KtraTEST(str,n);
  72.     for (int j=1; j<=n; j++)
  73.         x[j] = j; // Khoi tao x[1] = 1, x[2] = 2, ...
  74.     do
  75.     {
  76.         dem = XuliHoanVi(x,n,str);
  77.         if (dem < min) min = dem;
  78.  
  79.         i = n-1;
  80.         while(i>0 && x[i] > x[i+1]) i--;
  81.         if (i>0) // Chua gap phai phan tu cuoi day
  82.         {
  83.             k = n; // x[k] la phan tu cuoi day
  84.             while(x[k] < x[i]) k--; // Lui dan k de tim phan tu x[k] dau tien lon hon x[i]
  85.             Swap(x[k],x[i]); // Doi cho x[k] cho x[i]
  86.  
  87.             int a = i+1, b = n; // Lat nguoc doan cuoi giam dan, a : dau doan, b : cuoi doan
  88.             while(a<b)
  89.             {
  90.                 Swap(x[a],x[b]);
  91.                 a++;
  92.                 b--;
  93.             }
  94.         }
  95.     } while (i>0);
  96.     cout << min << endl;
  97. }
  98. int main()
  99. {
  100.  
  101.     vector<string> str;
  102.     int n;
  103.  
  104.     // Nhap du lieu
  105.  
  106.     cin >> n;
  107.     for (int i=0; i<n; i++)
  108.     {
  109.         string temp;
  110.         cin >> temp;
  111.         str.push_back(temp);
  112.     }
  113.  
  114.  
  115.  
  116.     InHoanVi(n,str);
  117.     //cout << KtraTEST(str,n);
  118.     return 0;
  119. }
Time limit exceeded #stdin #stdout 5s 5204KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9PKAPQ
language:
C++ (gcc 8.3)
created:
5 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!