v 0. Pasted by slipstak2 as cpp at 2011-01-11 15:30:59 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. }
  160.  
  161. // Меньшиков. Тренировка 14.
  162. // 14B. Д-44 [d44]
  163. // ibelyaev: 10Jan2011
  164.  
  165. #include <iostream>
  166. #include <cstdio>
  167. #include <cmath>
  168.  
  169. using namespace std;
  170. const double k = 0.0008137;
  171. const double V0 = 800;
  172. const double m = 9.6;
  173. const double g = 9.8;
  174. const double pi = 2*acos(0.0);
  175.  
  176.  
  177. double alpha;
  178. void input()
  179. {
  180.     cin>>alpha;
  181.     alpha = pi * alpha / 180.0;
  182. }
  183. void solve()
  184. {
  185.     double dt = 0.0001;
  186.     double Vxt = V0 * cos(alpha);
  187.     double Vyt = V0 * sin(alpha);
  188.     double Xt = Vxt * dt;
  189.     double Yt = Vyt * dt;
  190.     double Vt,Xnext,Ynext,Axt,Ayt,Frxt,Fryt,Frt;
  191.     do
  192.     {
  193.         Vt = sqrt(Vxt*Vxt + Vyt*Vyt);
  194.         Xnext = Xt + Vxt*dt;
  195.         Ynext = Yt + Vyt*dt;
  196.  
  197.         Frt = k * Vt * Vt;
  198.         Frxt = - Frt * Vxt / Vt;
  199.         Fryt = - Frt * Vyt / Vt;
  200.  
  201.         Axt = Frxt / m;
  202.         Ayt = Fryt / m - g;
  203.  
  204.         Vxt = Vxt + Axt * dt;
  205.         Vyt = Vyt + Ayt * dt;
  206.  
  207.         Xt = Xnext;
  208.         Yt = Ynext;
  209.     }while (Yt>=0);
  210.  
  211.     printf("%0.0f",Xt);
  212. }
  213. int main()
  214. {
  215.     freopen("input.txt","r",stdin);
  216.     freopen("output.txt","w",stdout);
  217.  
  218.     input();
  219.     solve();
  220.     return 0;
  221. }
  222.  
  223. // Меньшиков. Тренировка 14.
  224. // 14C. Упаковка символов [folding]
  225. // ibelyaev: 10Jan2011
  226.  
  227. #include <iostream>
  228. #include <cstdio>
  229. #include <string>
  230. #include <vector>
  231.  
  232. using namespace std;
  233. const int MAX_LEN = 1e9;
  234. int n;
  235. string str;
  236. vector<vector<int> > mas;
  237. void input()
  238. {
  239.     cin>>str;
  240.     n = str.size();
  241.     mas = vector<vector<int> >(n,vector<int>(n,0));
  242. }
  243. int count(int num)
  244. {
  245.     int amount = 0;
  246.     while (num) {
  247.         num/=10;
  248.         amount++;
  249.     }
  250.     return amount;
  251. }
  252. string getAnswer(int i, int j) {
  253.  
  254.     if (i == j)
  255.         return string(&str[i],1);
  256.     int res = MAX_LEN;
  257.     int LEN = j - i + 1;
  258.     for (int step = 1; step <= LEN / 2; step++)
  259.     {
  260.         if (LEN % step != 0) continue;
  261.         bool isOK = true;
  262.         for (int cur = 0; cur<step; cur++) {
  263.             for (int pos = i + cur; pos<=j; pos+=step) {
  264.                 if (str[i+cur] != str[pos]) {
  265.                     isOK = false;
  266.                     break;
  267.                 }
  268.             }
  269.         }
  270.         if (isOK) {
  271.             int curLen = count((j-i+1) / step) + 2 + mas[i][i+step-1];
  272.             if (curLen == mas[i][j]) {
  273.  
  274.                 char buf[10];
  275.                 sprintf(buf,"%d",(j-i+1) / step);
  276.                 return string(buf) + "(" + getAnswer(i,i+step-1) + ")";
  277.             }
  278.  
  279.         }
  280.     }
  281.  
  282.     for (int m = i; m<j; m++)
  283.         if (mas[i][m] + mas[m+1][j] == mas[i][j])
  284.             return getAnswer(i,m) + getAnswer(m+1,j);
  285. }
  286. void solve()
  287. {
  288.     for (int len = 0; len < n; len++) {
  289.         for (int i=0;i<n; i++) {
  290.             int j = i + len;
  291.             if (j >= n) break;
  292.  
  293.             if (len == 0) mas[i][j] = 1;
  294.  
  295.             else {
  296.                 int res = MAX_LEN;
  297.                 int LEN = j - i + 1;
  298.                 for (int step = 1; step <= LEN / 2; step++)
  299.                 {
  300.                     if (LEN % step != 0) continue;
  301.                     bool isOK = true;
  302.                     for (int cur = 0; cur<step; cur++) {
  303.                         for (int pos = i + cur; pos<=j; pos+=step) {
  304.                             if (str[i+cur] != str[pos]) {
  305.                                 isOK = false;
  306.                                 break;
  307.                             }
  308.                         }
  309.                     }
  310.                     if (isOK) {
  311.                         int curLen = count( LEN / step) + 2 + mas[i][i+step-1];
  312.                         res = min(res,curLen);
  313.                     }
  314.                 }
  315.  
  316.                 for (int m = i; m<j; m++)
  317.                     res = min(res,mas[i][m] + mas[m+1][j]);
  318.  
  319.                 mas[i][j] = res;
  320.             }
  321.         }
  322.     }
  323.  
  324.     string ans = getAnswer(0,n-1);
  325.     cout<<ans;
  326. }
  327. int main()
  328. {
  329.     freopen("input.txt","r",stdin);
  330.     freopen("output.txt","w",stdout);
  331.  
  332.     input();
  333.     solve();
  334.     return 0;
  335. }
  336.  
  337. // Меньшиков. Тренировка 14.
  338. // 14D. Пирамиды [pyramids]
  339. // ibelyaev: 10Jan2011
  340.  
  341. #include <iostream>
  342. #include <cstdio>
  343. #include <cmath>
  344.  
  345. using namespace std;
  346.  
  347. double AB,AC,AD,BC,BD,CD;
  348. void input()
  349. {
  350.     cin>>AB>>AC>>AD>>BC>>BD>>CD;
  351. }
  352. void solve()
  353. {
  354.     double Xb = AB;
  355.     double Xc = (AC*AC - BC*BC + AB*AB) / (2*AB);
  356.     double Yc = sqrt(AC*AC - Xc*Xc);
  357.  
  358.     double Xd = (AD*AD + AB*AB - BD*BD) / (2*AB);
  359.     double Yd = (AD*AD - CD*CD - 2*Xc*Xd + Xc*Xc + Yc*Yc) / (2*Yc);
  360.     double Zd = sqrt(AD*AD - Xd*Xd - Yd*Yd);
  361.  
  362.     double S = Xb*Yc*Zd / 6.0;
  363.     printf("%0.4f",S);
  364.    
  365. }
  366. int main()
  367. {
  368.     freopen("input.txt","r",stdin);
  369.     freopen("output.txt","w",stdout);
  370.  
  371.     input();
  372.     solve();
  373.     return 0;
  374. }
  375.  
  376. // Меньшиков. Тренировка 14.
  377. // 14E. Поле для крикета [cricket]
  378. // O(N*N) для перебора угла +
  379. // O(N*logN) бинарный поиск длины + проверка корректности длины
  380. // ibelyaev: 10Jan2011
  381.  
  382. #include <iostream>
  383. #include <cstdio>
  384. #include <utility>
  385. #include <vector>
  386. #include <set>
  387.  
  388. using namespace std;
  389. #define X first
  390. #define Y second
  391. int n,W,H;
  392. vector<pair<int,int> > mas;
  393. set<int> XX,YY;
  394. void input()
  395. {
  396.     cin>>n>>W>>H;
  397.     mas.resize(n);
  398.     int x,y;
  399.     for (int i=0;i<n;i++) {
  400.         cin>>x>>y;
  401.         mas[i] = make_pair(x,y);
  402.         XX.insert(x); YY.insert(y);
  403.     }
  404.     mas.push_back(make_pair(0,0));
  405.     mas.push_back(make_pair(W,H));
  406.     n+=2;
  407.     XX.insert(0); XX.insert(W);
  408.     YY.insert(0); YY.insert(H);
  409. }
  410. void solve()
  411. {
  412.     int Xres, Yres, resLen = -1e9;
  413.     int curX, curY, curLen;
  414.     int xx,yy;
  415.     for (set<int>::iterator x = XX.begin(); x != XX.end(); x++) {
  416.         for (set<int>::iterator y = YY.begin(); y != YY.end(); y++) {
  417.            
  418.             int l = 0, r = 1e4 + 10;
  419.             while (l<=r) {
  420.                 int m = (l+r)>>1;
  421.                 int Xm = *x + m;
  422.                 int Ym = *y + m;
  423.                 if (Xm > W || Ym > H) {
  424.                     r = m - 1;
  425.                     continue;
  426.                 }
  427.                 bool isOK = false;
  428.                 for (int i=0;i<n;i++) {
  429.                     if (mas[i].X > *x && mas[i].Y > *y) {
  430.                         if (mas[i].X < Xm && mas[i].Y < Ym) {
  431.                             isOK = false;
  432.                             break;
  433.                         }
  434.                         else {
  435.                             isOK = true;
  436.                             xx = *x;
  437.                             yy = *y;
  438.                         }
  439.                     }
  440.                 }
  441.                 if (isOK){
  442.                     l = m + 1;
  443.                     curLen = m;
  444.                     curX = xx;
  445.                     curY = yy;
  446.                 }
  447.                 else
  448.                     r = m-1;
  449.             }
  450.             if (curLen > resLen) {
  451.                 resLen = curLen;
  452.                 Xres = curX;
  453.                 Yres = curY;
  454.             }
  455.         }
  456.     }
  457.     cout<<Xres<<' '<<Yres<<' '<<resLen;
  458. }
  459. int main()
  460. {
  461.     freopen("input.txt","r",stdin);
  462.     freopen("output.txt","w",stdout);
  463.  
  464.     input();
  465.     solve();
  466.     return 0;
  467. }
  468.  
  469. // Меньшиков. Тренировка 14.
  470. // 14E. Поле для крикета [cricket]
  471. // O(N*N) для перебора угла +
  472. // O(N)  нахождение длины
  473. // ibelyaev: 11Jan2011
  474.  
  475. #include <iostream>
  476. #include <cstdio>
  477. #include <vector>
  478. #include <set>
  479. #include <utility>
  480.  
  481. using namespace std;
  482. typedef vector<pair<int,int> > POINTS;
  483. #define mp make_pair
  484. #define X(i) mas[i].first
  485. #define Y(i) mas[i].second
  486. int n,W,H;
  487. POINTS mas;
  488.  
  489. void input()
  490. {
  491.     cin>>n>>W>>H;
  492.     int x,y;
  493.     for (int i=0;i<n;i++) {
  494.         cin>>x>>y;
  495.         mas.push_back(mp(x,y));
  496.     }
  497.     mas.push_back(mp(0,0));
  498.     n = mas.size();
  499. }
  500. void solve()
  501. {
  502.     int resX = 0, resY = 0, resSide = 1;
  503.     int curX, curY, curSide;
  504.     for (int i = 0; i<n; i++) {
  505.         for (int j = 0; j<n; j++) {
  506.             curX = X(i);
  507.             curY = Y(j);
  508.             curSide = min(W-curX, H-curY);
  509.             for (int k=0; k<n; k++) {
  510.                 if (X(k) > curX && Y(k) > curY) {
  511.                     if (max(X(k) - curX,Y(k) - curY) < curSide)
  512.                         curSide = max(X(k) - curX,Y(k) - curY);
  513.                 }
  514.             }
  515.             if (resSide < curSide) {
  516.                 resSide = curSide;
  517.                 resX = curX;
  518.                 resY = curY;
  519.             }
  520.         }
  521.  
  522.     }
  523.     cout<<resX<<' '<<resY<<' '<<resSide;
  524. }
  525. int main()
  526. {
  527.     freopen("input.txt","r",stdin);
  528.     freopen("output.txt","w",stdout);
  529.  
  530.     input();
  531.     solve();
  532.     return 0;
  533. }
  534.  
  535. // Меньшиков. Тренировка 14.
  536. // 14F. Электронная таблица [sprsheet]
  537. // ibelyaev: 11Jan2011
  538.  
  539. #include <iostream>
  540. #include <cstdio>
  541. #include <string>
  542. #include <vector>
  543. #include <stack>
  544. #include <set>
  545. #include <string.h>
  546.  
  547. using namespace std;
  548. const int size = 26 * 9;
  549. const int MAX_SIZE = 255 + 10;
  550. enum TYPE {WHITE, GRAY, BLACK};
  551. int n;
  552. vector<string> exp(size);
  553. vector<int> value(size);
  554. vector<set<int> > adj(size);
  555. vector<TYPE> used(size, WHITE);
  556.  
  557. stack<char> opers;
  558. stack<int>  numbers;
  559. void trim(string &str)
  560. {
  561.     while (str[0] == ' ')
  562.         str.erase(0,1);
  563.     while (str[str.size()-1]==' ')
  564.         str.erase(str.size()-1,1);
  565. }
  566. int code(const char *pos) {
  567.     return (*pos - 'A') * 9 + *(pos+1) - '1';
  568. }
  569. int code(const string &s)
  570. {
  571.     return code(s.c_str());
  572. }
  573.  
  574. bool isLetter(char c) {
  575.     return 'A' <= c && c<= 'Z';
  576. }
  577. bool isDigit(char c) {
  578.     return '0'<= c && c <= '9';
  579. }
  580. void fillAdj(int index, string s)
  581. {
  582.     for (int i = 0; i<s.size();i++) {
  583.         if (isLetter(s[i])) {
  584.             adj[index].insert(code(s.substr(i,2)));
  585.         }
  586.     }
  587. }
  588. void input()
  589. {
  590.     scanf("%d\n",&n);
  591.     string str,f,s;
  592.     int pos;
  593.     for (int i=0;i<n;i++)
  594.     {
  595.         getline(cin,str);
  596.         pos = str.find('=');
  597.         f = str.substr(0,pos);
  598.         s = str.substr(pos+1,str.size() - (pos+1));
  599.         trim(f);
  600.         trim(s);   
  601.         exp[code(f)] = s;
  602.         fillAdj(code(f),s);
  603.     }
  604. }
  605. void dfs(int pos, vector<int> &G, bool &isCircle) {
  606.    
  607.     used[pos] = GRAY;
  608.     for (set<int>::iterator it=adj[pos].begin(); it != adj[pos].end(); it++) {
  609.        
  610.         if (isCircle) return;
  611.  
  612.         if (used[*it] == GRAY) {
  613.             isCircle = true;
  614.             break;
  615.         }
  616.         else if (used[*it] == WHITE){
  617.             dfs(*it,G,isCircle);
  618.         }
  619.     }
  620.     G.push_back(pos);
  621.     used[pos] = BLACK;
  622. }
  623. bool topological_sort(vector<int> &G) {
  624.  
  625.     bool isCircle = false;
  626.     dfs(0,G,isCircle);
  627.     return isCircle;
  628. }
  629. inline bool isEnd(const char * pos) {
  630.     return *pos == 0;
  631. }
  632. void SkipSep(char* &pos) {
  633.     while (!isEnd(pos) && *pos == ' ')
  634.         pos++;
  635. }
  636. bool isOper(const char* pos) {
  637.     return !isEnd(pos) &&
  638.      (  *pos == '+' ||
  639.         *pos == '-' ||
  640.         *pos == '*' ||
  641.         *pos == '/' );
  642. }
  643. int prior (const char pos) {
  644.     if (pos == '+' || pos == '-')
  645.         return 1;
  646.     else
  647.         return 2;
  648. }
  649. void ReadCell(char* &pos, int &number) {
  650.     int cell = code(pos);
  651.     pos+=2;
  652.     number = value[cell];
  653. }
  654. void ReadNumber (char* &pos, int &number) {
  655.     number = 0;
  656.     while (!isEnd(pos) && isDigit(*pos)) {
  657.         number = number * 10 + (*pos - '0');
  658.         pos++;
  659.     }
  660. }
  661. void calcExp(char* &pos, int &res);
  662. void ReadNextValue(char* &pos, int &number) {
  663.  
  664.     if (*pos == '(') {
  665.         pos++;
  666.         calcExp(pos,number);
  667.         pos++;
  668.     }
  669.     else {
  670.  
  671.         if (isLetter(*pos))
  672.             ReadCell(pos, number);
  673.         if (isDigit(*pos))
  674.             ReadNumber(pos, number);
  675.     }
  676. }
  677. int calc(int f, int s, char oper) {
  678.     switch(oper) {
  679.         case '+': return f + s;
  680.         case '-': return f - s;
  681.         case '*': return f * s;
  682.         case '/': if (s == 0)
  683.                       return 0;
  684.                   else
  685.                       return f/s;
  686.     }
  687. }
  688. void calcExp(char* &pos, int &res) {
  689.  
  690.     stack<int> locNumbers;
  691.     stack<char> locOper;
  692.     do
  693.     {
  694.         SkipSep(pos);
  695.         if (isOper(pos)) {
  696.             char curOper = *pos++;
  697.            
  698.             while (!locOper.empty() && prior(locOper.top()) > prior(curOper)) {
  699.                
  700.                 int s = locNumbers.top();               locNumbers.pop();
  701.                 int f = locNumbers.top();               locNumbers.pop();
  702.                 int locRes = calc(f,s,locOper.top());   locOper.pop();
  703.                 locNumbers.push(locRes);
  704.             }
  705.             locOper.push(curOper);
  706.         }
  707.         else {
  708.             int number = 0;
  709.             ReadNextValue(pos, number);
  710.             locNumbers.push(number);
  711.         }
  712.         SkipSep(pos);
  713.     } while (!isEnd(pos) && *pos != ')');
  714.  
  715.     while (!locOper.empty()) {
  716.         int s = locNumbers.top(); locNumbers.pop();
  717.         int f = locNumbers.top(); locNumbers.pop();
  718.         int locRes = calc(f,s,locOper.top());
  719.         locOper.pop();
  720.         locNumbers.push(locRes);
  721.     }
  722.     res = locNumbers.top();
  723. }
  724. void solve()
  725. {
  726.     vector<int> G;
  727.     if (topological_sort(G)) {
  728.         cout<<(int)1e6;
  729.     }
  730.     else {
  731.         if (G.empty()) G.push_back(0);
  732.  
  733.         for (int i=0;i<G.size();i++) {
  734.             char *buf = new char[MAX_SIZE];
  735.             strcpy(buf,exp[G[i]].c_str());
  736.             calcExp(buf,value[G[i]]);
  737.         }
  738.         cout<<value[0];
  739.     }
  740. }
  741. int main()
  742. {
  743.     freopen("input.txt","r",stdin);
  744.     freopen("output.txt","w",stdout);
  745.  
  746.     input();
  747.     solve();
  748.     return 0;
  749. }


Editing is locked.