v 0. Pasted by slipstak2 as cpp at 2010-11-29 18:27:17 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 7.
  2. // 7А. Упорядоченные дроби [ordfrac]
  3. // Лобовая реализация
  4. // ibelyaev: 24Nov2010
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <cstring>
  9. #include <string.h>
  10. #include <algorithm>
  11. #include <stack>
  12. #include <queue>
  13.  
  14. using namespace std;
  15.  
  16. int n;
  17. struct drob
  18. {
  19.     int ch,zn;
  20.     drob(){}
  21.     drob(int Ch, int Zn)
  22.     {
  23.         ch = Ch;
  24.         zn = Zn;
  25.     }
  26.     void output()
  27.     {
  28.         printf("%d/%d\n", ch, zn);
  29.     }
  30. };
  31. bool operator < (const drob &a, const drob &b)
  32. {
  33.     return (double)a.ch / a.zn  < (double)b.ch / b.zn;
  34. }
  35. void input()
  36. {
  37.     cin>>n;
  38. }
  39. vector<drob> mas;
  40. int gcd(int a, int b)
  41. {
  42.     if (b == 0)
  43.         return a;
  44.     return gcd(b,a%b);
  45. }
  46. void solve()
  47. {
  48.     for (int zn = 2; zn<=n; zn++)
  49.         for (int ch = 1; ch<zn; ch++)
  50.             if (gcd(ch,zn) == 1)
  51.                 mas.push_back(drob(ch,zn));
  52.     sort(mas.begin(),mas.end());
  53. }
  54. void output()
  55. {
  56.     for (int i=0;i<mas.size();i++)
  57.         mas[i].output();
  58. }
  59. int main()
  60. {
  61.     freopen("input.txt","r",stdin);
  62.     freopen("output.txt","w",stdout);
  63.    
  64.     input();
  65.     solve();
  66.     output();
  67.     return 0;
  68. }
  69. // Меньшиков. Тренировка 7.
  70. // 7А. Упорядоченные дроби [ordfrac]
  71. // На основе ряда Фарея
  72. // ibelyaev: 24Nov2010
  73. #include <iostream>
  74. #include <cstdio>
  75. #include <vector>
  76. #include <cstring>
  77. #include <string.h>
  78. #include <algorithm>
  79. #include <stack>
  80. #include <queue>
  81.  
  82. using namespace std;
  83.  
  84. int n;
  85. void input()
  86. {
  87.     cin>>n;
  88. }
  89. void find_fractions(int chLeft, int znLeft, int chRight, int znRight)
  90. {
  91.     if (znLeft > n || znRight >n)
  92.         return;
  93.     int chMiddle = chLeft + chRight;
  94.     int znMiddle = znLeft + znRight;
  95.     find_fractions(chLeft, znLeft, chMiddle, znMiddle);
  96.     if (znMiddle <=n)
  97.         printf("%d/%d\n",chMiddle, znMiddle);
  98.     find_fractions(chMiddle,znMiddle, chRight, znRight);
  99. }
  100. void solve()
  101. {
  102.     find_fractions(0,1,1,1);
  103. }
  104. int main()
  105. {
  106.     freopen("input.txt","r",stdin);
  107.     freopen("output.txt","w",stdout);
  108.    
  109.     input();
  110.     solve();
  111.     return 0;
  112. }
  113. // Меньшиков. Тренировка 7.
  114. // 7B. Сообщение [message]
  115. // ibelyaev: 24Nov2010
  116. #include <iostream>
  117. #include <cstdio>
  118. #include <vector>
  119. #include <string>
  120. #include <string.h>
  121.  
  122. using namespace std;
  123. const int max_size = 15;
  124. int osn = 1000;
  125. char* format = "%.3d";
  126. struct BigInt
  127. {
  128.     int amount;
  129.     int digits[max_size];
  130.     BigInt()
  131.     {
  132.         memset(digits,0,sizeof(digits));
  133.         amount = 1;
  134.     }
  135.     BigInt(int n)
  136.     {
  137.         memset(digits,0,sizeof(digits));
  138.         amount = 1;
  139.         digits[0] = n;
  140.     }
  141.     void output()
  142.     {
  143.         printf("%d",digits[amount-1]);
  144.         for (int i=amount-2;i>=0;i--)
  145.             printf(format,digits[i]);
  146.     }
  147. };
  148. BigInt operator + (const BigInt &a, const BigInt &b)
  149. {
  150.     BigInt res;
  151.     res.amount = max(a.amount, b.amount);
  152.     int r = 0;
  153.     for (int i=0;i<res.amount || r;i++)
  154.     {
  155.         res.digits[i] = a.digits[i] + b.digits[i] + r;
  156.         if (res.digits[i] >= osn)
  157.         {
  158.             res.digits[i] -= osn;
  159.             r = 1;
  160.         }
  161.         else
  162.             r = 0;
  163.     }
  164.     if (res.digits[res.amount])
  165.         res.amount++;
  166.     return res;
  167. }
  168. int n;
  169. string str;
  170. vector<BigInt> mas;
  171. void input()
  172. {
  173.     cin>>str;
  174.     str.insert(str.begin(),'*');
  175. }
  176. bool isCorrect(char a, char b)
  177. {
  178.     int num = 10*(a - '0') + b - '0';
  179.     return 10<=num && num<=33;
  180. }
  181. void solve()
  182. {
  183.     mas.resize(str.size());
  184.     mas[0] = 1;
  185.     mas[1] = 1;
  186.     for (size_t i=2;i<mas.size();i++)
  187.     {
  188.         mas[i] = mas[i] +  mas[i-1];
  189.         if (isCorrect(str[i-1],str[i]))
  190.             mas[i] = mas[i] + mas[i-2];
  191.     }
  192.     mas.back().output();
  193. }
  194. int main()
  195. {
  196.     freopen("input.txt","r",stdin);
  197.     freopen("output.txt","w",stdout);
  198.    
  199.     input();
  200.     solve();
  201.     return 0;
  202. }
  203. // Меньшиков. Тренировка 7.
  204. // 7C. Игра умножения [multgame]
  205. // ДП с запоминанием, использующим map. Доступ к ответу решенной подзадачи за O(logN)
  206. // ibelyaev: 25Nov2010
  207. #include <iostream>
  208. #include <cstdio>
  209. #include <map>
  210.  
  211. using namespace std;
  212.  
  213. int n;
  214. void input()
  215. {
  216.     cin>>n;
  217. }
  218. map<long long, short> memIsWin;
  219. //  1 - win
  220. // -1 - not win
  221. short isWin(long long value)
  222. {
  223.     if (memIsWin[value] != 0)
  224.         return memIsWin[value];
  225.     short isCurWin = -1;
  226.     for (int i=2;i<=9;i++)
  227.     {
  228.         if (value * i >= n || isWin(value*i) == -1)
  229.         {
  230.             isCurWin = 1;
  231.             break;
  232.         }
  233.     }
  234.     memIsWin[value] = isCurWin;
  235.     return isCurWin;
  236. }
  237. void solve()
  238. {
  239.     if (isWin(1) == 1)
  240.         cout<<"Stan wins.";
  241.     else
  242.         cout<<"Ollie wins.";
  243. }
  244. int main()
  245. {
  246.     freopen("input.txt","r",stdin);
  247.     freopen("output.txt","w",stdout);
  248.    
  249.     input();
  250.     solve();
  251.     return 0;
  252. }
  253. // Меньшиков. Тренировка 7.
  254. // 7C. Игра умножения [multgame]
  255. // Одномерное ДП без map. Доступ к ответу решенной подзадаче за O(logN)
  256. // ibelyaev: 25Nov2010
  257. #include <iostream>
  258. #include <cstdio>
  259. #include <vector>
  260. #include <algorithm>
  261.  
  262. using namespace std;
  263.  
  264. int n;
  265. void input()
  266. {
  267.     cin>>n;
  268. }
  269. long long maxValue = 4294967295;
  270. vector<long long> mas;
  271. void findMas()
  272. {
  273.     mas.push_back(1);
  274.     vector<long long>::iterator iter;
  275.     for (int i=0;i<mas.size();i++)
  276.     {
  277.         for (int j=2;j<=9;j++)
  278.         {
  279.             long long curValue = mas[i] * j;
  280.             if (curValue < maxValue)
  281.             {
  282.                 iter = lower_bound(mas.begin(),mas.end(),curValue);
  283.                 if (iter == mas.end() || *iter != curValue)
  284.                     mas.insert(iter,curValue);             
  285.             }
  286.         }
  287.     }   
  288. }
  289.  
  290. void solve()
  291. {
  292.     findMas();
  293.     vector<bool> isWin(mas.size());
  294.     vector<long long>::iterator iter;
  295.     for (int i = mas.size()-1;i>=0;i--)
  296.     {
  297.         bool isCurWin = false;
  298.         for (int j=2;j<=9;j++)
  299.         {
  300.             long long curValue = mas[i] * j;
  301.             if (curValue >=n)
  302.             {
  303.                 isCurWin = true;
  304.                 break;
  305.             }
  306.             iter = lower_bound(mas.begin(),mas.end(),curValue);
  307.             if (iter != mas.end() && *iter == curValue)
  308.             {
  309.                 int index = iter - mas.begin();
  310.                 if (!isWin[index])
  311.                 {
  312.                     isCurWin = true;
  313.                     break;
  314.                 }               
  315.             }
  316.         }
  317.         isWin[i] = isCurWin;
  318.     }
  319.     if (isWin[0])
  320.         cout<<"Stan wins.";
  321.     else
  322.         cout<<"Ollie wins.";
  323. }
  324. int main()
  325. {
  326.     freopen("input.txt","r",stdin);
  327.     freopen("output.txt","w",stdout);
  328.    
  329.     input();
  330.     solve();
  331.     return 0;
  332. }
  333. // Меньшиков. Тренировка 7.
  334. // 7D. Прямая и квадраты [sqline]
  335. // Решение за O(N)
  336. // ibelyaev: 26Nov2010
  337. #include <iostream>
  338. #include <cstdio>
  339.  
  340. using namespace std;
  341.  
  342. struct point
  343. {
  344.     int x,y;
  345.     point(){}
  346.     point(int X, int Y)
  347.     {
  348.         x = X;
  349.         y = Y;
  350.     }
  351. };
  352. struct line
  353. {
  354.     double a,b,c;
  355.     line(){}
  356.     line(point f, point s)
  357.     {
  358.         a = s.y - f.y;
  359.         b = f.x - s.x;
  360.         c = -a * f.x -b * f.y;
  361.     }
  362.     double getY(double x)
  363.     {
  364.         return (-a*x - c) / b;
  365.     }
  366. };
  367. int N, W, E;
  368. void input()
  369. {
  370.     cin>>N>>W>>E;
  371. }
  372. const double eps = 1e-8;
  373. double fabs(double a)
  374. {
  375.     if (a<0)
  376.         return -a;
  377.     return a;
  378. }
  379. bool Equal(double a, double b)
  380. {
  381.     return fabs(a-b) <= eps;
  382. }
  383. bool Less(double a, double b)
  384. {
  385.     return (a < b && !Equal(a,b));
  386. }
  387. bool More(double a, double b)
  388. {
  389.     return (a > b && !Equal(a,b));
  390. }
  391. // a - положительное, поэтому корректировать +eps
  392. bool isRoundDoulbe(double &a)
  393. {
  394.     //return a == (int)a; // может быть потеря точности double
  395.     return fabs(a - (int)(a + eps)) <= eps;
  396. }
  397. // curY - находится на краю области и не является углом
  398. // curY - нормированная величина (Y/100)
  399. bool isSideNoCornerY(int curY)
  400. {
  401.     return curY !=0 && curY != N;
  402. }
  403. void solve()
  404. {
  405.     line l(point(0,W),point(100*N, E));
  406.     // горизонтальная линия
  407.     if (l.a == 0)
  408.     {
  409.         if (W%100 == 0 && W!=0 && W != 100*N)
  410.             cout<<2*N;
  411.         else
  412.             cout<<N;
  413.         return;
  414.     }
  415.    
  416.     int crossRect = 0;
  417.     int y = W;
  418.     double prevY = l.getY(0) / 100;
  419.  
  420.     // начальная точка пересекает два прямогоульника
  421.     // один из них считаем сразу(верхний или нижний)
  422.     // второй во время первой итерации цикла
  423.     if (isRoundDoulbe(prevY) && isSideNoCornerY(prevY))
  424.         crossRect++;
  425.  
  426.     for (int x=1; x<=N;x++)
  427.     {
  428.         double curY = l.getY(100*x) / 100;
  429.         if (isRoundDoulbe(curY))
  430.         {
  431.             if (x != N) // крестовина
  432.                 crossRect += 2;// диагональные квадраты
  433.             else if (isSideNoCornerY(curY)) // квадрат снизу или сверху
  434.                 crossRect++;
  435.         }
  436.         if ((int)(curY + eps) != (int)(prevY + eps))
  437.         {
  438.             // убывающая линия
  439.             if (More(prevY,curY)&& !isRoundDoulbe(prevY))
  440.                 crossRect++; // нижний квадрат
  441.             // возрастающая линия
  442.             if (Less(prevY,curY) && !isRoundDoulbe(curY))
  443.                 crossRect++; // верхний квадрат
  444.         }
  445.         crossRect++; // текущий квадрат
  446.         prevY = curY;
  447.     }
  448.     cout<<crossRect;
  449. }
  450. int main()
  451. {
  452.     freopen("input.txt","r",stdin);
  453.     freopen("output.txt","w",stdout);
  454.    
  455.     input();
  456.     solve();
  457.     return 0;
  458. }
  459. // Меньшиков. Тренировка 7.
  460. // 7D. Прямая и квадраты [sqline]
  461. // Решение за O(N*N)
  462. // ibelyaev: 26Nov2010
  463. #include <iostream>
  464. #include <cstdio>
  465.  
  466. using namespace std;
  467.  
  468. struct point
  469. {
  470.     int x,y;
  471.     point(){}
  472.     point(int X, int Y)
  473.     {
  474.         x = X;
  475.         y = Y;
  476.     }
  477. };
  478. double eps = 1e-8;
  479. double Fabs(double a)
  480. {
  481.     if (a<0)
  482.         return -a;
  483.     return a;
  484. }
  485. int Abs(int a)
  486. {
  487.     if (a<0)
  488.         return -a;
  489.     return a;
  490. }
  491. bool Equal(double a, double b)
  492. {
  493.     return Fabs(a-b) <= eps;
  494. }
  495. bool More(double a, double b)
  496. {
  497.     return a > b && !Equal(a,b);
  498. }
  499. struct line
  500. {
  501.     double a, b, c;
  502.     line(){}
  503.     line(point f, point s)
  504.     {
  505.         a = s.y - f.y;
  506.         b = f.x - s.x;
  507.         c = -a*f.x - b*f.y;
  508.     }
  509.     int getSign (int x, int y)
  510.     {
  511.         double value = a*x + b*y + c;
  512.         if (Equal(value, 0.0))
  513.             return 0;
  514.         else if (More(value, 0.0))
  515.             return 1;
  516.         else
  517.             return -1;
  518.     }
  519. };
  520. int n,w,e;
  521. void input()
  522. {
  523.     cin>>n>>w>>e;
  524. }
  525. void solve()
  526. {
  527.     line l(point(0,w),point(100*n,e));
  528.     int size = 100*n;
  529.     int amount = 0;
  530.     for (int i=0;i<size;i+=100)
  531.     {
  532.         for (int j=0;j<size;j+=100)
  533.         {
  534.             int res =
  535.             l.getSign(i    ,j) +
  536.             l.getSign(i+100,j) +
  537.             l.getSign(i    ,j+100) +
  538.             l.getSign(i+100,j+100);
  539.            
  540.             if (Abs(res) != 4)
  541.                 amount++;
  542.         }
  543.     }
  544.     cout<<amount;
  545. }
  546. int main()
  547. {
  548.     freopen("input.txt","r",stdin);
  549.     freopen("output.txt","w",stdout);
  550.    
  551.     input();
  552.     solve();
  553.     return 0;
  554. }
  555. // Меньшиков. Тренировка 7.
  556. // 7E. Lines(2) [lines2]
  557. // Аналог 6E. Lines
  558. // ibelyaev: 29Nov2010
  559. #include <iostream>
  560. #include <cstdio>
  561. #include <vector>
  562. #include <queue>
  563. #include <cstring>
  564.  
  565. using namespace std;
  566.  
  567. struct point
  568. {
  569.     int x,y;
  570.     point(){}
  571.     point(int X, int Y)
  572.     {
  573.         x = X;
  574.         y = Y;
  575.     }
  576. };
  577. bool operator == (const point &a, const point &b)
  578. {
  579.     return a.x == b.x && a.y == b.y;
  580. }
  581. const int max_size = 255;
  582. int n;
  583. char mas[max_size][max_size];
  584. int  f[max_size][max_size];
  585. point begin,end;
  586. void input()
  587. {
  588.     scanf("%d\n", &n);
  589.    
  590.     char c;
  591.     for (int i=0;i<n;i++)
  592.     {
  593.         for (int j=0;j<n;j++)
  594.         {
  595.             scanf("%c",&c);
  596.             mas[i][j] = c;
  597.             if (c == '@')
  598.                 begin = point(i,j);
  599.             if (c == 'X')
  600.                 end = point(i,j);
  601.         }
  602.         scanf("%c",&c); // считываем '\n'
  603.     }
  604. }
  605. int moveX[4] = {0,1,0,-1};
  606. int moveY[4] = {1,0,-1,0};
  607. bool correct(int x, int y)
  608. {
  609.     if (x<0 || y<0)
  610.         return false;
  611.     if (x==n || y==n)
  612.         return false;
  613.     return true;
  614. }
  615. void findWay()
  616. {
  617.     memset(f,0,sizeof(f));
  618.     f[begin.x][begin.y] = 1;
  619.     queue<point> q;
  620.     q.push(begin);
  621.     while (!q.empty())
  622.     {
  623.         point cur = q.front(); q.pop();
  624.         for (int i=0;i<4;i++)
  625.         {
  626.             int x = cur.x + moveX[i];
  627.             int y = cur.y + moveY[i];
  628.             if (correct(x,y) && f[x][y]==0 && mas[x][y] != 'O')
  629.             {
  630.                 point next(x,y);
  631.                 f[x][y] = f[cur.x][cur.y] + 1;
  632.                 if (next == end)
  633.                     return;
  634.                 q.push(next);
  635.             }
  636.         }
  637.     }
  638. }
  639. void findAnswer()
  640. {
  641.     point cur = end;
  642.     int value = f[end.x][end.y]-1;
  643.     mas[end.x][end.y] = '+';
  644.     while (!(cur==begin))
  645.     {
  646.         for (int i=0;i<4;i++)
  647.         {
  648.             int x = cur.x + moveX[i];
  649.             int y = cur.y + moveY[i];
  650.             if (correct(x,y) && f[x][y] == value)
  651.             {
  652.                 value--;
  653.                 if (value != 0)
  654.                     mas[x][y] = '+';
  655.                 cur = point(x,y);
  656.                 break;
  657.             }
  658.         }
  659.     }
  660.  
  661. }
  662. void output()
  663. {
  664.     for (int i=0;i<n;i++)
  665.     {
  666.         for (int j=0;j<n;j++)
  667.             printf("%c",mas[i][j]);
  668.         printf("\n");
  669.     }
  670. }
  671. void solve()
  672. {
  673.     findWay();
  674.     if (!f[end.x][end.y])
  675.         printf("N");
  676.     else
  677.     {
  678.         printf("Y\n");
  679.         findAnswer();
  680.         output();
  681.     }
  682. }
  683.  
  684. int main()
  685. {
  686.     freopen("input.txt","r",stdin);
  687.     freopen("output.txt","w",stdout);
  688.    
  689.     input();
  690.     solve();
  691.     return 0;
  692. }
  693. // Меньшиков. Тренировка 7.
  694. // 7F. Удаление клеток [remsquar]
  695. // ibelyaev: 29Nov2010
  696. #include <iostream>
  697. #include <cstdio>
  698. #include <queue>
  699.  
  700. using namespace std;
  701.  
  702. const int max_size = 100+5;
  703. int n,m;
  704. char mas[max_size][max_size];
  705. void input()
  706. {
  707.     cin>>n>>m;
  708.     for (int i=0;i<n;i++)
  709.     {
  710.         getchar(); // переход на новую строку
  711.         for (int j=0;j<m;j++)
  712.         {
  713.             mas[i][j] = getchar();
  714.         }       
  715.     }
  716. }
  717. struct point
  718. {
  719.     int x,y;
  720.     point(){}
  721.     point(int X, int Y)
  722.     {
  723.         x = X; y = Y;
  724.     }
  725. };
  726. int moveX[4] = {0,1,0,-1};
  727. int moveY[4] = {1,0,-1,0};
  728. bool correct(int x, int y)
  729. {
  730.     if (x<0 || y<0)
  731.         return false;
  732.     if (x>=n || y>=m)
  733.         return false;
  734.     return true;
  735. }
  736. void bfs(int x, int y)
  737. {
  738.     queue<point> q;
  739.     q.push(point(x,y));
  740.     while (!q.empty())
  741.     {
  742.         point cur = q.front(); q.pop();
  743.         for (int i=0;i<4;i++)
  744.         {
  745.             int x = cur.x + moveX[i];
  746.             int y = cur.y + moveY[i];
  747.             if (correct(x,y) && mas[x][y] == '#')
  748.             {
  749.                 q.push(point(x,y));
  750.                 mas[x][y] = '.';
  751.             }
  752.         }
  753.     }
  754. }
  755. void solve()
  756. {
  757.     int amount = 0;
  758.     for (int i=0;i<n;i++) {
  759.         for (int j=0;j<m;j++) {
  760.             if (mas[i][j] == '#')
  761.             {
  762.                 mas[i][j] = '.';
  763.                 bfs(i,j);
  764.                 amount++;
  765.             }
  766.         }
  767.     }
  768.     cout<<amount;
  769. }
  770. int main()
  771. {
  772.     freopen("input.txt","r",stdin);
  773.     freopen("output.txt","w",stdout);
  774.    
  775.     input();
  776.     solve();
  777.     return 0;
  778. }


Editing is locked.