v 0. Pasted by slipstak2 as cpp at 2011-01-17 21:16:43 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 15.
  2. // 15A. Игра с калькулятором [calcgame]
  3. // ibelyaev: 14Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8.  
  9. using namespace std;
  10.  
  11. const int MAX_VALUE = 1e9;
  12. int k;
  13. vector<bool> mem(1000);
  14. int resD = MAX_VALUE, resL = MAX_VALUE;
  15. void input()
  16. {
  17.     cin>>k;
  18. }
  19. void solve()
  20. {
  21.     int prev,cur;
  22.     for (int d = 1; d <= 9; d++) {
  23.         fill(mem.begin(), mem.end(), 0);
  24.  
  25.         int prev = d % k;
  26.  
  27.         if (prev == 0) {
  28.             resD = d; resL = 1;
  29.             return;
  30.         }
  31.         mem[prev] = true;
  32.         for (int len = 2; len <= k + 1; len++) {
  33.             cur = (prev * 10 + d) % k;
  34.             if (cur == 0) {
  35.                 if (len < resL) {
  36.                     resL = len;
  37.                     resD = d;
  38.                 }
  39.             }
  40.             prev = cur;
  41.             mem[cur] = true;
  42.         }
  43.     }
  44. }
  45. void output() {
  46.     if (resD == MAX_VALUE)
  47.         cout<<"Impossible";
  48.     else
  49.         cout<<resD<<' '<<resL;
  50. }
  51. int main()
  52. {
  53.     freopen("input.txt","r",stdin);
  54.     freopen("output.txt","w",stdout);
  55.  
  56.     input();
  57.     solve();
  58.     output();
  59.    
  60.     return 0;
  61. }
  62.  
  63. // Меньшиков. Тренировка 15.
  64. // 15B. Площадь треугольника [tria-abm]
  65. // ibelyaev: 14Jan2011
  66.  
  67. #include <iostream>
  68. #include <cstdio>
  69. #include <cmath>
  70.  
  71. using namespace std;
  72. const double eps = 1e-6;
  73.  
  74. double h,m,b;
  75. void input()
  76. {
  77.     cin>>h>>b>>m;
  78. }
  79. double getB(double x) {
  80.     double d = sqrt(m*m - h*h);
  81.     double l = sqrt(h*h + (d+x)*(d+x));
  82.     double r = sqrt(h*h + (d-x)*(d-x));
  83.     double bpx = d - x + (2*r*x) / (l+r);
  84.     return sqrt(bpx*bpx + h*h);
  85. }
  86. void solve()
  87. {
  88.     if (h>b) swap(h,b);
  89.     if (b>m) swap(b,m);
  90.     if (h>b) swap(h,b);
  91.     if (h == b && b == m)
  92.         cout<<0;
  93.     else if(h==b || b==m)
  94.         cout<<-1;
  95.     else {
  96.         double l = 0, r = 2e9;
  97.         while (l + eps < r) {
  98.             double m = (l + r) / 2;
  99.             if (getB(m) > b)
  100.                 l = m;
  101.             else
  102.                 r = m;
  103.         }
  104.         printf("%0.5f",l*h);       
  105.     }
  106. }
  107. int main()
  108. {
  109.     freopen("input.txt","r",stdin);
  110.     freopen("output.txt","w",stdout);
  111.  
  112.     input();
  113.     solve();
  114.     return 0;
  115. }
  116.  
  117. // Меньшиков. Тренировка 15.
  118. // 15С. Формирование поезда [train-ab]
  119. // ibelyaev: 16Jan2011
  120.  
  121. #include <iostream>
  122. #include <cstdio>
  123. #include <vector>
  124.  
  125. using namespace std;
  126. typedef long long i64;
  127. typedef vector<i64> vi64;
  128. typedef vector<vi64 > vvi64;
  129. typedef vector<vvi64 > vvvi64;
  130. int n,k;
  131. char x,y;
  132. int aa,ab,ba,bb;
  133. vector<vector<vector<i64> > > prev,cur;
  134. void input()
  135. {
  136.     cin>>n>>k;
  137.     cur  = vvvi64(k+1,vvi64(k+1,vi64(3,0)));
  138.     prev = vvvi64(k+1,vvi64(k+1,vi64(3,0)));
  139.     scanf("\n%c%c\n",&y,&x);
  140.     y-='A' - 1; x-='A' - 1;
  141.     char cX,cY;
  142.     for (int i=0;i<n;i++) {
  143.         scanf("%c%c\n",&cX,&cY);
  144.         if (cX == 'A' && cY == 'A') aa++;
  145.         if (cX == 'A' && cY == 'B') ab++;
  146.         if (cX == 'B' && cY == 'A') ba++;
  147.         if (cX == 'B' && cY == 'B') bb++;
  148.     }
  149. }
  150. void solve()
  151. {
  152.     if (x == 1) {
  153.         if (aa>0) cur[1][0][1] = 1;
  154.         if (ab>0) cur[0][1][2] = 1;
  155.     }
  156.     else {
  157.         if (ba>0) cur[0][0][1] = 1;
  158.         if (bb>0) cur[0][0][2] = 1;
  159.     }
  160.     prev.swap(cur);
  161.  
  162.     for (int len = 2; len<=k; len++) {
  163.         for (int AA=0; AA<=len; AA++){
  164.             for (int AB=0; AB<=len; AB++){
  165.                 if (aa>=AA && ab>=AB && AA+AB<=len) {
  166.                     cur[AA][AB][1] = 0;
  167.                     cur[AA][AB][2] = 0;
  168.                     if (x==1) {
  169.                         int BA = AB; // x = 'A'  E = 'A'
  170.                         int BB = len - AA - AB - BA;
  171.                         if (BB>=0 && BB<=bb && BA<=ba) {
  172.                             if (AA >= 1) cur[AA][AB][1] += prev[AA-1][AB][1];
  173.                             if (BA >= 1) cur[AA][AB][1] += prev[AA][AB][2];
  174.                         }
  175.  
  176.                         BA = AB-1; // x = 'A'  E ='B'
  177.                         BB = len - AA - AB - BA;
  178.                         if (BB>=0 && BB<=bb && BA<=ba) {
  179.                             if (AB >= 1) cur[AA][AB][2] += prev[AA][AB-1][1];
  180.                             if (BB >= 1) cur[AA][AB][2] += prev[AA][AB][2];
  181.                         }
  182.                     }
  183.                     else if (x==2) {
  184.                         int BA = AB + 1; // x = 'B' E = 'A'
  185.                         int BB = len - AA - AB - BA;
  186.                         if (BB>=0 && BB<=bb && BA <= ba) {
  187.                             if (AA >= 1)
  188.                                 cur[AA][AB][1] += prev[AA-1][AB][1];
  189.                             if (BA >= 1)
  190.                                 cur[AA][AB][1] += prev[AA][AB][2];
  191.                         }
  192.  
  193.                         BA = AB; // x = 'B' E = 'B'
  194.                         BB = len - AA - AB - BA;
  195.                         if (BB>=0 && BB<=bb && BA <= ba) {
  196.                             if (AB >= 1)
  197.                                 cur[AA][AB][2] += prev[AA][AB-1][1];
  198.                             if (BB >= 1)
  199.                                 cur[AA][AB][2] += prev[AA][AB][2];
  200.                         }
  201.                     }
  202.                 }
  203.  
  204.             }
  205.         }
  206.         cur.swap(prev);
  207.     }
  208.  
  209.     i64 res = 0;
  210.     for (int AA=0; AA<=k; AA++) {
  211.         for (int AB=0; AB<=k; AB++) {
  212.             res += prev[AA][AB][y];
  213.         }
  214.     }
  215.     if (res == 0)
  216.         cout<<"NO";
  217.     else
  218.         cout<<"YES"<<endl<<res;
  219. }
  220. int main()
  221. {
  222.     freopen("input.txt","r",stdin);
  223.     freopen("output.txt","w",stdout);
  224.  
  225.     input();
  226.     solve();
  227.     return 0;
  228. }
  229.  
  230. // Меньшиков. Тренировка 15.
  231. // 15D. Стена [wall]
  232. // ibelyaev: 16Jan2011
  233.  
  234. #include <iostream>
  235. #include <cstdio>
  236. #include <vector>
  237. #include <algorithm>
  238. #include <cmath>
  239. using namespace std;
  240.  
  241. typedef pair<int, int> point;
  242. #define X first
  243. #define Y second
  244.  
  245. const double pi = 2*acos(0.0);
  246. int n, R;
  247. vector<point> points;
  248.  
  249. void input() {
  250.     cin>>n>>R;
  251.     points.resize(n);
  252.     int x,y;
  253.     for (int i=0;i<n;i++) {
  254.         cin>>x>>y;
  255.         points[i] = point(x,y);
  256.     }   
  257. }
  258. bool cw(const point &a, const point &b, const point &c) {
  259.     return a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y) < 0;
  260. }
  261. vector<point> convexHull(vector<point> &p) {
  262.  
  263.     int k = 0;
  264.     sort(p.begin(), p.end());
  265.     vector<point> q(n*2); // ?
  266.     for (int i=0; i<n; q[k++] = p[i++])
  267.         for ( ; k>=2 && !cw(q[k-2],q[k-1],p[i]); --k)
  268.             ;
  269.     for (int i=n-2, t=k; i>=0; q[k++] = p[i--])
  270.         for ( ; k > t && !cw(q[k-2],q[k-1],p[i]); --k)
  271.             ;
  272.     q.resize(k-1 - (q[0] == q[1]));
  273.     return q;
  274. }
  275. double dist(point &a, point &b) {
  276.     return sqrt(0.0 + (a.X - b.X)*(a.X - b.X) + (a.Y - b.Y)*(a.Y - b.Y));
  277. }
  278. void solve() {
  279.     vector<point> hull = convexHull(points);
  280.     double res = 2*pi*R;
  281.     for (int i=0; i<hull.size();++i) {
  282.         res += dist(hull[i], hull[(i+1)%hull.size()]);
  283.     }
  284.     printf("%0.0f",res);
  285. }
  286. int main() {
  287.     freopen("input.txt","r",stdin);
  288.     freopen("output.txt","w",stdout);
  289.     input();
  290.     solve();
  291. }
  292.  
  293. // Меньшиков. Тренировка 15.
  294. // 15E. Семечки [seeds]
  295. // ibelyaev: 17Jan2011
  296.  
  297. #include <iostream>
  298. #include <cstdio>
  299. #include <vector>
  300. #include <algorithm>
  301.  
  302. using namespace std;
  303.  
  304. int n;
  305. vector<int> Pr,B,posPr,PrRev;
  306. int maxP = -1, resL = -1, resP = -1;
  307. void input()
  308. {
  309.     cin>>n;
  310.     Pr.resize(n); B.resize(n);
  311.     for (int i=0;i<n;i++) {
  312.         cin>>Pr[i];
  313.         posPr.push_back(Pr[i]);
  314.         posPr.push_back(Pr[i]-1);
  315.     }
  316.     for (int i=0;i<n;i++)
  317.         cin>>B[i];
  318. }
  319. int calc(int L, int P, vector<int> &Pr) {
  320.     int curB = 0;
  321.     // идем слева
  322.     bool isLeft = true;
  323.     for (int i=0; i <= L;i++) {
  324.         if (Pr[i]<P)
  325.             isLeft = false;
  326.     }
  327.     if (isLeft) {
  328.         int ML = n-1;
  329.         for (int i=L+1;i<n-1;i++) {
  330.             if (Pr[i] <= P) {
  331.                 ML = i;
  332.                 break;
  333.             }
  334.         }
  335.         for (int i=L+1; i<=ML; i++)
  336.             curB += B[i];               
  337.     }
  338.     return curB;
  339. }
  340. void solve()
  341. {
  342.     sort(posPr.begin(),posPr.end());
  343.     vector<int>::iterator it = unique(posPr.begin(),posPr.end());
  344.     posPr.resize( it - posPr.begin());
  345.     PrRev = Pr;
  346.     reverse(PrRev.begin(),PrRev.end());
  347.     for (int L=0; L<=n-2; L++) {
  348.         for (vector<int>::iterator P = posPr.begin(); P != posPr.end(); P++) {
  349.             int f = calc(L, *P,Pr);
  350.  
  351.             int s = calc(n-2-L, *P,PrRev);
  352.  
  353.             int curB = f+s;
  354.  
  355.             int curP = curB * *P;
  356.             if (curP > maxP) {
  357.                 maxP = curP;
  358.                 resP = *P;
  359.                 resL = L;
  360.             }
  361.         }
  362.     }
  363.     cout<<resL+1<<' '<<resP;
  364. }
  365. int main()
  366. {
  367.     freopen("input.txt","r",stdin);
  368.     freopen("output.txt","w",stdout);
  369.  
  370.     input();
  371.     solve();
  372.     return 0;
  373. }
  374.  
  375. // Меньшиков. Тренировка 15.
  376. // 15F. Умножение многочленов [polymul]
  377. // ibelyaev: 17Jan2011
  378.  
  379. #include <iostream>
  380. #include <cstdio>
  381. #include <vector>
  382. #include <string>
  383.  
  384. using namespace std;
  385. const int MAX_POW = 10 * 2 + 5;
  386.  
  387. typedef long long i64;
  388. typedef vector<i64> polynom;
  389.  
  390. void SkipSeps(char* &pos) {
  391.     while (*pos == ' ')
  392.         pos++;
  393. }
  394. bool isEnd(char* &pos) {
  395.     SkipSeps(pos);
  396.     return pos == 0;
  397. }
  398. bool isPlusOrMinus(const char* pos) {
  399.     return *pos == '+' || *pos =='-';
  400. }
  401. bool isDigit(char p) {
  402.     return '0' <= p && p <='9';
  403. }
  404. void ReadNumber(char * &pos, int &num) {
  405.     if (isEnd(pos)) return;
  406.     while (!isEnd(pos) && isDigit(*pos)) {
  407.         num = num*10 + *pos - '0';
  408.         pos++;
  409.     }
  410. }
  411. void ReadPower(char* &pos, int &pow) {
  412.     // <Степень> ::= "^"<Число>
  413.     if (isEnd(pos)) return;
  414.     if (*pos!='^') {
  415.         pow = 1;
  416.         return;
  417.     }else {
  418.         pos++;
  419.         pow = 0;
  420.         ReadNumber(pos, pow);
  421.     }
  422. }
  423. void ReadKoef(char* &pos, int &k) {
  424.     // <Коэффициент> ::= ("+" | "-")<Число>
  425.     if (isEnd(pos)) return;
  426.  
  427.     bool isNeg = false;
  428.     if (isPlusOrMinus(pos)){
  429.         isNeg = *pos == '-';
  430.         pos++;
  431.     }
  432.     if (isDigit(*pos)) {
  433.         k = 0;
  434.         ReadNumber(pos, k);
  435.     }
  436.     else
  437.         k = 1;
  438.     k *= isNeg ? -1 : 1;
  439. }
  440. void ReadMonomial(char* &pos, int &k, int &pow) {
  441.     if (isEnd(pos)) return;
  442.     // <Одночлен> ::= {<Коэффициент>}x{<Степень>}
  443.     ReadKoef(pos,k);
  444.     if (*pos == 'x') {
  445.         pos++; // x;
  446.         ReadPower(pos,pow);
  447.     }
  448.     else
  449.         pow = 0;
  450. }
  451. void ReadPolynom(char* &pos, polynom &p) {
  452.  // <Многочлен> ::= <Одночлен> {("+"|"-") <Одночлен>}
  453.     do
  454.     {
  455.         int k, pow;
  456.         ReadMonomial(pos, k, pow);
  457.         p[pow] += k;
  458.  
  459.     } while (!isEnd(pos) && isPlusOrMinus(pos));
  460.  
  461. }
  462. void input(polynom &a, polynom &b) {
  463.     string str;
  464.     cin>>str;
  465.     char *buf = (char*)str.c_str();
  466.     ReadPolynom(buf,a);
  467.    
  468.     cin>>str;
  469.     buf = (char*)str.c_str();
  470.     ReadPolynom(buf,b);
  471.  
  472. }
  473. void mul(const polynom &a, const polynom &b, polynom &res) {
  474.     for (int i=0; i < MAX_POW; i++) {
  475.         for (int j=0; j<MAX_POW; j++) {
  476.             if (i+j < MAX_POW)
  477.                 res[i+j] += a[i] * b[j];
  478.         }
  479.     }
  480. }
  481. void output (const polynom &p) {
  482.     bool isEmpty = true;
  483.     for (int i=0;i<p.size();i++) isEmpty &= !p[i];
  484.     if (isEmpty) {
  485.         cout<<0;
  486.         return;
  487.     }
  488.     bool isFirst = true;
  489.     for (int i=MAX_POW-1;i>=0;i--) {
  490.         if (p[i]) {
  491.             if (!isFirst && p[i] > 0) cout<<"+";
  492.  
  493.             if (i == 0) {
  494.                 cout<<p[i];
  495.             }else {
  496.                 if (p[i] == -1)
  497.                     cout<<"-";
  498.                 else if (p[i] != 1)
  499.                     cout<<p[i];
  500.             }
  501.  
  502.             if (i != 0)
  503.                 cout<<"x";
  504.             if (i > 1)
  505.                 cout<<"^"<<i;
  506.  
  507.             if (isFirst) isFirst = !isFirst;
  508.         }
  509.     }
  510. }
  511. int main() {
  512.     freopen("input.txt","r",stdin);
  513.     freopen("output.txt","w",stdout);
  514.  
  515.     polynom a(MAX_POW), b(MAX_POW), res(MAX_POW);
  516.     input(a,b);
  517.     mul(a,b,res);
  518.     output(res);
  519.     return 0;
  520. }


Editing is locked.