v 0. Pasted by slipstak2 as cpp at 2011-01-06 18:35:05 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 12.
  2. // 12A. Последовательность [seq2]
  3. // ibelyaev: 30Dec2010
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. const int size = 1010;
  12. long long n;
  13. vector<int> mas;
  14. vector<int> mem;
  15. vector<int> pos;
  16. void input()
  17. {
  18.     mas.resize(size);
  19.     mem.resize(size);
  20.     pos.resize(size);
  21.     cin>>mas[0]>>mas[1]>>mas[2];
  22.     mem[mas[2] + 10*mas[1] + 100*mas[0]] = 1;
  23.  
  24.     cin>>n;
  25.     n--;
  26. }
  27. void solve()
  28. {
  29.     int base = -1;
  30.     int len = -1;
  31.     for (int i=3;i<size;i++)
  32.     {
  33.         mas[i] = (mas[i-1] + mas[i-2] + mas[i-3])%10;
  34.         int value = mas[i-1] + 10*mas[i-2] + 100*mas[i-3];
  35.         if (mem[value] && i!=3)
  36.         {
  37.             base = pos[value];
  38.             len = i - 3 - base;
  39.             break;
  40.         }
  41.         mem[value] = 1;
  42.         pos[value] = i-3;
  43.     }
  44.     if (n < base + len)
  45.         cout<<mas[n];
  46.     else
  47.     {
  48.         int index = base + (n - base) % len;
  49.         cout<<mas[index];
  50.     }
  51. }
  52. int main()
  53. {
  54.     freopen("input.txt","r",stdin);
  55.     freopen("output.txt","w",stdout);
  56.  
  57.     input();
  58.     solve();
  59.     return 0;
  60. }
  61.  
  62. // Меньшиков. Тренировка 12.
  63. // 12B. Гирлянда [garland]
  64. // ibelyaev: 02Jan2011
  65.  
  66. #include <iostream>
  67. #include <cstdio>
  68. #include <vector>
  69.  
  70. using namespace std;
  71.  
  72. int n;
  73. const double eps = 1e-9;
  74. vector<double> h;
  75. void input()
  76. {
  77.     cin>>n;
  78.     h.resize(n);
  79.     cin>>h[0];
  80. }
  81. double _fabs(double a)
  82. {
  83.     if (a<0)
  84.         return -a;
  85.     return a;
  86. }
  87. double Equal(double a, double b)
  88. {
  89.     return _fabs(a-b) <= eps;
  90. }
  91. double Less(double a, double b)
  92. {
  93.     return a < b && !Equal(a,b);
  94. }
  95. double More(double a, double b)
  96. {
  97.     return a > b && !Equal(a,b);
  98. }
  99. void solve()
  100. {
  101.     double res = 1e9;
  102.     double l = 0, r = h[0];
  103.     while (Less(l,r))
  104.     {
  105.         h[1] = (l + r) / 2;
  106.         h.back() = 0;
  107.         bool isUp = false;
  108.         for (int i=2;i<n;i++)
  109.         {
  110.             h[i] = 2*h[i-1] - h[i-2] + 2;
  111.             if (!More(h[i],0))
  112.             {
  113.                 isUp = true;
  114.                 break;
  115.             }
  116.         }
  117.         if (More(h.back(),0.0))
  118.             res = min(res,h.back());
  119.         if (isUp)
  120.             l = h[1];
  121.         else
  122.             r = h[1];
  123.     }
  124.     printf("%0.2f",res);
  125. }
  126. int main()
  127. {
  128.     freopen("input.txt","r",stdin);
  129.     freopen("output.txt","w",stdout);
  130.  
  131.     input();
  132.     solve();
  133.     return 0;
  134. }
  135.  
  136. // Меньшиков. Тренировка 12.
  137. // 12C. Головоломка умножения [mpuzzle]
  138. // ibelyaev: 02Jan2011
  139.  
  140. #include <iostream>
  141. #include <vector>
  142. #include <cstdio>
  143.  
  144. using namespace std;
  145.  
  146. int n;
  147. vector<int> mas;
  148. vector<vector<int> > mem;
  149. void input()
  150. {
  151.     cin>>n;
  152.     mas.resize(n);
  153.     for (int i=0;i<n;i++)
  154.         cin>>mas[i];
  155.     mem = vector<vector<int> > (n,vector<int>(n));
  156. }
  157.  
  158. void solve()
  159. {
  160.     for (int len = 2; len < n; len++)
  161.     {
  162.         for (int i=0;i<n;i++)
  163.         {
  164.             int j = i + len;
  165.             if (j == n)
  166.                 break;
  167.             int res = 1e9;
  168.             for (int m = i+1; m<=j-1; m++)
  169.             {
  170.                 int cur = mem[i][m] + mas[i] * mas[m] * mas[j] + mem[m][j];
  171.                 res = min(res,cur);
  172.             }
  173.             mem[i][j] = res;
  174.         }
  175.     }
  176.     cout<<mem[0][n-1];
  177. }
  178. int main()
  179. {
  180.     freopen("input.txt","r",stdin);
  181.     freopen("output.txt","w",stdout);
  182.  
  183.     input();
  184.     solve();
  185.     return 0;
  186. }
  187.  
  188. // Меньшиков. Тренировка 12.
  189. // 12D. Точки в многоугольнике [polygonp]
  190. // ibelyaev: 03Jan2011
  191.  
  192. #include <iostream>
  193. #include <cstdio>
  194. #include <vector>
  195.  
  196. using namespace std;
  197. typedef long long INT;
  198. struct point
  199. {
  200.     INT x,y;
  201.     void input()
  202.     {
  203.         scanf("%lld %lld", &x, &y);
  204.     }
  205. };
  206. vector<point> mas;
  207. int n;
  208. void input()
  209. {
  210.     cin>>n;
  211.     mas.resize(n);
  212.     for (int i=0;i<n;i++)
  213.         mas[i].input();
  214. }
  215. inline INT _abs(INT a)
  216. {
  217.     if (a < 0)
  218.         return -a;
  219.     return a;
  220. }
  221. INT Square(point &a, point &b, point &c)
  222. {
  223.     return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
  224. }
  225. INT gcd (INT a, INT b)
  226. {
  227.     return b?gcd(b,a%b):a;
  228. }
  229. INT findBP()
  230. {
  231.     INT res = 0;
  232.     for (int i=0;i<n;i++)
  233.     {
  234.         INT dx = _abs(mas[i].x - mas[(i+1)%n].x);
  235.         INT dy = _abs(mas[i].y - mas[(i+1)%n].y);
  236.         res += gcd(dx,dy);
  237.     }
  238.     return res;
  239.  
  240. }
  241. void solve()
  242. {
  243.     INT S = 0;
  244.    
  245.     for (int i=1;i<n-1;i++)
  246.         S += Square(mas[0],mas[i],mas[i+1]);
  247.    
  248.     S = _abs(S) / 2;
  249.  
  250.     INT BorderPoints = findBP();
  251.    
  252.     INT InsidePoints  = S - BorderPoints/2 + 1;
  253.     cout<<InsidePoints;
  254. }
  255. int main()
  256. {
  257.     freopen("input.txt","r",stdin);
  258.     freopen("output.txt","w",stdout);
  259.  
  260.     input();
  261.     solve();
  262.     return 0;
  263. }
  264.  
  265. // Меньшиков. Тренировка 12.
  266. // 12E. Водопровод [wpipe]
  267. // Рекурсивный перебор с отсечением
  268. // ibelyaev: 05Jan2011
  269.  
  270. #include <iostream>
  271. #include <cstdio>
  272. #include <vector>
  273.  
  274. using namespace std;
  275. const int MAX_VALUE = 1e9;
  276. int k;
  277. vector<int> C,L;
  278. int x0, y0, x1, y1;
  279. int dx, dy;
  280. void input()
  281. {
  282.     cin>>x0>>y0>>x1>>y1>>k;
  283.     C.resize(k);
  284.     L.resize(k);
  285.     for (int i=0;i<k;i++)
  286.         cin>>L[i];
  287.     for (int j=0;j<k;j++)
  288.         cin>>C[j];
  289. }
  290. int _abs(int a)
  291. {
  292.     return (a<0) ? -a:a;
  293. }
  294. int minAmount = MAX_VALUE;
  295. int curAmount;
  296. bool isLast = false;
  297. void rec(int pos, int curLen, int totalLen)
  298. {
  299.     if ((totalLen - curLen) % L[pos] == 0)
  300.     {
  301.         int lastAmount = _abs(totalLen - curLen) / L[pos];
  302.         if (lastAmount <= C[pos])
  303.         {
  304.             if (isLast)
  305.                 minAmount = min(minAmount, curAmount + lastAmount);
  306.             else
  307.             {
  308.                 isLast = true;
  309.                 curAmount += lastAmount;
  310.                 C[pos] -= lastAmount;
  311.  
  312.                 rec(0,0,dy);
  313.  
  314.                 C[pos] += lastAmount;
  315.                 curAmount -= lastAmount;
  316.                 isLast = false;
  317.             }
  318.         }
  319.     }
  320.     if (pos == k-1)
  321.         return;
  322.     for (int x = -C[pos]; x <= C[pos]; x++)
  323.     {
  324.         C[pos]-= _abs(x);
  325.         curAmount += _abs(x);
  326.  
  327.         rec(pos+1, curLen + x * L[pos], totalLen);
  328.  
  329.         curAmount -= _abs(x);
  330.         C[pos] += _abs(x);
  331.     }
  332. }
  333.  
  334. void solve()
  335. {
  336.     dx = _abs(x0 - x1);
  337.     dy = _abs(y0 - y1);
  338.     // a*L[0] + b*L[1] + c*L[2] + d*L[3] = dx
  339.     rec(0,0,dx);
  340.     if (minAmount == MAX_VALUE)
  341.         cout<<-1;
  342.     else
  343.         cout<<minAmount;
  344. }
  345. int main()
  346. {
  347.     freopen("input.txt","r",stdin);
  348.     freopen("output.txt","w",stdout);
  349.  
  350.     input();
  351.     solve();
  352.     return 0;
  353. }
  354.  
  355. // Меньшиков. Тренировка 12.
  356. // 12E. Водопровод [wpipe]
  357. // Нерекурсивный перебор с использованием ДП
  358. // ibelyaev: 05Jan2011
  359.  
  360. #include <iostream>
  361. #include <cstdio>
  362. #include <vector>
  363. using namespace std;
  364.  
  365. const int MAX_LEN = 4*1000*10+2;
  366. const int MAX_VALUE = 1e9;
  367. const int OSN = 11;
  368.  
  369. int k;
  370. vector<int> C,L,step;
  371. int x1,y1,x2,y2;
  372. int minAmount = MAX_VALUE;
  373. void input()
  374. {
  375.     cin>>x1>>y1>>x2>>y2>>k;
  376.     C.resize(k);
  377.     L.resize(k);
  378.     step.resize(k);
  379.     for (int i=0;i<k;i++)
  380.         cin>>L[i];
  381.     for (int i=0;i<k;i++)
  382.         cin>>C[i];
  383. }
  384. int _abs(int a)
  385. {
  386.     return (a<0)?-a:a;
  387. }
  388. void UnPack(int num, int mas[])
  389. {
  390.     int pos = 0;
  391.     while (pos!=k)
  392.     {
  393.         mas[pos++] = num % OSN;
  394.         num /= OSN;
  395.     }   
  396. }
  397. void solve()
  398. {
  399.     step[0] = 1;
  400.     for (int i=1;i<k;i++)
  401.         step[i] = step[i-1] * OSN;
  402.  
  403.     vector<vector<int> > dp(MAX_LEN * 2);
  404.     dp[MAX_LEN].push_back(0);
  405.     for (int i=0;i<k;i++)
  406.     {
  407.         vector<vector<int> > ndp(dp);
  408.         for (int j=0;j<dp.size();j++)
  409.         {
  410.             for (int p=0; p<dp[j].size(); p++)
  411.             {
  412.                 for (int mul = 1; mul <= C[i]; mul++)
  413.                 {
  414.                     int nextState = dp[j][p] + mul * step[i];
  415.  
  416.                     int nextLen = j + mul * L[i];
  417.                     ndp[nextLen].push_back(nextState)
  418.  
  419.                     nextLen = j - mul*L[i];
  420.                     ndp[nextLen].push_back(nextState);
  421.                 }
  422.             }
  423.         }
  424.         dp.swap(ndp);
  425.     }
  426.     vector<int> x = dp[MAX_LEN + _abs(x1-x2)];
  427.     vector<int> y = dp[MAX_LEN + _abs(y1-y2)];
  428.  
  429.     int stateX[4], stateY[4];
  430.     for (int i=0;i<x.size();i++) {
  431.         UnPack(x[i],stateX);
  432.         for (int j=0;j<y.size();j++) {
  433.             UnPack(y[j],stateY);
  434.             bool isOK = true;
  435.             int curAmount = 0;
  436.             for (int p = 0; p < k; p++)
  437.             {
  438.                 curAmount += stateX[p] + stateY[p];
  439.                 if (stateX[p] + stateY[p] > C[p]) {
  440.                     isOK = false;
  441.                     break;
  442.                 }
  443.             }
  444.             if (isOK)
  445.                 minAmount = min(minAmount, curAmount);
  446.         }
  447.     }
  448.     if (minAmount == MAX_VALUE)
  449.         cout<< -1;
  450.     else
  451.         cout<<minAmount;
  452. }
  453. int main()
  454. {
  455.     freopen("input.txt","r",stdin);
  456.     freopen("output.txt","w",stdout);
  457.  
  458.     input();
  459.     solve();
  460.     return 0;
  461. }
  462.  
  463. // Меньшиков. Тренировка 12.
  464. // 12F. Химические реакции [chem]
  465. // ibelyaev: 06Jan2011
  466.  
  467. #include <iostream>
  468. #include <cstdio>
  469. #include <map>
  470. #include <string>
  471. #include <string.h>
  472. using namespace std;
  473.  
  474. int n;
  475. typedef map<string,int> form;
  476.  
  477. void ReadSequence(char* &pos, int number, form& formula);
  478.  
  479. inline bool _isEnd(const char* pos)
  480. {
  481.     return !*pos;
  482. }
  483. inline bool _isDigit(const char* pos)
  484. {
  485.     //<число> ::= "1".."9" {"0".."9"}
  486.     if (_isEnd(pos)) return false;
  487.     return '0' <= *pos && *pos <= '9';
  488. }
  489. inline bool _isUpLetter(const char* pos)
  490. {
  491.     //<прописная буква> ::= "A".."Z"
  492.     if (_isEnd(pos)) return false;
  493.     return 'A'<= *pos && *pos <='Z';
  494. }
  495. inline bool _isLwLetter(const char* pos)
  496. {
  497.     //<строчная буква> ::= "a".."z"
  498.     if (_isEnd(pos)) return false;
  499.     return 'a'<= *pos && *pos <='z';
  500. }
  501. inline bool _isChemElemBegin(const char* pos)
  502. {
  503.     if (_isEnd(pos)) return false;
  504.     return _isUpLetter(pos);
  505. }
  506. inline bool _isElemBegin(const char* pos)
  507. {
  508.     if (_isEnd(pos)) return false;
  509.     return _isChemElemBegin(pos) || *pos == '(';
  510. }
  511. inline bool _isSeqBegin(const char* pos)
  512. {
  513.     if (_isEnd(pos)) return false;
  514.     return _isElemBegin(pos);
  515. }
  516. inline bool _isPlusSeq(const char* pos)
  517. {
  518.     if (_isEnd(pos)) return false;
  519.     return *pos == '+';
  520. }
  521. void ReadNumber(char* &pos, int &number)
  522. {
  523.     number = number*10 + (*pos - '0');
  524.     pos++;
  525.     if (!_isEnd(pos) && _isDigit(pos))
  526.         ReadNumber(pos,number);
  527. }
  528. void ReadChemElement(char* &pos, string &chemElement)
  529. {
  530.     //<химический элемент> ::= <прописная буква> [<строчная буква>]
  531.     chemElement += *pos++;
  532.     if (_isLwLetter(pos))
  533.         chemElement += *pos++;
  534. }
  535. void ReadElement(char* &pos, int number, form &formula)
  536. {
  537.     //<элемент> ::= <химический элемент> | "(" <последовательность> ")"
  538.     if (*pos == '(')
  539.     {
  540.         pos++;
  541.         ReadSequence(pos, number, formula);
  542.         pos++;
  543.     }
  544.     else
  545.     {
  546.         string chemElement = "";
  547.         ReadChemElement(pos, chemElement);
  548.         formula[chemElement] += 1;
  549.     }
  550. }
  551. void ReadSequence(char* &pos, int number, form& totalFormula)
  552. {
  553.     //<последовательность> ::= <элемент> [<число>] {<элемент> [<число>]}
  554.     form localFormula;
  555.     while (_isElemBegin(pos)) {
  556.         localFormula.clear();
  557.         ReadElement(pos, number, localFormula);
  558.         int mul = 1;
  559.         if (_isDigit(pos)) {
  560.             mul = 0;
  561.             ReadNumber(pos, mul);
  562.         }
  563.  
  564.         form::iterator it = localFormula.begin();
  565.         for (it; it!= localFormula.end();it++)
  566.             totalFormula[it->first] += it->second * mul;
  567.     }
  568. }
  569. void ReadFormula(char* &pos, form &formula)
  570. {
  571.     //<формула> ::= [<число>] <последовательность> {"+" [<число>] <последовательность>}
  572.     if (_isEnd(pos)) return;
  573.     do
  574.     {
  575.         int number = 1;
  576.         if (_isDigit(pos)){
  577.             number = 0;
  578.             ReadNumber(pos,number);
  579.         }
  580.         form seqFormula;
  581.         if (_isSeqBegin(pos))
  582.             ReadSequence(pos,number,seqFormula);
  583.  
  584.         form::iterator it = seqFormula.begin();
  585.         for (it; it != seqFormula.end(); it++)
  586.             formula[it->first] += it->second * number;
  587.     }
  588.     while (_isPlusSeq(pos++));
  589. }
  590. void ReadFormulaString(string &strFormula, form &formula)
  591. {
  592.     cin>>strFormula;
  593.     char* buf = new char[strFormula.size()+1]; // +1 на нуль символ
  594.     strcpy(buf,strFormula.c_str());
  595.    
  596.     ReadFormula(buf,formula);
  597.  
  598.     buf -= strFormula.size() + 1;
  599.     delete [] buf;
  600. }
  601. void input()
  602. {
  603.     string initStrFormula = "";
  604.     form initFormula;
  605.     ReadFormulaString(initStrFormula, initFormula);
  606.    
  607.     cin>>n;
  608.     for (int i=0;i<n;i++)
  609.     {
  610.         form curFormula;
  611.         string curStrFormula;
  612.         ReadFormulaString(curStrFormula, curFormula);
  613.  
  614.         cout<<initStrFormula;
  615.         if (curFormula == initFormula)
  616.             cout<<"==";
  617.         else
  618.             cout<<"!=";
  619.         cout<<curStrFormula<<endl;
  620.     }
  621. }
  622. int main()
  623. {
  624.     freopen("input.txt","r",stdin);
  625.     freopen("output.txt","w",stdout);
  626.  
  627.     input();
  628.     return 0;
  629. }


Editing is locked.