v 0. Pasted by slipstak2 as cpp at 2011-01-11 14:13:13 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 14.
  2. // 14C. Упаковка символов [folding]
  3. // ibelyaev: 10Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <string>
  8. #include <vector>
  9.  
  10. using namespace std;
  11. const int MAX_LEN = 1e9;
  12. int n;
  13. string str;
  14. vector<vector<int> > mas;
  15. void input()
  16. {
  17.     cin>>str;
  18.     n = str.size();
  19.     mas = vector<vector<int> >(n,vector<int>(n,0));
  20. }
  21. int count(int num)
  22. {
  23.     int amount = 0;
  24.     while (num) {
  25.         num/=10;
  26.         amount++;
  27.     }
  28.     return amount;
  29. }
  30. string getAnswer(int i, int j) {
  31.  
  32.     if (i == j)
  33.         return string(&str[i],1);
  34.     int res = MAX_LEN;
  35.     int LEN = j - i + 1;
  36.     for (int step = 1; step <= LEN / 2; step++)
  37.     {
  38.         if (LEN % step != 0) continue;
  39.         bool isOK = true;
  40.         for (int cur = 0; cur<step; cur++) {
  41.             for (int pos = i + cur; pos<=j; pos+=step) {
  42.                 if (str[i+cur] != str[pos]) {
  43.                     isOK = false;
  44.                     break;
  45.                 }
  46.             }
  47.         }
  48.         if (isOK) {
  49.             int curLen = count((j-i+1) / step) + 2 + mas[i][i+step-1];
  50.             if (curLen == mas[i][j]) {
  51.  
  52.                 char buf[10];
  53.                 sprintf(buf,"%d",(j-i+1) / step);
  54.                 return string(buf) + "(" + getAnswer(i,i+step-1) + ")";
  55.             }
  56.  
  57.         }
  58.     }
  59.  
  60.     for (int m = i; m<j; m++)
  61.         if (mas[i][m] + mas[m+1][j] == mas[i][j])
  62.             return getAnswer(i,m) + getAnswer(m+1,j);
  63. }
  64. void solve()
  65. {
  66.     for (int len = 0; len < n; len++) {
  67.         for (int i=0;i<n; i++) {
  68.             int j = i + len;
  69.             if (j >= n) break;
  70.  
  71.             if (len == 0) mas[i][j] = 1;
  72.  
  73.             else {
  74.                 int res = MAX_LEN;
  75.                 int LEN = j - i + 1;
  76.                 for (int step = 1; step <= LEN / 2; step++)
  77.                 {
  78.                     if (LEN % step != 0) continue;
  79.                     bool isOK = true;
  80.                     for (int cur = 0; cur<step; cur++) {
  81.                         for (int pos = i + cur; pos<=j; pos+=step) {
  82.                             if (str[i+cur] != str[pos]) {
  83.                                 isOK = false;
  84.                                 break;
  85.                             }
  86.                         }
  87.                     }
  88.                     if (isOK) {
  89.                         int curLen = count( LEN / step) + 2 + mas[i][i+step-1];
  90.                         res = min(res,curLen);
  91.                     }
  92.                 }
  93.  
  94.                 for (int m = i; m<j; m++)
  95.                     res = min(res,mas[i][m] + mas[m+1][j]);
  96.  
  97.                 mas[i][j] = res;
  98.             }
  99.         }
  100.     }
  101.  
  102.     string ans = getAnswer(0,n-1);
  103.     cout<<ans;
  104. }
  105. int main()
  106. {
  107.     freopen("input.txt","r",stdin);
  108.     freopen("output.txt","w",stdout);
  109.  
  110.     input();
  111.     solve();
  112.     return 0;
  113. }


Editing is locked.