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

Paste will expire never.

  1. // Меньшиков. Тренировка 14.
  2. // 14A. Марковский цикл [markovc]
  3. // ibelyaev: 09Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <string>
  8. #include <set>
  9. #include <vector>
  10. #include <map>
  11.  
  12. using namespace std;
  13. const int osn = 3;
  14. int calcHash(const string &str)
  15. {
  16.     int hash = 0;
  17.     for (int i=0;i<str.size();i++) {
  18.         hash = hash * osn + str[i] -'A';
  19.     }
  20.     return hash;
  21. }
  22. struct rule
  23. {
  24.     string L;
  25.     string R;
  26.     int hash;
  27.     rule(){}
  28.     rule(string left, string right)
  29.     {
  30.         L = left;
  31.         R = right;
  32.         hash = calcHash(left);
  33.     }
  34. };
  35. struct entry
  36. {
  37.     int H;
  38.     int P;
  39.     entry(){H = 0; P = 0;}
  40.     entry(int hash, int pos)
  41.     {
  42.         H = hash;
  43.         P = pos;
  44.     }
  45. };
  46. bool operator < (const entry &a, const entry &b)
  47. {
  48.     return a.H < b.H;
  49. }
  50. vector<rule> rules;
  51. string str;
  52. void trim(string &str)
  53. {
  54.     while (str[0] == ' ')
  55.         str.erase(0,1);
  56.  
  57.     while (str[str.size() - 1] == ' ')
  58.         str.erase(str.size()-1, 1);
  59. }
  60. void input()
  61. {
  62.     getline(cin, str);
  63.     trim(str);
  64.     string buf,left,right;
  65.     while(getline(cin,buf)) {
  66.         int pos = buf.find('-');
  67.         left = buf.substr(0,pos);
  68.         right = buf.substr(pos+2,buf.size() - (pos+2));
  69.         trim(left); trim(right);
  70.         rules.push_back(rule(left,right));
  71.     }
  72. }
  73. typedef set<entry> S_ENT;
  74. vector<int> step;
  75. vector<S_ENT > sizeHash;
  76. vector<int> curHash;
  77. void recalcSizeHash()
  78. {
  79.     for (int i=0;i<sizeHash.size();i++)
  80.         sizeHash[i].clear();
  81.     curHash.assign(curHash.size(), 0);
  82.  
  83.     for (int i=0; i<=str.size();i++)
  84.     {
  85.         int c = i == str.size() ? 0 :str[i] - 'A';
  86.         for (int j=0; j < curHash.size(); j++)
  87.         {
  88.             if (i <= j)
  89.                 curHash[j] = curHash[j] * osn + c;
  90.             else {
  91.                 entry curEntry(curHash[j],i-1-j);
  92.  
  93.                 if (sizeHash[j].find(curEntry) == sizeHash[j].end())
  94.                     sizeHash[j].insert(curEntry);
  95.  
  96.                 curHash[j] = (curHash[j] % step[j]) * osn + c;
  97.             }
  98.         }
  99.     }
  100. }
  101. vector<int> mem(531442,-1);
  102. void solve()
  103. {
  104.     step.resize(str.size());
  105.     step[0] = 1;
  106.     for (int i=1;i<step.size();i++)
  107.         step[i] = step[i-1] * osn;
  108.     sizeHash.resize(str.size());
  109.     curHash.resize(str.size(),0);
  110.    
  111.     bool isOK;
  112.     int stepAmount = 0;
  113.     int perLen = 0;
  114.     do
  115.     {
  116.         int memPos = calcHash(str);
  117.         if (mem[memPos] != -1) {
  118.             perLen = stepAmount - mem[memPos];
  119.             stepAmount = mem[memPos] + 1;
  120.             break;
  121.         }
  122.         else
  123.             mem[memPos] = stepAmount++;
  124.  
  125.         isOK = false;
  126.         recalcSizeHash();
  127.         int len;
  128.         entry curE;
  129.         S_ENT::iterator it;
  130.         for (int i=0;i<rules.size();i++)
  131.         {
  132.             len = rules[i].L.size() - 1;
  133.             curE.H = rules[i].hash;
  134.             if (len < sizeHash.size()) {
  135.                 it  = sizeHash[len].find(curE);
  136.                 if (it != sizeHash[len].end())
  137.                 {
  138.                     int pos = 0;
  139.                     for (int j = it->P; pos<len+1; j++)
  140.                         str[j] = rules[i].R[pos++];
  141.                     isOK = true;
  142.                     break;
  143.                 }
  144.             }
  145.         }
  146.     }
  147.     while (isOK);
  148.  
  149.     cout<<stepAmount - 1<<' '<<perLen;
  150. }
  151. int main()
  152. {
  153.     freopen("input.txt","r",stdin);
  154.     freopen("output.txt","w",stdout);
  155.  
  156.     input();
  157.     solve();
  158.     return 0;
  159. }


Editing is locked.