v 0. Pasted by slipstak2 as cpp at 2010-11-23 23:10:35 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 6.
  2. // 6A. Закраска прямой [cover]
  3. // ibelyaev: 20Nov2010
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <algorithm>
  9.  
  10. using namespace std;
  11.  
  12. struct point
  13. {
  14.     int value;
  15.     bool isBegin;
  16.     point(){}
  17.     point(int _value, bool _isBegin)
  18.     {
  19.         value = _value;
  20.         isBegin = _isBegin;
  21.     }
  22. };
  23. int n;
  24. vector<point> mas;
  25. void input()
  26. {
  27.     cin>>n;
  28.     mas.resize(2*n);
  29.     int begin,end;
  30.     for (int i=0;i<2*n;i+=2)
  31.     {
  32.         scanf("%d %d",&begin, &end);
  33.         mas[i]   = point(begin,true);
  34.         mas[i+1] = point(end,false);
  35.     }
  36. }
  37. bool cmpPoint(const point &a, const point &b)
  38. {
  39.     if (a.value != b.value)
  40.         return a.value < b.value;
  41.     if (a.isBegin && !b.isBegin)
  42.         return true;
  43.     return false;
  44. }
  45. void solve()
  46. {
  47.     sort(mas.begin(),mas.end(),cmpPoint);
  48.     int totalLen = 0;
  49.     int segmAmount = 1;
  50.     int prev = mas[0].value;
  51.     for (int i=1;i<mas.size();i++)
  52.     {
  53.         if (segmAmount != 0)
  54.             totalLen += mas[i].value - prev;
  55.         prev = mas[i].value;
  56.         if (mas[i].isBegin)
  57.             segmAmount++;
  58.         else
  59.             segmAmount--;
  60.     }
  61.     cout<<totalLen;
  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. // Меньшиков. Тренировка 6.
  73. // 6B. Суммы [sums]
  74. // ibelyaev: 20Nov2010
  75.  
  76. #include <iostream>
  77. #include <cstdio>
  78. #include <vector>
  79.  
  80. using namespace std;
  81.  
  82. const int max_size = 50000 + 5;
  83. int n;
  84. vector<int> mas;
  85. void input()
  86. {
  87.     cin>>n;
  88.     mas.resize(n);
  89.     for (int i=0;i<n;i++)
  90.         scanf("%d", &mas[i]);
  91. }
  92. void solve()
  93. {
  94.     vector<int> met(max_size);
  95.     met[0] = 1;
  96.     int maxValue = 0;
  97.     for (int j = 0; j<mas.size();j++)
  98.     {
  99.         int newMaxValue = maxValue;
  100.         for (int i = maxValue;i>=0;i--)
  101.         {
  102.             if (met[i])
  103.             {
  104.                 met[i + mas[j]] = 1;
  105.                 newMaxValue = max(i + mas[j], newMaxValue);
  106.             }
  107.         }
  108.         maxValue = newMaxValue;
  109.     }
  110.  
  111.     int difAmount = 0;
  112.     for (int i=0;i<met.size();i++)
  113.         if (met[i])
  114.             difAmount++;
  115.     cout<<difAmount;
  116. }
  117. int main()
  118. {
  119.     freopen("input.txt","r",stdin);
  120.     freopen("output.txt","w",stdout);
  121.  
  122.     input();
  123.     solve();
  124.     return 0;
  125. }
  126. // Меньшиков. Тренировка 6.
  127. // 6C. Игра "Даты" [dategame]
  128. // ibelyaev: 23Nov2010
  129.  
  130. #include <iostream>
  131. #include <cstdio>
  132. #include <vector>
  133. #include <string.h>
  134.  
  135. using namespace std;
  136.  
  137. bool isWin[32][13];
  138. int day,mon;
  139. void input()
  140. {
  141.     cin>>day>>mon;
  142. }
  143. inline bool equal(int* a, int *b)
  144. {
  145.     return a[0] == b[0] && a[1] == b[1];
  146. }
  147. int days[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
  148. bool isCorrectDate(int* d)
  149. {
  150.     return d[1] < 13 && days[d[1]] >= d[0];
  151. }
  152. void DecDay(int* cur)
  153. {
  154.     cur[0]--;
  155.     if (cur[0] == 0)
  156.     {
  157.         cur[1]--;
  158.         cur[0] = days[cur[1]];
  159.     }
  160. }
  161. void solve()
  162. {
  163.     isWin[31][12] = true;
  164.  
  165.     int cur[2]   = {31,12};
  166.     int begin[2] = {day,mon};
  167.     do
  168.     {
  169.         DecDay(cur);
  170.         int next[2];
  171.         bool isCurWin = false;
  172.         for (int i=0;i<2;i++)
  173.         {
  174.             memcpy(next,cur,2*sizeof(int));
  175.             for (int j=1; j<=2; j++)
  176.             {
  177.                 next[i] = cur[i] + j;
  178.                 if (isCorrectDate(next))
  179.                     if (!isWin[next[0]][next[1]])
  180.                         isCurWin = true;
  181.             }
  182.         }
  183.         isWin[cur[0]][cur[1]] = isCurWin;
  184.  
  185.     } while (!equal(cur,begin));
  186. }
  187. void output()
  188. {
  189.     if (isWin[day][mon])
  190.         cout<<1;
  191.     else
  192.         cout<<2;
  193. }
  194. int main()
  195. {
  196.     freopen("input.txt","r",stdin);
  197.     freopen("output.txt","w",stdout);
  198.  
  199.     input();
  200.     solve();
  201.     output();
  202.     return 0;
  203. }
  204. // Меньшиков. Тренировка 6.
  205. // 6D. Площадь прямоугольников [rectarea]
  206. // ibelyaev: 23Nov2010
  207.  
  208. #include <iostream>
  209. #include <cstdio>
  210. #include <vector>
  211. #include <algorithm>
  212.  
  213. using namespace std;
  214.  
  215. vector<int> X,Y;
  216. void Add(vector<int> &mas , int value)
  217. {
  218.     vector<int>::iterator it = lower_bound(mas.begin(),mas.end(),value);
  219.     if (it == mas.end() || *it != value)
  220.         mas.insert(it,value);
  221. }
  222.  
  223. // оси координат вправо и вниз
  224. struct RECT
  225. {
  226.     int x0,y0; // левый верхний угол
  227.     int x1,y1; // правый нижний угол
  228.     void input()
  229.     {
  230.         int _x0,_y0,_x1,_y1;
  231.         scanf("%d %d %d %d",&_x0, &_y0, &_x1, &_y1);
  232.         if (_x0 > _x1) swap(_x0,_x1);
  233.         if (_y0 > _y1) swap(_y0,_y1);
  234.         init(_x0,_y0,_x1,_y1);
  235.         Add(X,_x0); Add(X,_x1);
  236.         Add(Y,_y0); Add(Y,_y1);
  237.     }
  238.     void init(int _x0, int _y0, int _x1, int _y1)
  239.     {
  240.         x0 = _x0;
  241.         y0 = _y0;
  242.         x1 = _x1;
  243.         y1 = _y1;
  244.     }
  245.     inline bool isInside(int left, int value, int right)
  246.     {
  247.         return left <= value && value <=right;
  248.     }
  249.     bool isParentFor(const RECT &r)
  250.     {
  251.         return isInside(x0,r.x0,x1) &&
  252.                isInside(x0,r.x1,x1) &&
  253.                isInside(y0,r.y0,y1) &&
  254.                isInside(y0,r.y1,y1);       
  255.     }
  256.     int Square()
  257.     {
  258.         return (x1 - x0) * (y1 - y0);
  259.     }
  260. };
  261. int n;
  262. vector<RECT> rects;
  263. void input()
  264. {
  265.     cin>>n;
  266.     rects.resize(n);
  267.     for (int i=0;i<n;i++)
  268.     {
  269.         RECT rect;
  270.         rect.input();
  271.         rects[i] = rect;
  272.     }
  273. }
  274. void solve()
  275. {
  276.     int totalS = 0;
  277.     RECT curRect;
  278.     for (size_t i=0;i<X.size()-1;i++)
  279.     {
  280.         for (size_t j=0;j<Y.size()-1;j++)
  281.         {
  282.             curRect.init(X[i],Y[j],X[i+1],Y[j+1]);
  283.             for (size_t k=0;k<rects.size();k++)
  284.             {
  285.                 if (rects[k].isParentFor(curRect))
  286.                 {
  287.                     totalS += curRect.Square();
  288.                     break;
  289.                 }
  290.             }
  291.         }
  292.     }
  293.     cout<<totalS;
  294. }
  295. int main()
  296. {
  297.     freopen("input.txt","r",stdin);
  298.     freopen("output.txt","w",stdout);
  299.    
  300.     input();
  301.     solve();
  302.     return 0;
  303. }
  304. // Меньшиков. Тренировка 6.
  305. // 6E. Lines [lines]
  306. // ibelyaev: 23Nov2010
  307.  
  308. #include <iostream>
  309. #include <cstdio>
  310. #include <vector>
  311. #include <queue>
  312. #include <cstring>
  313.  
  314. using namespace std;
  315.  
  316. struct point
  317. {
  318.     int x,y;
  319.     point(){}
  320.     point(int X, int Y)
  321.     {
  322.         x = X;
  323.         y = Y;
  324.     }
  325. };
  326. bool operator == (const point &a, const point &b)
  327. {
  328.     return a.x == b.x && a.y == b.y;
  329. }
  330. const int max_size = 45;
  331. int n;
  332. char mas[max_size][max_size];
  333. int  f[max_size][max_size];
  334. point begin,end;
  335. void input()
  336. {
  337.     scanf("%d\n", &n);
  338.    
  339.     char c;
  340.     for (int i=0;i<n;i++)
  341.     {
  342.         for (int j=0;j<n;j++)
  343.         {
  344.             scanf("%c",&c);
  345.             mas[i][j] = c;
  346.             if (c == '@')
  347.                 begin = point(i,j);
  348.             if (c == 'X')
  349.                 end = point(i,j);
  350.         }
  351.         scanf("%c",&c); // считываем '\n'
  352.     }
  353. }
  354. int moveX[4] = {0,1,0,-1};
  355. int moveY[4] = {1,0,-1,0};
  356. bool correct(int x, int y)
  357. {
  358.     if (x<0 || y<0)
  359.         return false;
  360.     if (x==n || y==n)
  361.         return false;
  362.     return true;
  363. }
  364. void findWay()
  365. {
  366.     memset(f,0,sizeof(f));
  367.     f[begin.x][begin.y] = 1;
  368.     queue<point> q;
  369.     q.push(begin);
  370.     while (!q.empty())
  371.     {
  372.         point cur = q.front(); q.pop();
  373.         for (int i=0;i<4;i++)
  374.         {
  375.             int x = cur.x + moveX[i];
  376.             int y = cur.y + moveY[i];
  377.             if (correct(x,y) && f[x][y]==0 && mas[x][y] != 'O')
  378.             {
  379.                 point next(x,y);
  380.                 f[x][y] = f[cur.x][cur.y] + 1;
  381.                 if (next == end)
  382.                     return;
  383.                 q.push(next);
  384.             }
  385.         }
  386.     }
  387. }
  388. void findAnswer()
  389. {
  390.     point cur = end;
  391.     int value = f[end.x][end.y]-1;
  392.     mas[end.x][end.y] = '+';
  393.     while (!(cur==begin))
  394.     {
  395.         for (int i=0;i<4;i++)
  396.         {
  397.             int x = cur.x + moveX[i];
  398.             int y = cur.y + moveY[i];
  399.             if (correct(x,y) && f[x][y] == value)
  400.             {
  401.                 value--;
  402.                 if (value != 0)
  403.                     mas[x][y] = '+';
  404.                 cur = point(x,y);
  405.                 break;
  406.             }
  407.         }
  408.     }
  409.  
  410. }
  411. void output()
  412. {
  413.     for (int i=0;i<n;i++)
  414.     {
  415.         for (int j=0;j<n;j++)
  416.             printf("%c",mas[i][j]);
  417.         printf("\n");
  418.     }
  419. }
  420. void solve()
  421. {
  422.     findWay();
  423.     if (!f[end.x][end.y])
  424.         printf("N");
  425.     else
  426.     {
  427.         printf("Y\n");
  428.         findAnswer();
  429.         output();
  430.     }
  431. }
  432.  
  433. int main()
  434. {
  435.     freopen("input.txt","r",stdin);
  436.     freopen("output.txt","w",stdout);
  437.    
  438.     input();
  439.     solve();
  440.     return 0;
  441. }
  442. // Меньшиков. Тренировка 6.
  443. // 6F. Покраска лабиринта [paintlab]
  444. // Рекурсивный DFS.
  445. // ibelyaev: 23Nov2010
  446.  
  447. #include <iostream>
  448. #include <cstdio>
  449. #include <vector>
  450. #include <cstring>
  451. #include <string.h>
  452. #include <algorithm>
  453. #include <stack>
  454. #include <queue>
  455.  
  456. using namespace std;
  457.  
  458. int n;
  459. const int max_size = 36;
  460. char mas[max_size][max_size];
  461. void input()
  462. {
  463.     scanf("%d\n",&n);
  464.     char c;
  465.     for (int i=1;i<=n;i++)
  466.     {
  467.         for (int j=1;j<=n;j++)
  468.         {
  469.             scanf("%c",&c);
  470.             mas[i][j] = c;
  471.         }
  472.         scanf("%c",&c); // считываем "\n"
  473.     }
  474.     for (int i=0;i<n+2;i++)
  475.     {
  476.         mas[0][i] = mas[n+1][i] = '#';
  477.         mas[i][0] = mas[i][n+1] = '#';
  478.     }
  479. }
  480. struct state
  481. {
  482.     int x,y,pos;
  483.     state(int X, int Y, int Pos)
  484.     {
  485.         x = X;  // координата X клетки
  486.         y = Y;  // координата Y клетки
  487.         pos = Pos; // позиция в массиве движения, с которой нужно продолжать
  488.     }
  489. };
  490. int moveX[4] = {0,1,0,-1};
  491. int moveY[4] = {1,0,-1,0};
  492. // Рекурсивный поиск в глубину
  493. void DFS(int x, int y, int &walls)
  494. {
  495.     if (mas[x][y] == '.')
  496.         mas[x][y] = 'X';
  497.     else
  498.         return;
  499.     for (int i=0;i<4;i++)
  500.     {
  501.         int nextX = x + moveX[i];
  502.         int nextY = y + moveY[i];
  503.         if (mas[nextX][nextY] == '#')
  504.             walls++;
  505.     }
  506.     for (int i=0;i<4;i++)
  507.     {
  508.         int nextX = x + moveX[i];
  509.         int nextY = y + moveY[i];
  510.         if (mas[nextX][nextY] == '.')
  511.             DFS(nextX,nextY,walls);
  512.     }
  513. }
  514. void solve()
  515. {
  516.     int walls = 0;
  517.     DFS(1,1,walls);
  518.     DFS(n,n,walls);
  519.     cout<<(walls-4) * 9;
  520. }
  521. // for debug only
  522. void output()
  523. {
  524.     cout<<endl;
  525.     for (int i=0;i<n+2;i++)
  526.     {
  527.         for (int j=0;j<n+2;j++)
  528.             cout<<mas[i][j];
  529.         cout<<endl;
  530.     }
  531. }
  532. int main()
  533. {
  534.     freopen("input.txt","r",stdin);
  535.     freopen("output.txt","w",stdout);
  536.    
  537.     input();
  538.     solve();
  539.     //output();
  540.     return 0;
  541. }
  542. // Меньшиков. Тренировка 6.
  543. // 6F. Покраска лабиринта [paintlab]
  544. // Нерекурсивный DFS.
  545. // ibelyaev: 23Nov2010
  546.  
  547. #include <iostream>
  548. #include <cstdio>
  549. #include <vector>
  550. #include <cstring>
  551. #include <string.h>
  552. #include <algorithm>
  553. #include <stack>
  554. #include <queue>
  555.  
  556. using namespace std;
  557.  
  558. int n;
  559. const int max_size = 36;
  560. char mas[max_size][max_size];
  561. void input()
  562. {
  563.     scanf("%d\n",&n);
  564.     char c;
  565.     for (int i=1;i<=n;i++)
  566.     {
  567.         for (int j=1;j<=n;j++)
  568.         {
  569.             scanf("%c",&c);
  570.             mas[i][j] = c;
  571.         }
  572.         scanf("%c",&c); // считываем "\n"
  573.     }
  574.     for (int i=0;i<n+2;i++)
  575.     {
  576.         mas[0][i] = mas[n+1][i] = '#';
  577.         mas[i][0] = mas[i][n+1] = '#';
  578.     }
  579. }
  580. struct state
  581. {
  582.     int x,y,pos;
  583.     state(int X, int Y, int Pos)
  584.     {
  585.         x = X;  // координата X клетки
  586.         y = Y;  // координата Y клетки
  587.         pos = Pos; // позиция в массиве движения, с которой нужно продолжать
  588.     }
  589. };
  590. int moveX[4] = {0,1,0,-1};
  591. int moveY[4] = {1,0,-1,0};
  592. // Нерекурсивный поиск в глубину (первый опыт :))
  593. void DFS(int x, int y, int &walls)
  594. {
  595.     stack<state> s;
  596.     if (mas[x][y] == '.')
  597.     {
  598.         s.push(state(x,y,0));
  599.         mas[x][y] = 'X';
  600.     }
  601.     while (!s.empty())
  602.     {
  603.         // считаем количество стенок
  604.         if (s.top().pos == 0)
  605.         {
  606.             for (int i=0;i<4;i++)
  607.             {
  608.                 int x = s.top().x + moveX[i];
  609.                 int y = s.top().y + moveY[i];
  610.                 if (mas[x][y] == '#')
  611.                     walls++;
  612.             }
  613.         }
  614.         for (int i=s.top().pos; i<4; i++)
  615.         {
  616.             int x = s.top().x + moveX[i];
  617.             int y = s.top().y + moveY[i];
  618.             s.top().pos++;
  619.             if (mas[x][y] == '.')
  620.             {
  621.                 mas[x][y] = 'X';
  622.                 s.push(state(x,y,0));
  623.                 break;
  624.             }
  625.         }
  626.         // Вершина стека отработана
  627.         if (s.top().pos == 4)
  628.             s.pop();
  629.     }   
  630. }
  631. void solve()
  632. {
  633.     int walls = 0;
  634.     DFS(1,1,walls);
  635.     DFS(n,n,walls);
  636.     cout<<(walls-4) * 9;
  637. }
  638. // for debug only
  639. void output()
  640. {
  641.     cout<<endl;
  642.     for (int i=0;i<n+2;i++)
  643.     {
  644.         for (int j=0;j<n+2;j++)
  645.             cout<<mas[i][j];
  646.         cout<<endl;
  647.     }
  648. }
  649. int main()
  650. {
  651.     freopen("input.txt","r",stdin);
  652.     freopen("output.txt","w",stdout);
  653.    
  654.     input();
  655.     solve();
  656.     //output();
  657.     return 0;
  658. }


Editing is locked.