|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <stdio.h> #include <iostream> using namespace std; int main() { int n,a,b,c,d,aa,bb,ans,t; cin>>t; while(t--) { cin>>a>>b>>c>>d; aa=a-c-1; bb=b-d-1; ans=aa^bb^c^d; if(ans==0) cout<<"Hansel\n"; else cout<<"Gretel\n"; } return 0; } |
Nim game: It is an ancient game.Charles Boute discovered the trick behind the game strategy to win obviously. The idea is to figure out the current state of the stones of all the piles. If it is in the zero state then there is no way we can make a move to put the state
|
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 |
#include <iostream> #include <cstdio> using namespace std; int arr[25000]; struct path{ int len,st,en; }; path p; int kadanesAlgo(int rd,int first) { int max_end_here=0,max_so_far=0; int begin=first,length; int finish=0,start=first; for(int i=first;i<rd;i++) { max_end_here+=arr[i]; if(max_end_here<0) { max_end_here=0; begin=i+1; } if(max_end_here>max_so_far) { max_so_far = max_end_here; start=begin; finish=i+1; length=finish-start+1; p.len=length; p.en=finish; p.st=start; } else if(max_end_here==max_so_far) { max_so_far = max_end_here; start=begin; finish=i+1; length=finish-start+1; if(length>p.len) { p.len=length; p.en=finish; p.st=start; } else if(length==p.len) { if(p.st>begin) { p.st=begin;p.en=finish; } } } } return max_so_far; } int main() { int t,kase=1; int rd,res; int first; cin>>t; bool f=0; while(t--) { cin>>rd; f=0; for(int i=1;i<rd;i++) { cin>>arr[i]; if(!f) { if(arr[i]>0) { first=i; f=1; } } } p.en=0;p.st=0;p.len=-1; res = kadanesAlgo(rd,first); if(res) cout<<"The nicest part of route "<<kase++<<" is between stops "<<p.st<<" and "<<p.en<<"\n"; else cout<<"Route "<<kase++<<" has no nice parts\n"; } return 0; } |
Golbach’s Conjecture: Any even number can be expressed as a summation of two prime numbers. This idea is used to solve the problem. if the number is odd then .ie 49 thn 2,3 and goldbach conjechture of (49-5) can be expressed as sum of 2 primes. if the number is even then 2,2 and goldbach
Theory: Perfect square problem.Problem is to determine a pair of numbers where the small (lower_num) number divides the numbers from 1 up to higher_num into two groups in a way that summation of 1 to (lower_num-1) is equal to summation of the numbers from (lower_num+1) to higher_num. Expanation: first pair 6 8 summation of 1
|
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 |
#include <iostream> #include <cstdio> #include <cmath> #include <vector> using namespace std; int n; int arr[1300000]; vector<int> v; int main() { int lo,hi,mid; for(int i=0;i<1300000;i++) { arr[i]=0; } for(int i=2;i<sqrt(1300000);i++) { if(arr[i]==0) { for(int j=i+i;j<1300000;j+=i) { arr[j]=1; } } } for(int i=2;i<1300000;i++) { if(arr[i]==0) { v.push_back(i); } } //cout<<v.size()<<"\n"; while(scanf("%d",&n),n) { if(arr[n]==0) { cout<<0<<"\n"; continue; } lo=0;hi=v.size()-1; while(hi-lo>1) { if((hi-lo)%2) { mid=lo+(hi-lo)/2+1; } else mid=lo+(hi-lo)/2; //cout<<lo<<" "<<mid<<" "<<hi<<" "<<n<<"\n"; //getchar(); if(n<v[mid]) { hi=mid; } else { lo=mid; } } cout<<v[hi]-v[lo]<<"\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 |
#include <iostream> #include <cstdio> #include <sstream> #include <string> using namespace std; int n; string str; int main() { int t; cin>>t; while(t--) { cin>>n; cin>>str; int i=0,j=1,k; while(i<n && j<n) { for(k=0;k<n;k++) { if(str[(k+i)%n]!=str[(k+j)%n]) break; } if(k==n) break; if(str[(k+i)%n]>str[(k+j)%n]) i=i+k+1; else if(str[(k+i)%n]<str[(k+j)%n]) j=j+k+1; if(i==j) j+=1; } cout<<((i>j)?j:i)<<"\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 |
#include <iostream> using namespace std; int arr[105][105]; int s; int Matsum(int a,int b) { int p; int Line[105]; int max_end_here,max_so_far; for(int i=1;i<=s;i++) { p=0; for(int j=a;j<=b;j++) { p+=arr[j][i]; } Line[i]=p; } max_end_here=0; max_so_far=0; for(int i=1;i<=s;i++) { max_end_here+=Line[i]; if(max_end_here<0) max_end_here=0; if(max_end_here>max_so_far) max_so_far=max_end_here; } return max_so_far; } int main() { int t,mx,m; int b,r1,r2,c1,c2; cin>>t; while(t--) { cin>>s; cin>>b; mx =0; for(int i=0;i<=101;i++) for(int j=0;j<=101;j++) arr[i][j]=1; while(b--) { cin>>r1>>c1>>r2>>c2; for(int i=r1;i<=r2;i++) { for(int j=c1;j<=c2;j++) arr[i][j]=-10000000; } } for(int i=1;i<=s;i++) for(int j=1;j<=s;j++) { m = Matsum(i,j); if(mx<m) mx=m; } cout<<mx<<"\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 |
#include <iostream> using namespace std; int arr[105][105]; int M,N; int Matsum(int a,int b) { int p,max_end_here=0,max_so_far=0; int Line[105]; for(int i=1;i<=N;i++) { p = 0; for(int j=a;j<=b;j++) { p+=arr[j][i]; } Line[i]=p; } max_end_here=0; max_so_far=0; for(int i=1;i<=N;i++) { max_end_here = max_end_here + Line[i]; if(max_end_here<0) max_end_here = 0; if(max_so_far<max_end_here) max_so_far = max_end_here; } return max_so_far; } int main() { int a; int mx=0,x; while(cin>>M>>N) { if(M==0 && N==0) break; for(int i=1;i<=M;i++) { for(int j=1;j<=N;j++) { cin>>a; if(a==0) arr[i][j]=1; //a = -1; if(a) arr[i][j]=-1000000;//a[i-1][j]+a; } } mx = 0; for(int i=1;i<=M;i++) { for(int j=i;j<=M;j++) { x = Matsum(i,j); if(x>mx) mx=x; } } cout<<mx<<"\n"; }//end while 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 |
#include <stdio.h> int a[100][100]={0}; int N; int Line[100]; int KadaneAlg(); int MatSum(int a,int b); int main() { int p=-100; int Max=-100; while(scanf("%d",&N)==1) { Max=-100; p =-100; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) scanf("%d",&a[i][j]); } for(int k=0;k<N;k++) { for(int l=k;l<N;l++) { p = MatSum(k,l); if(p>Max) Max = p; } } printf("%d\n",Max); } return 0; } int MatSum(int c,int b) { int p; for(int i=0;i<N;i++) { p =0; for(int j=c;j<=b;j++)//row { p += a[j][i]; } Line[i] = p; } return KadaneAlg(); } int KadaneAlg() { int max_so_far = 0, max_ending_here = 0; int i; for(i = 0; i < N; i++) { max_ending_here = max_ending_here + Line[i]; if(max_ending_here < 0) max_ending_here = 0; else if (max_so_far < max_ending_here) max_so_far = max_ending_here; } return max_so_far; } |