// Меньшиков. Тренировка 3. // 3A. Разложение на простые множители [pfactor] // ibelyaev: 28Feb2010 #include <iostream> #include <vector> #include <cmath> using namespace std; int n; vector<int> muls; void FindAllSumMul() { int curMul = 2; int sqrt_N = sqrt((double)n); while (curMul<=sqrt_N) { while (n % curMul == 0) { muls.push_back(curMul); n /= curMul; } curMul++; sqrt_N = sqrt((double)n); } if (n!=1) muls.push_back(n); } void output() { cout<<muls[0]; for (int i=1;i<muls.size();i++) cout<<'*'<<muls[i]; } int main() { cin>>n; FindAllSumMul(); output(); return 0; } // Меньшиков. Тренировка 3. // 3B. Перестановки (2) [permut2] // Рекурсивная реализация с подсчетом элементов // ibelyaev: 28Feb2010 #include <iostream> #include <string> #include <vector> using namespace std; string letters,perm; vector<int> amounts; int n; void input() { string str; cin>>str; n = str.size(); for (int i =0;i<str.size();i++) { bool isExist = false; for (int j = 0;j<letters.size();j++) { if (letters[j] == str[i]) { amounts[j]++; isExist = true; } } if (!isExist) { letters.push_back(str[i]); amounts.push_back(1); } } } void output() { //[cout - 0.2 c,printf 0.02 c] cout<<perm<<endl; } void rec(int pos) { if (pos == n) output(); for (int i=0;i<letters.size();i++) { if (amounts[i]) { perm[pos] = letters[i]; amounts[i]--; rec(pos+1); amounts[i]++; perm[pos] = '*'; // for debug only } } } void solve() { perm = string(n,'*'); rec(0); } int main() { input(); solve(); return 0; } // Меньшиков. Тренировка 3. // 3B. Перестановки (2) [permut2] // Решение идентично 2B по принципу next_permutation // ibelyaev: 02Mar2010 #include <iostream> #include <string> #include <algorithm> using namespace std; string str; void input() { cin>>str; } bool next_permutation(string &str) { // находим элемент меньше или равного последующему int pos = -1; for (int i=str.size()-2;i>=0;i--) if (str[i] < str[i+1]) { pos = i; break; } if (pos == -1) return false; // текущая перестановка последняя в лексикографическом порядке // находим минимальный элемент превышающий найденый char value = str[pos]; int swapIndex = -1; for (int i=str.size()-1;i>=pos;i--) if (str[i]>value) { swapIndex = i; break; } swap(str[pos],str[swapIndex]); //реверс подстроки правее индекса pos int f = pos+1, s = str.size()-1; while (f<s) swap(str[f++],str[s--]); return true; } void solve() { sort(str.begin(),str.end()); cout<<str<<endl; while (next_permutation(str)) cout<<str<<endl; } int main() { input(); solve(); return 0; } // Меньшиков. Тренировка 3. // 3C. Копилка [piggy] // ibelyaev: 02Mar2010 #include <iostream> #include <vector> #include <limits.h> using namespace std; vector<int> P,W; int n; int E,F; vector<int> MAX, MIN; void input() { cin>>E>>F; cin>>n; MAX = vector<int>(F - E + 1,INT_MIN); MIN = vector<int>(F - E + 1,INT_MAX); P.resize(n); W.resize(n); for (int i=0;i<n;i++) cin>>P[i]>>W[i]; } void solve() { MIN[0] = 0; MAX[0] = 0; for (int i = 0;i<MIN.size();i++) { for (int j=0;j<W.size();j++) { if (i - W[j]>=0 && MIN[i-W[j]]!=INT_MAX) { MIN[i] = min(MIN[i],MIN[i-W[j]] + P[j]); MAX[i] = max(MAX[i],MAX[i-W[j]] + P[j]); } } } } void output() { if (MIN.back()==INT_MAX) cout<<"This is impossible."; else cout<<MIN.back()<<' '<<MAX.back(); } int main() { input(); solve(); output(); return 0; } // Меньшиков. Тренировка 3. // 3D. Открытка и конверт [postcard] // ibelyaev: 02Mar2010 #include <iostream> #include <cmath> using namespace std; double pi = 2*acos(0.0); int h,w,H,W; void input() { cin>>h>>w; cin>>H>>W; } double Fabs(double a) { if (a<0) return -a; return a; } double eps = 1e-9; bool Equal(double a, double b) { return Fabs(a-b) <= eps; } bool LessEqual(double a, double b) { return a<b || Equal(a,b); } bool isInside(int w, int h, int W, int H) { if (h>w) swap(h,w); if (H>W) swap(H,W); // тривиальный случай if (h<=H && w<=W) return true; else // Под углом { double beta = acos((double)H / sqrt((double)(h*h + w*w))); double phi = acos((double)W / sqrt((double)(h*h + w*w))); double alpha = 2* atan((double)h/(double)w); double Alpha = pi/2 - beta - phi; return LessEqual(alpha,Alpha); } } void solve() { if (isInside(w,h,W,H)) cout<<"Possible"; else cout<<"Impossible"; } int main() { input(); solve(); return 0; } // Меньшиков. Тренировка 3. // 3E. Длинное произведение [longprod] // ibelyaev: 02Mar2010 #include <iostream> #include <string> #include <cstring> using namespace std; const int max_len = 5100; struct BigInt { int digits[max_len]; int amount; BigInt() { memset(digits,0,sizeof(digits)); amount = 1; } void init(string &str) { memset(digits,0,sizeof(digits)); amount = str.size(); int pos = 0; for (int i=amount-1;i>=0;i--) digits[pos++] = str[i] - '0'; } void input() { string str; cin>>str; init(str); } void output() { for (int i=amount-1;i>=0;i--) cout<<digits[i]; } }; int osn = 10; BigInt operator * (const BigInt &a, const BigInt &b) { BigInt res; int r = 0; for (int i=0;i<a.amount;i++){ for (int j=0;j<b.amount | r;j++) { res.digits[i+j] += a.digits[i]*b.digits[j]+r; r = res.digits[i+j]/osn; res.digits[i+j] -= r * osn; } } int pos = a.amount + b.amount; while (pos>0 && !res.digits[pos]) pos--; res.amount = pos + 1; return res; } int main() { BigInt a,b,res; a.input(); b.input(); res = a*b; res.output(); return 0; } // Меньшиков. Тренировка 3. // 3F. Змейка [serpent] // ibelyaev: 02Mar2010 #include <iostream> #include <vector> using namespace std; vector<vector<int> > mas; int n; void input() { cin>>n; mas = vector<vector<int> >(n,vector<int>(n,0)); } void solve() { int cur = 1, j,f,s; for (int c = 0;c<2*n-1;c++) { if (c-n+1 < 0) { f = 0; s = c; } else { f = c-n+1; s = c - f; } if (c&1) { for (int i=f;i<=s;i++) { j = c - i; mas[i][j] = cur++; } } else { for (int i=s;i>=f;i--) { j = c - i; mas[i][j] = cur++; } } } } void output() { for (int i=0;i<n;i++) { for (int j=0;j<n;j++) { cout<<mas[i][j]<<' '; } cout<<endl; } } int main() { input(); solve(); output(); return 0; } // Меньшиков. Тренировка 3. // 3F. Змейка [serpent] // ibelyaev: 15May2010 #include <iostream> #include <vector> using namespace std; vector<vector<int> > mas; int n; bool correct(int x, int y) { if (x<0 || y<0) return false; if (x>=n || y>=n) return false; return true; } void input() { cin>>n; mas = vector<vector<int> >(n,vector<int>(n,0)); } void solve() { int pos = 1; for (int c = 0; c<2*n; c++) { if (c%2) { for (int i=0;i<n;i++) { int j = c - i; if (correct(i,j)) mas[i][j] = pos++; } } else { for (int i=n-1;i>=0;i--) { int j = c - i; if (correct(i,j)) mas[i][j] = pos++; } } } } void output() { for (int i=0;i<n;i++) { for (int j=0;j<n;j++) cout<<mas[i][j]<<' '; cout<<endl; } } int main() { input(); solve(); output(); return 0; }