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
Month: July 2015
10703
|
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 |
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #define INF 1000000 using namespace std; void swp(int *p,int *q) { int tmp; tmp=*p; *p=*q; *q=tmp; } int main() { int h,w,n; int a,b,c,d; bool gr[505][505]; while(cin>>h) { cin>>w>>n; if(h+w+n==0) break; memset(gr,0,sizeof(gr)); int cnt=0; for(int k=0;k<n;k++) { cin>>a>>b>>c>>d; if(a>c) swp(&a,&c); if(b>d) swp(&b,&d); for(int i=a;i<=c;i++) { for(int j=b;j<=d;j++) { if(gr[i][j]==0) { cnt+=1; gr[i][j]=1; } } } } int ans = h*w-cnt; if(ans==0) cout<<"There is no empty spots.\n"; else if(ans==1) cout<<"There is one empty spot.\n"; else cout<<"There are "<<ans<<" empty spots.\n"; } return 0; } |
496
Using set::set_intersect(params) the problem can be solved.
|
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 |
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <algorithm> #include <sstream> #define INF 1000000 using namespace std; set<int> Set1,Set2,inn; int main() { int n; string str; stringstream ss; while(getline(cin,str)) { Set1.clear(); Set2.clear(); inn.clear(); ss.clear(); ss<<str; while(ss>>n) { Set1.insert(n); } getline(cin,str); ss.clear(); ss<<str; while(ss>>n) { Set2.insert(n); } set_intersection(Set1.begin(),Set1.end(),Set2.begin(),Set2.end(),insert_iterator< set<int> >(inn,inn.begin())); if(Set1==Set2) cout<<"A equals B\n"; else if(Set2==inn) cout<<"B is a proper subset of A\n"; else if(Set1==inn) cout<<"A is a proper subset of B\n"; else if(inn.size()==0) cout<<"A and B are disjoint\n"; else cout<<"I'm confused!\n"; } return 0; } |
10771
This is a very problem. Explanation: Elimination continues till there is a single maid remains. If number of keka maids are odd at beginning it never becomes even through the elimination process so it will reach at 1 first. And if the number of keka maids starts with even number it never becomes odd according
11565
|
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 |
#include <iostream> #include <cmath> #include <cstdio> #include <vector> #include <algorithm> using namespace std; vector<int> vb; int main() { int t; int A,B,C; cin>>t; while(t--) { cin>>A>>B>>C; bool found=0; vb.clear(); for(int i=-100;i<=100;i++) { for(int j=-100;j<=100;j++) { for(int k=-100;k<=100;k++) { if(i+j+k==A) if(i*j*k==B) if(i*i+j*j+k*k==C) if(i!=j && i!=k && j!=k) { vb.push_back(i);vb.push_back(j);vb.push_back(k); found=1; i=101;j=101;k=101; } } } } if(found) { sort(vb.begin(),vb.end()); cout<<vb[0]<<" "<<vb[1]<<" "<<vb[2]<<"\n"; } else cout<<"No solution.\n"; } return 0; } |
10773
This one is also a shitty problem, had to try and error to get accepted, do not know why it got AC.
|
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> #include <cmath> #include <cstdio> const double eps = 1e-6; using namespace std; int main() { int t,kase=1; double d,v,u; double x; cin>>t; while(t--) { cin>>d>>v>>u; printf("Case %d: ", kase++); if(u-v<eps || u<eps || v<eps) { printf("can't determine\n"); } else { x=sqrt(u*u-v*v); printf("%.3lf\n", d/x - d/u); } } return 0; } |
11588
|
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 |
#include <iostream> #include <cstdio> #include <sstream> #include <string> #include <cstring> using namespace std; int arr[27]; int main() { int t,ans; int kase=1; char ch; int R,C,M,N; cin>>t; while(t--) { cin>>R>>C>>M>>N; memset(arr,0,sizeof(arr)); for(int i=0;i<R*C;i++) { cin>>ch; arr[ch-'A']+=1; } int mx=-1; for(int i=0;i<26;i++) { if(arr[i]>mx) mx=arr[i]; } int cnt=0; for(int i=0;i<26;i++) { if(arr[i]==mx) cnt+=1; } ans=mx*cnt*M+(R*C-mx*cnt)*N; cout<<"Case "<<kase++<<": "<<ans<<"\n"; } return 0; } |
11687
|
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 <cstdio> #include <sstream> #include <string> using namespace std; int main() { int n,cnt; string s,t; stringstream ss; while(cin>>s) { if(s=="END") break; n=s.size(); cnt=1; ss.clear(); ss<<n; ss>>t; while(s!=t) { s=t; n=s.size(); ss.clear(); ss<<n; ss>>t; cnt+=1; } cout<<cnt<<"\n"; } return 0; } |
11634
|
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 |
#include <iostream> #include <cstring> #include <string> using namespace std; bool trace[10000]; int random(int n) { int a=n*n; int arr[10]; int k=8; while(a) { arr[k]=a%10; k-=1; a/=10; } for(int i=k;i>=1;i--) arr[i]=0; int num=0; for(int i=3;i<=6;i++) { num*=10; num+=arr[i]; } return num; } int main() { int n,k; int cnt; while(cin>>n) { if(n==0) break; memset(trace,0,sizeof(trace)); cnt=1; int num=n; trace[num]=1; while(1) { num=random(num); if(trace[num]==0) { trace[num]=1; cnt+=1; } else break; } cout<<cnt<<"\n"; } return 0; } |
12243
Need to know a little more about string.char an locale library.
|
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 |
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <locale> using namespace std; int main() { string str; locale loc; while(getline(cin,str)) { if(str=="*") break; char ch1; char ch=str[0]; if(isupper(ch,loc)) ch1=tolower(ch,loc); else ch1=toupper(ch,loc); //cout<<ch<<" "<<ch1<<"\n"; bool tautogram=1; for(int i=1;i<str.size();i++) { if(str[i]==' ') { if(i+1<str.size() && str[i+1]!=ch && str[i+1]!=ch1) { //cout<<"error "<<str[i+1]<<"\n"; tautogram=0; i=str.size(); } } } if(tautogram) cout<<"Y\n"; else cout<<"N\n"; } return 0; } |