PKU 1082 Calendar Game
http://poj.org/problem?id=1082
1900年1月1日から2001年11月4日までの日付が入力される。
ここでadamとeveはゲームをする。先攻はadamで、次のような手が打てる。
もし、入力された月だけを一つ進めた時に、それがカレンダーの日付として存在して2001年11月4日を超えていなければ月を一つすすめることが出来る。
もしくは日を一つだけ進めて2001年11月4日を超えていなければ日を一つすすめることが出来る。
打てる手が無くなったほうが負ける。
このときに与えられた日付において、adamが勝利するかどうかを判定しろというような問題。
ゲーム木探索。
ソースコードが汚くすぎてとおるか不安だったけれど大丈夫だった。
カレンダー系は面倒くさい問題が多い気がしますね。
int ans[110][13][40]; int mo[]={31,28,31,30,31,30,31,31,30,31,30,31}; int st; bool ga(int y,int m,int d){ if(ans[y-1900][m][d])return ans[y-1900][m][d]-1; if(y>2001 || y==2001 && m>11 || y==2001 && m==11 && d>4)return true; int ny=y,nm=m,nd=d; if(nm<12)++nm; else ny++,nm=1; bool isr=((ny%4==0 && ny%100!=0)||ny%400==0)&&nm==2; if(nd<=mo[nm-1]+isr){ if(ga(ny,nm,nd)==false)return (ans[y-1900][m][d]=2)-1; } ny=y,nm=m,nd=d; isr=((y%4==0 && y%100!=0) || ny%400==0 )&& m==2; ++nd; if(nd>mo[nm-1]+isr){ nd=1; ++nm; if(nm==13)nm=1,ny++; } if(ga(ny,nm,nd)==false)return (ans[y-1900][m][d]=2)-1; return (ans[y-1900][m][d]=1)-1; } main(){ int T; cin>>T; while(T--){ int y,m,d; cin>>y>>m>>d; cout<<(ga(y,m,d)?"YES":"NO")<<endl; } }