v 0. Pasted by UnderFelixAbove as cpp at 2010-05-18 23:22:06 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 3.
  2. // 3A. Разложение на простые множители [pfactor]
  3. // ibelyaev: 28Feb2010
  4.  
  5. #include <iostream>
  6. #include <vector>
  7. #include <cmath>
  8.  
  9. using namespace std;
  10. int n;
  11. vector<int> muls;
  12. void FindAllSumMul()
  13. {
  14.     int curMul = 2;
  15.     int sqrt_N = sqrt((double)n);
  16.     while (curMul<=sqrt_N)
  17.     {
  18.         while (n % curMul == 0)
  19.         {
  20.             muls.push_back(curMul);
  21.             n /= curMul;
  22.         }
  23.         curMul++;
  24.         sqrt_N = sqrt((double)n);
  25.     }
  26.     if (n!=1)
  27.         muls.push_back(n);
  28. }
  29. void output()
  30. {
  31.     cout<<muls[0];
  32.     for (int i=1;i<muls.size();i++)
  33.         cout<<'*'<<muls[i];
  34. }
  35. int main()
  36. {
  37.     cin>>n;
  38.     FindAllSumMul();
  39.     output();
  40.     return 0;
  41. }
  42.  
  43. // Меньшиков. Тренировка 3.
  44. // 3B. Перестановки (2) [permut2]
  45. // Рекурсивная реализация с подсчетом элементов
  46. // ibelyaev: 28Feb2010
  47. #include <iostream>
  48. #include <string>
  49. #include <vector>
  50.  
  51. using namespace std;
  52.  
  53. string letters,perm;
  54. vector<int>  amounts;
  55. int n;
  56. void input()
  57. {
  58.     string str;
  59.     cin>>str;
  60.     n = str.size();
  61.     for (int i =0;i<str.size();i++)
  62.     {
  63.         bool isExist = false;
  64.         for (int j = 0;j<letters.size();j++)
  65.         {
  66.             if (letters[j] == str[i])
  67.             {
  68.                 amounts[j]++;
  69.                 isExist = true;
  70.             }
  71.         }
  72.         if (!isExist)
  73.         {
  74.             letters.push_back(str[i]);
  75.             amounts.push_back(1);
  76.         }
  77.     }
  78. }
  79. void output()
  80. {
  81.     //[cout - 0.2 c,printf 0.02 c]
  82.     cout<<perm<<endl;
  83. }
  84. void rec(int pos)
  85. {
  86.     if (pos == n)
  87.         output();
  88.     for (int i=0;i<letters.size();i++)
  89.     {
  90.         if (amounts[i])
  91.         {
  92.             perm[pos] = letters[i];
  93.             amounts[i]--;
  94.             rec(pos+1);
  95.             amounts[i]++;
  96.             perm[pos] = '*'; // for debug only
  97.         }
  98.  
  99.     }
  100. }
  101. void solve()
  102. {
  103.     perm = string(n,'*');
  104.     rec(0);
  105. }
  106. int main()
  107. {
  108.     input();
  109.     solve();
  110.     return 0;
  111. }
  112.  
  113. // Меньшиков. Тренировка 3.
  114. // 3B. Перестановки (2) [permut2]
  115. // Решение идентично 2B по принципу next_permutation
  116. // ibelyaev: 02Mar2010
  117.  
  118. #include <iostream>
  119. #include <string>
  120. #include <algorithm>
  121. using namespace std;
  122.  
  123. string str;
  124. void input()
  125. {
  126.     cin>>str;
  127. }
  128. bool next_permutation(string &str)
  129. {
  130.     // находим элемент меньше или равного последующему
  131.     int pos = -1;
  132.     for (int i=str.size()-2;i>=0;i--)
  133.         if (str[i] < str[i+1])
  134.         {
  135.             pos = i;
  136.             break;
  137.         }
  138.     if (pos == -1)
  139.         return false; // текущая перестановка последняя в лексикографическом порядке
  140.     // находим минимальный элемент превышающий найденый
  141.     char value = str[pos];
  142.     int swapIndex = -1;
  143.     for (int i=str.size()-1;i>=pos;i--)
  144.         if (str[i]>value)
  145.         {
  146.             swapIndex = i;
  147.             break;
  148.         }
  149.     swap(str[pos],str[swapIndex]);
  150.     //реверс подстроки правее индекса pos
  151.     int f = pos+1, s = str.size()-1;
  152.     while (f<s)
  153.         swap(str[f++],str[s--]);
  154.     return true;
  155. }
  156. void solve()
  157. {
  158.     sort(str.begin(),str.end());
  159.     cout<<str<<endl;
  160.     while (next_permutation(str))
  161.         cout<<str<<endl;
  162. }
  163. int main()
  164. {
  165.     input();
  166.     solve();
  167.     return 0;
  168. }
  169.  
  170. // Меньшиков. Тренировка 3.
  171. // 3C. Копилка [piggy]
  172. // ibelyaev: 02Mar2010
  173. #include <iostream>
  174. #include <vector>
  175. #include <limits.h>
  176.  
  177. using namespace std;
  178.  
  179. vector<int> P,W;
  180. int n;
  181. int E,F;
  182. vector<int> MAX, MIN;
  183. void input()
  184. {
  185.     cin>>E>>F;
  186.     cin>>n;
  187.     MAX = vector<int>(F - E + 1,INT_MIN);
  188.     MIN = vector<int>(F - E + 1,INT_MAX);
  189.     P.resize(n); W.resize(n);
  190.     for (int i=0;i<n;i++)
  191.         cin>>P[i]>>W[i];
  192. }
  193. void solve()
  194. {
  195.     MIN[0] = 0;
  196.     MAX[0] = 0;
  197.     for (int i = 0;i<MIN.size();i++)
  198.     {
  199.         for (int j=0;j<W.size();j++)
  200.         {
  201.             if (i - W[j]>=0 && MIN[i-W[j]]!=INT_MAX)
  202.             {
  203.                 MIN[i] = min(MIN[i],MIN[i-W[j]] + P[j]);
  204.                 MAX[i] = max(MAX[i],MAX[i-W[j]] + P[j]);
  205.             }
  206.         }
  207.     }
  208.    
  209. }
  210. void output()
  211. {
  212.     if (MIN.back()==INT_MAX)
  213.         cout<<"This is impossible.";
  214.     else
  215.         cout<<MIN.back()<<' '<<MAX.back();
  216. }
  217. int main()
  218. {
  219.     input();
  220.     solve();
  221.     output();
  222.  
  223.     return 0;
  224. }
  225.  
  226. // Меньшиков. Тренировка 3.
  227. // 3D. Открытка и конверт [postcard]
  228. // ibelyaev: 02Mar2010
  229.  
  230. #include <iostream>
  231. #include <cmath>
  232.  
  233. using namespace std;
  234.  
  235. double pi = 2*acos(0.0);
  236. int h,w,H,W;
  237. void input()
  238. {
  239.     cin>>h>>w;
  240.     cin>>H>>W;
  241. }
  242. double Fabs(double a)
  243. {
  244.     if (a<0)
  245.         return -a;
  246.     return a;
  247. }
  248. double eps = 1e-9;
  249. bool Equal(double a, double b)
  250. {
  251.     return Fabs(a-b) <= eps;
  252. }
  253. bool LessEqual(double a, double b)
  254. {
  255.     return a<b || Equal(a,b);
  256. }
  257. bool isInside(int w, int h, int W, int H)
  258. {
  259.     if (h>w) swap(h,w);
  260.     if (H>W) swap(H,W);
  261.     // тривиальный случай
  262.     if (h<=H && w<=W)
  263.         return true;
  264.     else // Под углом
  265.     {
  266.         double beta = acos((double)H / sqrt((double)(h*h + w*w)));
  267.         double phi  = acos((double)W / sqrt((double)(h*h + w*w)));
  268.  
  269.         double alpha = 2* atan((double)h/(double)w);
  270.         double Alpha = pi/2 - beta - phi;
  271.         return LessEqual(alpha,Alpha);
  272.     }
  273. }
  274. void solve()
  275. {
  276.     if (isInside(w,h,W,H))
  277.         cout<<"Possible";
  278.     else
  279.         cout<<"Impossible";
  280. }
  281. int main()
  282. {
  283.     input();
  284.     solve();
  285.     return 0;
  286. }
  287.  
  288. // Меньшиков. Тренировка 3.
  289. // 3E. Длинное произведение [longprod]
  290. // ibelyaev: 02Mar2010
  291.  
  292. #include <iostream>
  293. #include <string>
  294. #include <cstring>
  295.  
  296. using namespace std;
  297.  
  298. const int max_len = 5100;
  299. struct BigInt
  300. {
  301.     int digits[max_len];
  302.     int amount;
  303.     BigInt()
  304.     {
  305.         memset(digits,0,sizeof(digits));
  306.         amount = 1;
  307.     }
  308.     void init(string &str)
  309.     {
  310.         memset(digits,0,sizeof(digits));
  311.         amount = str.size();
  312.         int pos = 0;
  313.         for (int i=amount-1;i>=0;i--)
  314.             digits[pos++] = str[i] - '0';
  315.     }
  316.     void input()
  317.     {
  318.         string str;
  319.         cin>>str;
  320.         init(str);
  321.     }
  322.     void output()
  323.     {
  324.         for (int i=amount-1;i>=0;i--)
  325.             cout<<digits[i];
  326.     }
  327. };
  328. int osn = 10;
  329. BigInt operator * (const BigInt &a, const BigInt &b)
  330. {
  331.     BigInt res;
  332.     int r = 0;
  333.     for (int i=0;i<a.amount;i++){
  334.         for (int j=0;j<b.amount | r;j++)
  335.         {
  336.             res.digits[i+j] += a.digits[i]*b.digits[j]+r;
  337.             r = res.digits[i+j]/osn;
  338.             res.digits[i+j] -= r * osn;
  339.         }
  340.     }
  341.     int pos = a.amount + b.amount;
  342.     while (pos>0 && !res.digits[pos])
  343.         pos--;
  344.     res.amount = pos + 1;
  345.     return res;
  346. }
  347. int main()
  348. {
  349.     BigInt a,b,res;
  350.     a.input();
  351.     b.input();
  352.     res = a*b;
  353.     res.output();
  354.     return 0;
  355. }
  356.  
  357. // Меньшиков. Тренировка 3.
  358. // 3F. Змейка [serpent]
  359. // ibelyaev: 02Mar2010
  360.  
  361. #include <iostream>
  362. #include <vector>
  363.  
  364. using namespace std;
  365.  
  366. vector<vector<int> > mas;
  367. int n;
  368. void input()
  369. {
  370.     cin>>n;
  371.     mas = vector<vector<int> >(n,vector<int>(n,0));
  372. }
  373. void solve()
  374. {
  375.     int cur = 1, j,f,s;
  376.     for (int c = 0;c<2*n-1;c++)
  377.     {
  378.         if (c-n+1 < 0)
  379.         {
  380.             f = 0;
  381.             s = c;
  382.         }
  383.         else
  384.         {
  385.             f = c-n+1;
  386.             s = c - f;
  387.         }
  388.         if (c&1)
  389.         {
  390.             for (int i=f;i<=s;i++)
  391.             {
  392.                 j = c - i;
  393.                 mas[i][j] = cur++;
  394.             }
  395.         }
  396.         else
  397.         {
  398.             for (int i=s;i>=f;i--)
  399.             {
  400.                 j = c - i;
  401.                 mas[i][j] = cur++;
  402.             }
  403.         }
  404.     }
  405. }
  406. void output()
  407. {
  408.     for (int i=0;i<n;i++)
  409.     {
  410.         for (int j=0;j<n;j++)
  411.         {
  412.             cout<<mas[i][j]<<' ';
  413.         }
  414.         cout<<endl;
  415.     }
  416. }
  417. int main()
  418. {
  419.     input();
  420.     solve();
  421.     output();
  422.     return 0;
  423. }
  424.  
  425. // Меньшиков. Тренировка 3.
  426. // 3F. Змейка [serpent]
  427. // ibelyaev: 15May2010
  428.  
  429. #include <iostream>
  430. #include <vector>
  431.  
  432. using namespace std;
  433.  
  434. vector<vector<int> > mas;
  435. int n;
  436. bool correct(int x, int y)
  437. {
  438.     if (x<0 || y<0)
  439.         return false;
  440.     if (x>=n || y>=n)
  441.         return false;
  442.     return true;
  443. }
  444. void input()
  445. {
  446.     cin>>n;
  447.     mas = vector<vector<int> >(n,vector<int>(n,0));
  448. }
  449. void solve()
  450. {
  451.     int pos = 1;
  452.     for (int c = 0; c<2*n; c++)
  453.     {
  454.         if (c%2)
  455.         {
  456.             for (int i=0;i<n;i++)
  457.             {
  458.                 int j = c - i;
  459.                 if (correct(i,j))
  460.                     mas[i][j] = pos++;
  461.             }
  462.         }
  463.         else
  464.         {
  465.             for (int i=n-1;i>=0;i--)
  466.             {
  467.                 int j = c - i;
  468.                 if (correct(i,j))
  469.                     mas[i][j] = pos++;
  470.             }
  471.         }
  472.     }
  473. }
  474. void output()
  475. {
  476.     for (int i=0;i<n;i++)
  477.     {
  478.         for (int j=0;j<n;j++)
  479.             cout<<mas[i][j]<<' ';
  480.         cout<<endl;
  481.     }
  482. }
  483.  
  484. int main()
  485. {
  486.     input();
  487.     solve();
  488.     output();
  489.     return 0;
  490. }


Editing is locked.