Paste will expire never.
- // Меньшиков. Тренировка 13.
- // 13A. Двойная решетка [dlattice]
- // ibelyaev: 06Jan2011
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <set>
- using namespace std;
- int x1,y1,x2,y2,dx,dy;
- void input()
- {
- cin>>x1>>y1>>x2>>y2>>dx>>dy;
- }
- int gcd(int a, int b)
- {
- return b ? gcd(b, a%b) : a;
- }
- int lcm(int a, int b)
- {
- return (a*b)/gcd(a,b);
- }
- void output(set<int> &S)
- {
- printf("%d\n",S.size());
- for (set<int>::iterator it = S.begin(); it != S.end(); it++)
- printf("%d\n",*it);
- }
- void solve()
- {
- int maxX = dx + lcm(x1, x2);
- int maxY = dy + lcm(y1, y2);
- vector<int> X, Y;
- set<int> S;
- for (int x = 0; x<=maxX; x+=x1)
- X.push_back(x);
- for (int x = dx; x<=maxX; x+= x2)
- X.push_back(x);
- for (int y = 0; y<=maxY; y+=y1)
- Y.push_back(y);
- for (int y = dy; y<=maxY; y+=y2)
- Y.push_back(y);
- sort(X.begin(), X.end());
- sort(Y.begin(), Y.end());
- int dx, dy;
- for (int i = 0; i < X.size()-1; i++) {
- for (int j = 0; j < Y.size()- 1; j++) {
- dx = X[i+1] - X[i];
- dy = Y[j+1] - Y[j];
- S.insert(dx*dy);
- }
- }
- S.erase(0);
- output(S);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
- // Меньшиков. Тренировка 13.
- // 13B. Последовательность Фибоначчи [fiboseq]
- // Бинарный поиск
- // ibelyaev: 06Jan2011
- #include <iostream>
- #include <cstdio>
- #include <stdlib.h>
- using namespace std;
- int n,i,j;
- long long Fi,Fj;
- void input()
- {
- cin>>i>>Fi>>j>>Fj>>n;
- }
- // F[i] F[i+1]
- long long Fib(long long prev, long long cur, int n)
- {
- // forward
- if (n > i) {
- for (int pos = i + 2; pos <= n; pos++) {
- prev += cur;
- swap(cur, prev);
- }
- return cur;
- }
- // back
- else {
- for (int pos = i - 1; pos>=n; pos--) {
- cur -= prev;
- swap(cur, prev);
- }
- return prev;
- }
- }
- void solve()
- {
- if (n == i) { cout<<Fi; return; }
- if (n == j) { cout<<Fj; return; }
- if (i > j) {
- swap(i,j);
- swap(Fi,Fj);
- }
- if (j == i + 1)
- {
- cout<<Fib(Fi,Fj,n);
- return;
- }
- long long l = -2e9 - 10, r = 2e9 + 10;
- while (l<=r)
- {
- long long FiNxt = (l+r)/2;
- long long FjPos = Fib(Fi,FiNxt, j);
- if (FjPos < Fj)
- l = FiNxt + 1;
- else if (FjPos > Fj)
- r = FiNxt - 1;
- else {
- cout<<Fib(Fi,FiNxt,n);
- return;
- }
- }
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
- // Меньшиков. Тренировка 13.
- // 13B. Последовательность Фибоначчи [fiboseq]
- // По формуле + выкладки
- // ibelyaev: 06Jan2011
- #include <iostream>
- #include <cstdio>
- #include <stdlib.h>
- using namespace std;
- int n,i,j;
- long long Fi,Fj;
- void input()
- {
- cin>>i>>Fi>>j>>Fj>>n;
- }
- long long Fib(int n)
- {
- long long prev = 1, cur = 1;
- for (int i = 2; i<=n; i++)
- {
- prev += cur;
- swap(cur, prev);
- }
- return cur;
- }
- // F[i] F[i+1]
- long long Fib(long long prev, long long cur, int n)
- {
- // forward
- if (n > i) {
- for (int pos = i + 2; pos <= n; pos++) {
- prev += cur;
- swap(cur, prev);
- }
- return cur;
- }
- // back
- else {
- for (int pos = i - 1; pos>=n; pos--) {
- cur -= prev;
- swap(cur, prev);
- }
- return prev;
- }
- }
- void solve()
- {
- if (n == i) { cout<<Fi; return; }
- if (n == j) { cout<<Fj; return; }
- if (i > j) {
- swap(i,j);
- swap(Fi,Fj);
- }
- // A(i) = 1 * A(i) + 0 * A(i+1)
- // A(i+1) = 0 * A(i) + 1 * A(i+1)
- // A(i+2) = 1 * A(i) + 1 * A(i+1)
- // A(i+3) = 1 * A(i) + 2 * A(i+1)
- // A(i+4) = 2 * A(i) + 3 * A(i+1)
- // A(i+5) = 3 * A(i) + 5 * A(i+1)
- // A(i+6) = 5 * A(i) + 8 * A(i+1)
- // F(0) = 1
- // F(1) = 1
- // F(2) = 2
- // F(3) = 3
- // F(4) = 5
- // F(5) = 8
- // A(i+x) = F(x-2) * A(i) + F(x-1) * A(i+1)
- // i + x = j
- // A(j) = F(j-i-2) * A(i) + F(j-i-1) * A(i+1);
- // A(i+1) = [A(j) - F(j-i-2) * A(i)] / F(j-i-1);
- // FiNxt = A(i+1);
- int k = j - i;
- long long FiNxt;
- if (k == 1)
- FiNxt = Fj;
- else
- FiNxt = (Fj - Fib(k-2) * Fi) / Fib(k-1);
- cout<<Fib(Fi, FiNxt, n);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
- // Меньшиков. Тренировка 13.
- // 13С. Скобки(3) [bracket3]
- // ibelyaev: 06Jan2011
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <vector>
- using namespace std;
- const int MAX_VALUE = 1e9;
- int n;
- string str;
- vector<vector<int> > mas;
- void input()
- {
- cin>>str;
- n = str.size();
- mas = vector<vector<int> >(n,vector<int>(n,0));
- }
- string open = "([";
- string clos = ")]";
- bool isPair(char f, char s)
- {
- int posF = open.find(f);
- int posS = clos.find(s);
- return posF == posS && posF != -1;
- }
- string Pair(char one)
- {
- int pos = open.find(one);
- if (pos == -1)
- pos = clos.find(one);
- return string(&open[pos],1) + string(&clos[pos],1);
- }
- string getAnswer(int l, int r)
- {
- if (l > r) return "";
- if (l == r)
- return Pair(str[l]);
- int border = (isPair(str[l],str[r]) ? mas[l+1][r-1] : MAX_VALUE);
- if (border == mas[l][r])
- return str[l] + getAnswer(l+1,r-1) + str[r];
- for (int m = l; m < r; m++)
- {
- if (mas[l][m] + mas[m+1][r] == mas[l][r])
- return getAnswer(l,m) + getAnswer(m+1,r);
- }
- }
- void solve()
- {
- for (int i=0;i<n;i++)
- mas[i][i] = 1;
- for (int len = 1; len < n; len++) {
- for (int i=0;i<n;i++) {
- int j = i + len;
- if (j>=n) break;
- int curLen = MAX_VALUE;
- if (isPair(str[i],str[j]))
- curLen = mas[i+1][j-1];
- for (int m = i; m < j; m++)
- curLen = min(curLen, mas[i][m] + mas[m+1][j]);
- mas[i][j] = curLen;
- }
- }
- string answer = "";
- answer = getAnswer(0,n-1);
- cout<<answer;
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
- // Меньшиков. Тренировка 13.
- // 13D. Центр тяжести [centgrav]
- // ibelyaev: 07Jan2011
- #include <iostream>
- #include <cstdio>
- #include <vector>
- using namespace std;
- const double eps = 1e-9;
- double _fabs(double a)
- {
- if (a<0) return -a;
- return a;
- }
- bool Equal(double a, double b)
- {
- return _fabs(a-b) <= eps;
- }
- struct point
- {
- double x, y;
- point(){}
- point(double X, double Y)
- {
- x = X;
- y = Y;
- }
- void input()
- {
- cin>>x>>y;
- }
- void output()
- {
- if (Equal(x,0)) x = 0;
- if (Equal(y,0)) y = 0;
- printf("%0.2f %0.2f",x,y);
- }
- };
- int n;
- vector<point> mas;
- void input()
- {
- cin>>n;
- mas.resize(n);
- for (int i=0;i<n;i++)
- mas[i].input();
- }
- double findS(const point &a, const point &b, const point &c)
- {
- return 0.5*(a.x*b.y + b.x*c.y + c.x *a.y - a.y*b.x - b.y*c.x - c.y*a.x);
- }
- void solve()
- {
- double S = 0;
- double midX = 0;
- double midY = 0;
- for (int i=1;i<n-1;i++)
- {
- double curS = findS(mas[0], mas[i], mas[i+1]);
- S += curS;
- midX += curS * (mas[0].x + mas[i].x + mas[i+1].x) / 3;
- midY += curS * (mas[0].y + mas[i].y + mas[i+1].y) / 3;
- }
- point center(midX/S, midY/S);
- center.output();
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
- // Меньшиков. Тренировка 13.
- // 13E. Сумма произведений [prodsum]
- // O(N) по авторскому разбору
- // ibelyaev: 07Jan2011
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- int n,s;
- void input()
- {
- cin>>n>>s;
- }
- int amount;
- double eps = 1e-9;
- void solve()
- {
- // z = 0 amount
- // p = +1 amount
- // m = -1 amount
- int p;
- for (int z = 0; z<=n; z++)
- {
- int k = n - z;
- int a = 4;
- int b = -4*k;
- int c = k*k - k - 2*s;
- int d = b*b - 4*a*c;
- if (d<0) continue;
- int sqrtD = sqrt((double)d) + eps;
- if (sqrtD * sqrtD == d)
- {
- if ((-b + sqrtD) % (2*a) == 0){
- p = (- b + sqrtD) / (2*a);
- if (0<=p && z+p <= n){
- amount++;
- continue;
- }
- }
- if ((-b - sqrtD) % (2*a) == 0){
- p = (- b - sqrtD) / (2*a);
- if (0<=p && z+p <= n){
- amount++;
- continue;
- }
- }
- }
- }
- cout<<amount;
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
- // Меньшиков. Тренировка 13.
- // 13E. Сумма произведений [prodsum]
- // O(N*N)
- // ibelyaev: 07Jan2011
- #include <iostream>
- #include <cstdio>
- using namespace std;
- int n,s;
- void input()
- {
- cin>>n>>s;
- }
- int F(int n)
- {
- return n*(n-1)>>1;
- }
- void solve()
- {
- int amount = 0;
- for (int nz = 0; nz<=n; nz++)
- {
- for (int minus = 0; minus<=nz; minus++)
- {
- int plus = nz - minus;
- if (F(minus) + F(plus) - plus*minus == s)
- {
- amount++;
- // break нужен для того, чтобы не считать
- // одинаковые комбинации, содержащие
- // одинаковое количество нулей
- break;
- }
- }
- }
- cout<<amount;
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- return 0;
- }
- // Меньшиков. Тренировка 13.
- // 13F. Статическая сложность [icomplex]
- // ibelyaev: 07Jan2011
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <string.h>
- using namespace std;
- const int MAX_SIZE = 2048 + 10;
- const int MAX_STEPS = 12;
- int n;
- typedef vector<int> algoComplex;
- void ReadOperatorsList(char* &pos, algoComplex &totalAC);
- void output(algoComplex &ac, int num)
- {
- printf("Program #%d\n",num);
- printf("Runtime = ");
- bool isFirst = true;
- bool isEmpty = true;
- for (int i = MAX_STEPS-1; i>=0; i--) {
- int mul = ac[i];
- if (mul){
- isEmpty = false;
- if (isFirst)
- isFirst = false;
- else
- cout<<"+";
- if (mul != 1 || (mul == 1 && i ==0))
- cout<<mul;
- if (i != 0){
- if (mul != 1) cout<<"*";
- cout<<"n";
- if (i!=1)
- cout<<"^"<<i;
- }
- }
- }
- if (isEmpty) cout<<0;
- printf("\n\n");
- }
- inline bool _isEnd(const char* pos)
- {
- return *pos == 0;
- }
- inline void _SkipSeps(char* &pos)
- {
- if (_isEnd(pos)) return;
- while (!_isEnd(pos) && *pos == ' ')
- pos++;
- }
- inline bool _isLoopBegin(const char* pos)
- {
- if (_isEnd(pos)) return false;
- return *pos == 'L';
- }
- inline bool _isOpBegin(const char* pos)
- {
- if (_isEnd(pos)) return false;
- return *pos == 'O';
- }
- inline bool _isOperatorBegin(const char* pos)
- {
- return _isLoopBegin(pos) || _isOpBegin(pos);
- }
- inline bool _isDigit(const char pos)
- {
- return '0' <= pos && pos <= '9';
- }
- inline void ReadLex(char* &pos, int len)
- {
- for (int i=0;i<len;i++)
- pos++;
- }
- void ReadNumber(char* &pos, int &number)
- {
- if (*pos == 'n') {
- pos++;
- number = -1;
- return;
- }
- while (_isDigit(*pos)) {
- number = number*10 + *pos - '0';
- pos++;
- }
- }
- void ReadOperatorLoop(char* &pos, algoComplex &listAC)
- {
- //<Оператор LOOP> ::= <Заголовок LOOP> <Список операторов> "END"
- //<Заголовок LOOP> ::= "LOOP" <число> | "LOOP n"
- ReadLex(pos, strlen("LOOP"));
- int loopNumber = 0;
- _SkipSeps(pos);
- ReadNumber(pos, loopNumber);
- _SkipSeps(pos);
- algoComplex loopAC(MAX_STEPS);
- bool isIns = false;
- while (_isOperatorBegin(pos)) {
- isIns = true;
- _SkipSeps(pos);
- ReadOperatorsList(pos,loopAC);
- _SkipSeps(pos);
- }
- if (isIns) {
- if (loopNumber != -1) { // !=n
- for (int i=0;i<MAX_STEPS;i++)
- loopAC[i] *= loopNumber;
- }
- else {
- for (int i=MAX_STEPS-2;i>=0;i--)
- {
- loopAC[i+1] = loopAC[i];
- loopAC[i] = 0;
- }
- }
- }
- else {
- if (loopNumber != -1) // !=n
- loopAC[0] = loopNumber;
- else
- loopAC[1]++;
- }
- for (int i=0;i<MAX_STEPS;i++)
- listAC[i] += loopAC[i];
- _SkipSeps(pos);
- ReadLex(pos,strlen("END"));
- }
- void ReadOperatorOp(char* &pos, algoComplex & listAC)
- {
- //<Оператор OP> ::= "OP" <число>
- ReadLex(pos, strlen("OP"));
- _SkipSeps(pos);
- int opNumber = 0;
- ReadNumber(pos, opNumber);
- if (opNumber != -1) // !=n
- listAC[0] += opNumber;
- else
- listAC[1]++;
- }
- void ReadOperator(char* &pos, algoComplex &curAC)
- {
- //<Оператор> ::= <Оператор LOOP> | <Оператор OP>
- if (_isLoopBegin(pos))
- ReadOperatorLoop(pos, curAC);
- else
- ReadOperatorOp(pos, curAC);
- }
- void ReadOperatorsList(char* &pos, algoComplex &totalAC)
- {
- //<Список операторов> ::= <Оператор> | <Оператор> <Список операторов>
- do
- {
- _SkipSeps(pos);
- algoComplex curAC(MAX_STEPS);
- ReadOperator(pos, curAC);
- for (int i=0;i<MAX_STEPS;i++)
- totalAC[i] += curAC[i];
- _SkipSeps(pos);
- }
- while (_isOperatorBegin(pos));
- }
- void ReadProgram(char* &pos, algoComplex &ac)
- {
- // <Программа> ::= "BEGIN" <Список операторов> "END"
- _SkipSeps(pos);
- ReadLex(pos, strlen("BEGIN"));
- ReadOperatorsList(pos, ac);
- _SkipSeps(pos);
- ReadLex(pos, strlen("END"));
- }
- void input()
- {
- cin>>n;
- string allPrograms = "";
- char buf[MAX_SIZE];
- while (cin.getline(buf,MAX_SIZE)) {
- allPrograms += string(buf);
- allPrograms += " ";
- }
- algoComplex progAC(MAX_STEPS);
- char *str = new char[allPrograms.size()];
- strcpy(str, allPrograms.c_str());
- char *pos = str;
- for (int i=0;i<n;i++)
- {
- progAC.assign(MAX_STEPS,0);
- ReadProgram(pos, progAC);
- output(progAC, i+1);
- }
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- return 0;
- }
Editing is locked.