|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> using namespace std; int a[30000005]; int main() { int t,n,c=0; for(int i=1;i<30000005;i++) { for(int j=i<<1;i+j<30000005;j+=i) { if(((i+j)&j)==j) a[i+j]++; } } for(int i=1;i<30000005;i++) a[i]+=a[i-1]; cin>>t; while(t--) { cin>>n; c++; cout<<"Case "<<c<<": "<<a[n]<<"\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <map> using namespace std; map<unsigned long long,int> mp; int main() { unsigned long long z,I,M,L; int c=0; while(cin>>z) { cin>>I>>M>>L; if(z==0 && I==0 && M==0 && L==0) break; c++; mp.clear(); L=((z)*(L)+I)%M; //mp[L]=1; while(mp[L]==0) { mp[L]=1; L=(z*L+I)%M; } cout<<"Case "<<c<<": "; cout<<mp.size()<<"\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
//Extended euclid Algorithm #include <iostream> using namespace std; long long int gcd(long long int a, long long int b) { if(b==0) return a; else return gcd(b,a%b); } int main() { long long int a,b,g,q,temp,t1,t2; while(cin>>a>>b) { //g=gcd(a,b); long long int prevx=1,x=0,y=1,prevy=0; while(b) { q=a/b; t1=x; x=prevx-q*x; prevx=t1; t2=y; y=prevy-q*y; prevy=t2; temp=a; a=b; b=temp%b; } cout<<prevx<<" "<<prevy<<" "<<a<<"\n"; } return 0; } |
Theory: The pseudo code of the extended euclid algorithm: xgcd(a,b): prevx, x = 1, 0; prevy, y = 0, 1 while (b!=0) { q = a/b x = prevx – q*x; prevx= x; y = prevy – q*y; prevy= y; a = b; b= a % b; } return a, prevx, prevy [button color=”red”
Solution:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include <iostream> #include <string> #include <string.h> #include <map> using namespace std; map<string,int> mp; int palin(string s) { int l=s.size()-1; for(int i=0;i<s.size()/2;i++) { if(s[i]!=s[l-i]) return 0; } return 1; } int main() { string s,str; int l,c; while(cin>>s) { l=s.size(); mp.clear(); c=0; for(int i=0;i<l;i++) { for(int j=0;j<l;j++) { str=s.substr(i,l-j); if(mp[str]>=1) continue; if(palin(str)) { mp[str]=1; c++; } } } cout<<"The string "<<"\'"<<s<<"\'"<<" contains "<<c<<" palindromes.\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
//1101110 =110 // //1101010 //1101110 //1101010 #include <iostream> #include <string> #include <string.h> #define MOD 1000000007 using namespace std; unsigned long long x[100001]; unsigned long long y; int main() { int t,l,m,kase=0; int a,b; string str,s; x[0]=1; x[1]=2; for(int i=2;i<100001;i++) x[i]=(x[i-1]*2)%MOD; cin>>t; while(t--) { cin>>str; y=0; s=""; kase++; if(str.size()%2==1) { a=str.size()/2; b=a; } else { b=str.size()/2; a=b-1; } for(int i=0;i<str.size();i++) { if(s.size()==str.size()) break; if(a==b) { s.append(1u,str[a]); l=str.size()-s.size(); y+=((x[l]*(str[a]-'0'))%MOD); y%=MOD; a=a-1; b=b+1; } else { if(str[a]>=str[b]) { s.append(1u,str[a]); l=str.size()-s.size(); y+=((x[l]*(str[a]-'0'))%MOD); y%=MOD; s.append(1u,str[b]); l=str.size()-s.size(); y+=((x[l]*(str[b]-'0'))%MOD); y%=MOD; a--; b++; } else { s.append(1u,str[b]); l=str.size()-s.size(); y+=((x[l]*(str[b]-'0'))%MOD); y%=MOD; s.append(1u,str[a]); l=str.size()-s.size(); y+=((x[l]*(str[a]-'0'))%MOD); y%=MOD; b++; a--; } } } cout<<"Case #"<<kase<<": "; cout<<y<<"\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include <iostream> #include <string.h> #include <string> #include <stdio.h> using namespace std; string a[10]; string b[10]; string c[10]; int main() { a[0]="\\ / "; b[0]=" | "; c[0]="/o\\ "; a[1]=" o "; b[1]="/|\\ "; c[1]="/ \\ "; a[2]=" "; b[2]=" "; c[2]="__\\o"; a[3]=" "; b[3]=" "; c[3]="\\_\\o"; a[4]="_o_ "; b[4]=" | "; c[4]="/ \\ "; a[5]="\\o/ "; b[5]=" | "; c[5]="/ \\ "; a[6]="\\o_ "; b[6]="\\| "; c[6]=" | "; a[7]="\\o/ "; b[7]="\\|/ "; c[7]=" "; a[8]=" "; b[8]=" __o"; c[8]="/ |"; a[9]=" o "; b[9]="( ) "; c[9]="/ \\ "; //cout<<c[0]<<"a"; int t,x,ct=0,org; string str; cin>>t; org=t; while(t--) { cin>>str; ct++; for(int i=0;i<3;i++) { for(int j=0;j<str.size();j++) { x = str[j]-'0'; if(i==0) cout<<a[x]; else if(i==1) cout<<b[x]; else if(i==2) cout<<c[x]; if(j!=(str.size()-1)) cout<<" "; else cout<<"\n"; } //cout<<"\n"; } //if(ct<=org-1) cout<<"\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <iostream> using namespace std; int a[10][10]; int ans1[8]; int ans2[8]; int main() { int N,M,n; a[1][1]=1; a[2][2]=1; a[3][3]=1; a[4][2]=2; a[5][5]=1; a[6][2]=1; a[6][3]=1; a[7][7]=1; a[8][2]=3; a[9][3]=2; for(int i=1;i<=9;i++) { for(int j=1;j<=7;j++) a[i][j]+=a[i-1][j]; } //for(int i=1;i<=9;i++) //cout<<a[9][i]<<" "; while(cin>>N) { cin>>M; if(N==0 && M==0) break; for(int i=1;i<8;i++) { ans1[i]=0; ans2[i]=0; } for(int i=0;i<N;i++) { cin>>n; if(n!=0) for(int j=1;j<=7;j++) ans1[j]+=a[n][j]; } for(int i=0;i<M;i++) { cin>>n; if(n!=0) for(int j=1;j<=7;j++) ans2[j]+=a[n][j]; } int f=0; for(int i=2;i<8;i++) { if(ans1[i]!=ans2[i]) { cout<<"NO\n"; f=1; break; } } if(f==0) cout<<"YES\n"; } return 0; } |
[highlight]Solution:[/highlight]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> using namespace std; int a[10][10]; int ans1[8]; int ans2[8]; int main() { int N,M,n; a[1][1]=1; a[2][2]=1; a[3][3]=1; a[4][2]=2; a[5][5]=1; a[6][2]=1; a[6][3]=1; a[7][7]=1; a[8][2]=3; a[9][3]=2; for(int i=1;i<=9;i++) { for(int j=1;j<=7;j++) a[i][j]+=a[i-1][j]; } //for(int i=1;i<=9;i++) //cout<<a[9][i]<<" "; while(cin>>N) { cin>>M; if(N==0 && M==0) break; for(int i=1;i<8;i++) { ans1[i]=0; ans2[i]=0; } for(int i=0;i<N;i++) { cin>>n; if(n!=0) for(int j=1;j<=7;j++) ans1[j]+=a[n][j]; } for(int i=0;i<M;i++) { cin>>n; if(n!=0) for(int j=1;j<=7;j++) ans2[j]+=a[n][j]; } int f=0; for(int i=2;i<8;i++) { if(ans1[i]!=ans2[i]) { cout<<"NO\n"; f=1; break; } } if(f==0) cout<<"YES\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <stdio.h> using namespace std; int MX; int main() { int n; int L,W,H,V; while(cin>>n) { if(n==0) break; MX=-1; for(int i=0;i<n;i++) { cin>>L>>W>>H; if(H>MX) { MX=H; V=L*W*H; } else if(H==MX) { if(L*W*H>V) V=L*W*H; } } cout<<V<<"\n"; } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <math.h> #include <stdio.h> using namespace std; int main() { int t,x,y,r; cin>>t; while(t--) { cin>>x>>y>>r; double l=sqrt((double)(x*x+y*y)); if(l<0) l*=-1; double a=r-l; if(a<0) a*=-1; double b=r+l; if(b<0) b*=-1; printf("%.2lf %.2lf\n",a,b); } return 0; } |