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

Paste will expire never.

  1. // Меньшиков. Тренировка 13.
  2. // 13A. Двойная решетка [dlattice]
  3. // ibelyaev: 06Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <set>
  10.  
  11. using namespace std;
  12.  
  13. int x1,y1,x2,y2,dx,dy;
  14. void input()
  15. {
  16.     cin>>x1>>y1>>x2>>y2>>dx>>dy;
  17. }
  18. int gcd(int a, int b)
  19. {
  20.     return b ? gcd(b, a%b) : a;
  21. }
  22. int lcm(int a, int b)
  23. {
  24.     return  (a*b)/gcd(a,b);
  25. }
  26. void output(set<int> &S)
  27. {
  28.     printf("%d\n",S.size());
  29.     for (set<int>::iterator it = S.begin(); it != S.end(); it++)
  30.         printf("%d\n",*it);
  31. }
  32. void solve()
  33. {
  34.     int maxX = dx + lcm(x1, x2);
  35.     int maxY = dy + lcm(y1, y2);
  36.     vector<int> X, Y;
  37.     set<int> S;
  38.  
  39.     for (int x = 0; x<=maxX; x+=x1)
  40.         X.push_back(x);
  41.     for (int x = dx; x<=maxX; x+= x2)
  42.         X.push_back(x);
  43.    
  44.  
  45.     for (int y = 0; y<=maxY; y+=y1)
  46.         Y.push_back(y);
  47.     for (int y = dy; y<=maxY; y+=y2)
  48.         Y.push_back(y);
  49.  
  50.     sort(X.begin(), X.end());
  51.     sort(Y.begin(), Y.end());
  52.     int dx, dy;
  53.     for (int i = 0; i < X.size()-1; i++) {
  54.         for (int j = 0; j < Y.size()- 1; j++) {
  55.             dx = X[i+1] - X[i];
  56.             dy = Y[j+1] - Y[j];
  57.             S.insert(dx*dy);
  58.         }
  59.     }
  60.     S.erase(0);
  61.     output(S);
  62. }
  63. int main()
  64. {
  65.     freopen("input.txt","r",stdin);
  66.     freopen("output.txt","w",stdout);
  67.  
  68.     input();
  69.     solve();
  70.     return 0;
  71. }
  72.  
  73. // Меньшиков. Тренировка 13.
  74. // 13B. Последовательность Фибоначчи [fiboseq]
  75. // Бинарный поиск
  76. // ibelyaev: 06Jan2011
  77.  
  78. #include <iostream>
  79. #include <cstdio>
  80. #include <stdlib.h>
  81.  
  82. using namespace std;
  83.  
  84. int n,i,j;
  85. long long Fi,Fj;
  86. void input()
  87. {
  88.     cin>>i>>Fi>>j>>Fj>>n;
  89. }
  90. //                       F[i]         F[i+1]
  91. long long Fib(long long prev, long long cur, int n)
  92. {
  93.     // forward
  94.     if (n > i) {
  95.         for (int pos = i + 2; pos <= n; pos++) {
  96.             prev += cur;
  97.             swap(cur, prev);
  98.         }
  99.         return cur;
  100.     }
  101.     // back
  102.     else {
  103.         for (int pos = i - 1; pos>=n; pos--) {
  104.             cur -= prev;
  105.             swap(cur, prev);
  106.         }
  107.         return prev;
  108.     }
  109. }
  110. void solve()
  111. {
  112.     if (n == i) { cout<<Fi; return; }
  113.     if (n == j) { cout<<Fj; return; }
  114.  
  115.     if (i > j) {
  116.         swap(i,j);
  117.         swap(Fi,Fj);
  118.     }
  119.  
  120.     if (j == i + 1)
  121.     {
  122.         cout<<Fib(Fi,Fj,n);
  123.         return;
  124.     }
  125.  
  126.     long long l = -2e9 - 10, r = 2e9 + 10;
  127.     while (l<=r)
  128.     {
  129.         long long FiNxt = (l+r)/2;
  130.         long long FjPos = Fib(Fi,FiNxt, j);
  131.         if (FjPos < Fj)
  132.             l = FiNxt + 1;
  133.         else if (FjPos > Fj)
  134.             r = FiNxt - 1;
  135.         else {
  136.             cout<<Fib(Fi,FiNxt,n);
  137.             return;
  138.         }
  139.     }
  140. }
  141. int main()
  142. {
  143.     freopen("input.txt","r",stdin);
  144.     freopen("output.txt","w",stdout);
  145.  
  146.     input();
  147.     solve();
  148.     return 0;
  149. }
  150.  
  151. // Меньшиков. Тренировка 13.
  152. // 13B. Последовательность Фибоначчи [fiboseq]
  153. // По формуле + выкладки
  154. // ibelyaev: 06Jan2011
  155.  
  156. #include <iostream>
  157. #include <cstdio>
  158. #include <stdlib.h>
  159.  
  160. using namespace std;
  161.  
  162. int n,i,j;
  163. long long Fi,Fj;
  164. void input()
  165. {
  166.     cin>>i>>Fi>>j>>Fj>>n;
  167. }
  168. long long Fib(int n)
  169. {
  170.     long long prev = 1, cur = 1;
  171.     for (int i = 2; i<=n; i++)
  172.     {
  173.         prev += cur;
  174.         swap(cur, prev);
  175.     }
  176.     return cur;
  177. }
  178. //                       F[i]         F[i+1]
  179. long long Fib(long long prev, long long cur, int n)
  180. {
  181.     // forward
  182.     if (n > i) {
  183.         for (int pos = i + 2; pos <= n; pos++) {
  184.             prev += cur;
  185.             swap(cur, prev);
  186.         }
  187.         return cur;
  188.     }
  189.     // back
  190.     else {
  191.         for (int pos = i - 1; pos>=n; pos--) {
  192.             cur -= prev;
  193.             swap(cur, prev);
  194.         }
  195.         return prev;
  196.     }
  197. }
  198. void solve()
  199. {
  200.     if (n == i) { cout<<Fi; return; }
  201.     if (n == j) { cout<<Fj; return; }
  202.  
  203.     if (i > j) {
  204.         swap(i,j);
  205.         swap(Fi,Fj);
  206.     }
  207.  
  208.     // A(i)   = 1 * A(i) + 0 * A(i+1)
  209.     // A(i+1) = 0 * A(i) + 1 * A(i+1)
  210.     // A(i+2) = 1 * A(i) + 1 * A(i+1)
  211.     // A(i+3) = 1 * A(i) + 2 * A(i+1)
  212.     // A(i+4) = 2 * A(i) + 3 * A(i+1)
  213.     // A(i+5) = 3 * A(i) + 5 * A(i+1)
  214.     // A(i+6) = 5 * A(i) + 8 * A(i+1)
  215.  
  216.     // F(0) = 1
  217.     // F(1) = 1
  218.     // F(2) = 2
  219.     // F(3) = 3
  220.     // F(4) = 5
  221.     // F(5) = 8
  222.  
  223.     // A(i+x) = F(x-2) * A(i) + F(x-1) * A(i+1)
  224.     // i + x = j
  225.     // A(j) = F(j-i-2) * A(i) + F(j-i-1) * A(i+1);
  226.     // A(i+1) = [A(j) - F(j-i-2) * A(i)] / F(j-i-1);
  227.     // FiNxt = A(i+1);
  228.    
  229.     int k = j - i;
  230.     long long FiNxt;
  231.     if (k == 1)
  232.         FiNxt = Fj;
  233.     else
  234.         FiNxt =  (Fj - Fib(k-2) * Fi) / Fib(k-1);   
  235.     cout<<Fib(Fi, FiNxt, n);
  236. }
  237. int main()
  238. {
  239.     freopen("input.txt","r",stdin);
  240.     freopen("output.txt","w",stdout);
  241.  
  242.     input();
  243.     solve();
  244.     return 0;
  245. }
  246.  
  247. // Меньшиков. Тренировка 13.
  248. // 13С. Скобки(3) [bracket3]
  249. // ibelyaev: 06Jan2011
  250.  
  251. #include <iostream>
  252. #include <cstdio>
  253. #include <string>
  254. #include <vector>
  255.  
  256. using namespace std;
  257. const int MAX_VALUE = 1e9;
  258. int n;
  259. string str;
  260. vector<vector<int> > mas;
  261. void input()
  262. {
  263.     cin>>str;
  264.     n = str.size();
  265.     mas = vector<vector<int> >(n,vector<int>(n,0));
  266. }
  267. string open = "([";
  268. string clos = ")]";
  269. bool isPair(char f, char s)
  270. {
  271.     int posF = open.find(f);
  272.     int posS = clos.find(s);
  273.     return posF == posS && posF != -1;
  274. }
  275. string Pair(char one)
  276. {
  277.     int pos = open.find(one);
  278.     if (pos == -1)
  279.         pos = clos.find(one);
  280.    
  281.     return string(&open[pos],1) + string(&clos[pos],1);
  282. }
  283. string getAnswer(int l, int r)
  284. {
  285.     if (l > r) return "";
  286.     if (l == r)
  287.         return Pair(str[l]);
  288.     int border = (isPair(str[l],str[r]) ? mas[l+1][r-1] : MAX_VALUE);
  289.     if (border == mas[l][r])
  290.         return str[l] + getAnswer(l+1,r-1) + str[r];
  291.     for (int m = l; m < r; m++)
  292.     {
  293.         if (mas[l][m] + mas[m+1][r] == mas[l][r])
  294.             return getAnswer(l,m) + getAnswer(m+1,r);
  295.     }
  296. }
  297. void solve()
  298. {
  299.     for (int i=0;i<n;i++)
  300.         mas[i][i] = 1;
  301.     for (int len = 1; len < n; len++) {
  302.         for (int i=0;i<n;i++) {
  303.             int j = i + len;
  304.             if (j>=n) break;
  305.  
  306.             int curLen = MAX_VALUE;
  307.             if (isPair(str[i],str[j]))
  308.                 curLen = mas[i+1][j-1];
  309.             for (int m = i; m < j; m++)
  310.                 curLen = min(curLen, mas[i][m] + mas[m+1][j]);
  311.             mas[i][j] = curLen;
  312.         }
  313.     }
  314.  
  315.     string answer = "";
  316.     answer = getAnswer(0,n-1);
  317.     cout<<answer;
  318. }
  319. int main()
  320. {
  321.     freopen("input.txt","r",stdin);
  322.     freopen("output.txt","w",stdout);
  323.  
  324.     input();
  325.     solve();
  326.     return 0;
  327. }
  328.  
  329. // Меньшиков. Тренировка 13.
  330. // 13D. Центр тяжести [centgrav]
  331. // ibelyaev: 07Jan2011
  332.  
  333. #include <iostream>
  334. #include <cstdio>
  335. #include <vector>
  336.  
  337. using namespace std;
  338.  
  339. const double eps = 1e-9;
  340. double _fabs(double a)
  341. {
  342.     if (a<0) return -a;
  343.     return a;
  344. }
  345. bool Equal(double a, double b)
  346. {
  347.     return _fabs(a-b) <= eps;
  348. }
  349. struct point
  350. {
  351.     double x, y;
  352.     point(){}
  353.     point(double X, double Y)
  354.     {
  355.         x = X;
  356.         y = Y;
  357.     }
  358.     void input()
  359.     {
  360.         cin>>x>>y;
  361.     }
  362.     void output()
  363.     {
  364.         if (Equal(x,0)) x = 0;
  365.         if (Equal(y,0)) y = 0;
  366.         printf("%0.2f %0.2f",x,y);
  367.     }
  368. };
  369. int n;
  370. vector<point> mas;
  371. void input()
  372. {
  373.     cin>>n;
  374.     mas.resize(n);
  375.     for (int i=0;i<n;i++)
  376.         mas[i].input();
  377. }
  378. double findS(const point &a, const point &b, const point &c)
  379. {
  380.     return 0.5*(a.x*b.y + b.x*c.y + c.x *a.y - a.y*b.x - b.y*c.x - c.y*a.x);
  381. }
  382. void solve()
  383. {
  384.    
  385.     double S = 0;
  386.     double midX = 0;
  387.     double midY = 0;
  388.     for (int i=1;i<n-1;i++)
  389.     {
  390.         double curS = findS(mas[0], mas[i], mas[i+1]);
  391.         S += curS;
  392.         midX += curS * (mas[0].x + mas[i].x + mas[i+1].x) / 3;
  393.         midY += curS * (mas[0].y + mas[i].y + mas[i+1].y) / 3;
  394.     }
  395.     point center(midX/S, midY/S);
  396.     center.output();
  397. }
  398. int main()
  399. {
  400.     freopen("input.txt","r",stdin);
  401.     freopen("output.txt","w",stdout);
  402.  
  403.     input();
  404.     solve();
  405.     return 0;
  406. }
  407.  
  408. // Меньшиков. Тренировка 13.
  409. // 13E. Сумма произведений [prodsum]
  410. // O(N) по авторскому разбору
  411. // ibelyaev: 07Jan2011
  412.  
  413. #include <iostream>
  414. #include <cstdio>
  415. #include <cmath>
  416.  
  417. using namespace std;
  418.  
  419. int n,s;
  420. void input()
  421. {
  422.     cin>>n>>s;
  423. }
  424. int amount;
  425. double eps = 1e-9;
  426. void solve()
  427. {
  428.     // z = 0 amount
  429.     // p = +1 amount
  430.     // m = -1 amount
  431.     int p;
  432.     for (int z = 0; z<=n; z++)
  433.     {
  434.         int k = n - z;
  435.         int a = 4;
  436.         int b = -4*k;
  437.         int c = k*k - k - 2*s;
  438.  
  439.         int d = b*b - 4*a*c;
  440.         if (d<0) continue;
  441.  
  442.         int sqrtD = sqrt((double)d) + eps;
  443.        
  444.         if (sqrtD * sqrtD == d)
  445.         {
  446.             if ((-b + sqrtD) % (2*a) == 0){
  447.                 p = (- b + sqrtD) / (2*a);
  448.                 if (0<=p && z+p <= n){
  449.                     amount++;
  450.                     continue;
  451.                 }
  452.             }
  453.             if ((-b - sqrtD) % (2*a) == 0){
  454.                 p = (- b - sqrtD) / (2*a);
  455.                 if (0<=p && z+p <= n){
  456.                     amount++;
  457.                     continue;
  458.                 }               
  459.             }           
  460.         }
  461.     }
  462.     cout<<amount;
  463. }
  464. int main()
  465. {
  466.     freopen("input.txt","r",stdin);
  467.     freopen("output.txt","w",stdout);
  468.  
  469.     input();
  470.     solve();
  471.     return 0;
  472. }
  473.  
  474. // Меньшиков. Тренировка 13.
  475. // 13E. Сумма произведений [prodsum]
  476. // O(N*N)
  477. // ibelyaev: 07Jan2011
  478.  
  479. #include <iostream>
  480. #include <cstdio>
  481.  
  482. using namespace std;
  483.  
  484. int n,s;
  485. void input()
  486. {
  487.     cin>>n>>s;
  488. }
  489. int F(int n)
  490. {
  491.     return n*(n-1)>>1;
  492. }
  493. void solve()
  494. {
  495.     int amount = 0;
  496.     for (int nz = 0; nz<=n; nz++)
  497.     {
  498.         for (int minus = 0; minus<=nz; minus++)
  499.         {
  500.             int plus = nz - minus;
  501.             if (F(minus) + F(plus) - plus*minus == s)
  502.             {
  503.                 amount++;
  504.                 // break нужен для того, чтобы не считать
  505.                 // одинаковые комбинации, содержащие
  506.                 // одинаковое количество нулей
  507.                 break;
  508.             }
  509.         }
  510.     }
  511.     cout<<amount;
  512. }
  513. int main()
  514. {
  515.     freopen("input.txt","r",stdin);
  516.     freopen("output.txt","w",stdout);
  517.  
  518.     input();
  519.     solve();
  520.     return 0;
  521. }
  522.  
  523. // Меньшиков. Тренировка 13.
  524. // 13F. Статическая сложность [icomplex]
  525. // ibelyaev: 07Jan2011
  526.  
  527. #include <iostream>
  528. #include <cstdio>
  529. #include <vector>
  530. #include <string.h>
  531.  
  532. using namespace std;
  533. const int MAX_SIZE = 2048 + 10;
  534. const int MAX_STEPS = 12;
  535.  
  536. int n;
  537. typedef vector<int> algoComplex;
  538.  
  539. void ReadOperatorsList(char* &pos, algoComplex &totalAC);
  540. void output(algoComplex &ac, int num)
  541. {
  542.     printf("Program #%d\n",num);
  543.     printf("Runtime = ");
  544.     bool isFirst = true;
  545.     bool isEmpty = true;
  546.     for (int i = MAX_STEPS-1; i>=0; i--) {
  547.         int mul = ac[i];
  548.         if (mul){
  549.             isEmpty = false;
  550.             if (isFirst)
  551.                 isFirst = false;
  552.             else
  553.                 cout<<"+";
  554.            
  555.             if (mul != 1 || (mul == 1 && i ==0))
  556.                 cout<<mul;
  557.             if (i != 0){
  558.                 if (mul != 1) cout<<"*";
  559.                 cout<<"n";
  560.                 if (i!=1)
  561.                     cout<<"^"<<i;
  562.             }
  563.         }
  564.     }
  565.     if (isEmpty) cout<<0;
  566.     printf("\n\n");
  567. }
  568.  
  569. inline bool _isEnd(const char* pos)
  570. {
  571.     return *pos == 0;
  572. }
  573. inline void _SkipSeps(char* &pos)
  574. {
  575.     if (_isEnd(pos)) return;
  576.     while (!_isEnd(pos) && *pos == ' ')
  577.         pos++;
  578. }
  579. inline bool _isLoopBegin(const char* pos)
  580. {
  581.     if (_isEnd(pos)) return false;
  582.     return *pos == 'L';
  583. }
  584. inline bool _isOpBegin(const char* pos)
  585. {
  586.     if (_isEnd(pos)) return false;
  587.     return *pos == 'O';
  588. }
  589. inline bool _isOperatorBegin(const char* pos)
  590. {
  591.     return _isLoopBegin(pos) || _isOpBegin(pos);
  592. }
  593. inline bool _isDigit(const char pos)
  594. {
  595.     return '0' <= pos && pos <= '9';
  596. }
  597. inline void ReadLex(char* &pos, int len)
  598. {
  599.     for (int i=0;i<len;i++)
  600.         pos++;
  601. }
  602. void ReadNumber(char* &pos, int &number)
  603. {
  604.     if (*pos == 'n') {
  605.         pos++;
  606.         number = -1;
  607.         return;
  608.     }
  609.     while (_isDigit(*pos)) {
  610.         number = number*10 + *pos - '0';
  611.         pos++;
  612.     }
  613. }
  614. void ReadOperatorLoop(char* &pos, algoComplex &listAC)
  615. {
  616.     //<Оператор LOOP> ::= <Заголовок LOOP> <Список операторов> "END"
  617.     //<Заголовок LOOP> ::= "LOOP" <число> | "LOOP n"
  618.     ReadLex(pos, strlen("LOOP"));
  619.     int loopNumber = 0;
  620.  
  621.     _SkipSeps(pos);
  622.     ReadNumber(pos, loopNumber);
  623.     _SkipSeps(pos);
  624.  
  625.     algoComplex loopAC(MAX_STEPS);
  626.  
  627.  
  628.     bool isIns = false;
  629.     while (_isOperatorBegin(pos)) {
  630.  
  631.         isIns = true;
  632.         _SkipSeps(pos);
  633.         ReadOperatorsList(pos,loopAC);
  634.         _SkipSeps(pos);
  635.     }
  636.     if (isIns) {
  637.         if (loopNumber != -1) { // !=n
  638.             for (int i=0;i<MAX_STEPS;i++)
  639.                 loopAC[i] *= loopNumber;
  640.         }
  641.         else {
  642.             for (int i=MAX_STEPS-2;i>=0;i--)
  643.             {
  644.                 loopAC[i+1] = loopAC[i];
  645.                 loopAC[i] = 0;
  646.             }
  647.         }
  648.     }
  649.     else {
  650.         if (loopNumber != -1)  // !=n
  651.             loopAC[0] = loopNumber;
  652.         else
  653.             loopAC[1]++;
  654.     }
  655.  
  656.     for (int i=0;i<MAX_STEPS;i++)
  657.         listAC[i] += loopAC[i];
  658.  
  659.     _SkipSeps(pos);
  660.     ReadLex(pos,strlen("END"));
  661. }
  662.  
  663. void ReadOperatorOp(char* &pos, algoComplex & listAC)
  664. {
  665.     //<Оператор OP> ::= "OP" <число>
  666.     ReadLex(pos, strlen("OP"));
  667.     _SkipSeps(pos);
  668.     int opNumber = 0;
  669.     ReadNumber(pos, opNumber);
  670.     if (opNumber != -1) // !=n
  671.         listAC[0] += opNumber;
  672.     else
  673.         listAC[1]++;   
  674. }
  675.  
  676. void ReadOperator(char* &pos, algoComplex &curAC)
  677. {
  678.     //<Оператор> ::= <Оператор LOOP> | <Оператор OP>
  679.     if (_isLoopBegin(pos))
  680.         ReadOperatorLoop(pos, curAC);
  681.     else
  682.         ReadOperatorOp(pos, curAC);
  683. }
  684. void ReadOperatorsList(char* &pos, algoComplex &totalAC)
  685. {
  686.     //<Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
  687.     do
  688.     {
  689.         _SkipSeps(pos);
  690.         algoComplex curAC(MAX_STEPS);
  691.         ReadOperator(pos, curAC);
  692.         for (int i=0;i<MAX_STEPS;i++)
  693.             totalAC[i] += curAC[i];
  694.         _SkipSeps(pos);
  695.     }
  696.     while (_isOperatorBegin(pos));
  697. }
  698. void ReadProgram(char* &pos, algoComplex &ac)
  699. {
  700.     // <Программа> ::= "BEGIN" <Список операторов> "END"
  701.     _SkipSeps(pos);
  702.     ReadLex(pos, strlen("BEGIN"));
  703.  
  704.     ReadOperatorsList(pos, ac);
  705.  
  706.     _SkipSeps(pos);
  707.     ReadLex(pos, strlen("END"));   
  708. }
  709. void input()
  710. {
  711.     cin>>n;
  712.     string allPrograms = "";
  713.     char buf[MAX_SIZE];
  714.     while (cin.getline(buf,MAX_SIZE)) {
  715.         allPrograms += string(buf);
  716.         allPrograms += " ";
  717.     }
  718.  
  719.     algoComplex progAC(MAX_STEPS);
  720.     char *str  = new char[allPrograms.size()];
  721.     strcpy(str, allPrograms.c_str());
  722.     char *pos = str;
  723.     for (int i=0;i<n;i++)
  724.     {
  725.         progAC.assign(MAX_STEPS,0);
  726.         ReadProgram(pos, progAC);
  727.         output(progAC, i+1);
  728.     }   
  729. }
  730. int main()
  731. {
  732.     freopen("input.txt","r",stdin);
  733.     freopen("output.txt","w",stdout);
  734.  
  735.     input();
  736.     return 0;
  737. }


Editing is locked.