Fishhead’s Little Game
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 377 Accepted Submission(s): 89
Problem Description
There is a 3 by 3 grid and each vertex is assigned a number.
It looks like JiuGongGe, but they are different, for we are not going to fill the cell but the edge. For instance,
adding edge 6 –> 10
The rule of this game is that each player takes turns to add an edge. You will get one point if the edge you just added, together with edges already added before, forms a new square (only square of size 1 is considered). Of course, you get two points if that edge forms two squares. Notice that an edge can be added only once.
forming two squares to get two points
Tom200 and Jerry404 is playing this little game, and have played n rounds when Fishhead comes in. Fishhead wants to know who will be the winner. Can you help him? Assume that Tom200 and Jerry404 are clever enough to make optimal decisions in each round. Every Game starts from Tom200.
It looks like JiuGongGe, but they are different, for we are not going to fill the cell but the edge. For instance,
adding edge 6 –> 10
The rule of this game is that each player takes turns to add an edge. You will get one point if the edge you just added, together with edges already added before, forms a new square (only square of size 1 is considered). Of course, you get two points if that edge forms two squares. Notice that an edge can be added only once.
forming two squares to get two points
Tom200 and Jerry404 is playing this little game, and have played n rounds when Fishhead comes in. Fishhead wants to know who will be the winner. Can you help him? Assume that Tom200 and Jerry404 are clever enough to make optimal decisions in each round. Every Game starts from Tom200.
Input
The first line of the input contains a single integer T (T <= 100), the number of test cases.
For each case, the first line contains an integers n (12 <= n <= 24), which means they have taken total n rounds in turn. Next n lines each contains two integers a, b (a, b <= 16) representing the two endpoints of the edge.
For each case, the first line contains an integers n (12 <= n <= 24), which means they have taken total n rounds in turn. Next n lines each contains two integers a, b (a, b <= 16) representing the two endpoints of the edge.
Output
For each case output one line "Case #X: ", representing the Xth case, starting from 1. If Tom200 wins, print "Tom200" on one line, print "Jerry404" otherwise.
Sample Input
1
15
1 2
1 5
2 6
5 9
6 10
9 10
5 6
2 3
3 7
7 11
10 11
3 4
6 7
7 8
4 8
Sample Output
Case #1: Tom200
Hint
In case 1, Tom200 gets two points when she add edge 5 -> 6, two points in edge 6 -> 7, one point in 4 -> 8.
Source
Recommend
liuyiding
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; int n,map[30][30],vis[30],dp[1100000]; struct node{ int x,y; }; vector<node> vt; int solve1(int x,int y){ if(x>y) swap(x,y); int x2=x-4, y2=y-4; int ans=0; if(x2>=1 && y2>=1){ if(map[x][y] && map[x][x2] && map[x2][y2] && map[y][y2]) ans++; } x2=x+4, y2=y+4; if(x2<=16 && y2<=17){ if(map[x][y] && map[x][x2] && map[x2][y2] && map[y][y2]) ans++; } return ans; } int solve2(int x,int y){ if(x>y) swap(x,y); int x2=x-1, y2=y-1; int ans=0; if(x2%4!=0 && y2%4!=0 && x2>=1 && y2>=1){ if(map[x][y] && map[x][x2] && map[x2][y2] && map[y][y2]) ans++; } x2=x+1, y2=y+1; if(x%4!=0 && y%4!=0){ if(map[x][y] && map[x][x2] && map[x2][y2] && map[y][y2]) ans++; } return ans; } int DFS(int cur,int score){ if(cur==25 || score==0) return 0; int status=0; for(int i=0;i<(int)vt.size();i++) if(vis[i]) status |= (1<<i); if(dp[status]!=-1) return dp[status]; int maxx=0; for(int i=0;i<(int)vt.size();i++){ if(!vis[i]){ int tmp=0; map[vt[i].x][vt[i].y]=1; map[vt[i].y][vt[i].x]=1; if(abs(vt[i].x-vt[i].y)==1) tmp=solve1(vt[i].x,vt[i].y); else tmp=solve2(vt[i].x,vt[i].y); vis[i]=1; maxx=max(maxx,score-DFS(cur+1,score-tmp)); vis[i]=0; map[vt[i].x][vt[i].y]=0; map[vt[i].y][vt[i].x]=0; } } dp[status]=maxx; return maxx; } int main(){ //freopen("input.txt","r",stdin); int t,cases=0; scanf("%d",&t); while(t--){ int tom=0, jerry=0; vt.clear(); scanf("%d",&n); memset(map,0,sizeof(map)); int x,y,tmp; for(int i=1;i<=n;i++){ scanf("%d%d",&x,&y); map[x][y]=map[y][x]=1; if(abs(x-y)==1){ tmp=solve1(x,y); if(i&1) tom+=tmp; else jerry+=tmp; }else{ tmp=solve2(x,y); if(i&1) tom+=tmp; else jerry+=tmp; } } node edge; for(int i=1;i<=16;i++) for(int j=i+1;j<=16;j++) if(!map[i][j]){ if(j-i==1 && i%4!=0){ edge.x=i; edge.y=j; vt.push_back(edge); }else if(j-i==4){ edge.x=i; edge.y=j; vt.push_back(edge); } } printf("Case #%d: ",++cases); if(tom>=5){ puts("Tom200"); continue; } if(jerry>=5){ puts("Jerry404"); continue; } memset(dp,-1,sizeof(dp)); memset(vis,0,sizeof(vis)); if(n+1<=24){ if((n+1)&1){ tom+=DFS(n+1,9-tom-jerry); jerry=9-tom; }else{ jerry+=DFS(n+1,9-tom-jerry); tom=9-jerry; } } printf("%s\n",(tom>jerry?"Tom200":"Jerry404")); } return 0; }
相关推荐
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
搜索 dfs 解题代码 hdu1241
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu2101AC代码
各种小数化分数的算法,acm的同学都喜欢看,仅供参考!
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
hdu 1166线段树代码
自己做的HDU ACM已经AC的题目
ACM HDU题目分类,我自己总结的大概只有十来个吧
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类