Hang or not to hang
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 604 | Accepted: 152 |
Description
Little Tom is learning how to program. He has just written some programs but is afraid to run them, because he does not know if they will ever stop. Please write a program to help him. This task is not as easy as it may seem, because Tom's programs are possibly
not deterministic. Given a program written by Tom, your program should tell him whether his program can stop and if so, what is the shortest possible time before it stops.
not deterministic. Given a program written by Tom, your program should tell him whether his program can stop and if so, what is the shortest possible time before it stops.
Tom's computer consists of 32 1-bit registers and the program consists of n instructions. The registers are numbered from 0 to 31 and the instructions are numbered from 0 to n-1.
Below, MEM[a] stands for the contents of the a-th register, 0 <= a, b < 32, 0 <= x < n, 0 <= c <= 1.
The instruction set is as follows:
| Instruction | Semantics |
|
AND a b OR a b XOR a b NOT a MOV a b SET a c RANDOM a JMP x JZ x a STOP |
MEM[a] := MEM[a] and MEM[b] MEM[a] := MEM[a] or MEM[b] MEM[a] := MEM[a] xor MEM[b] MEM[a] := not MEM[a] MEM[a] := MEM[b] MEM[a] := c MEM[a] := random value (0 or 1) jump to the instruction with the number x jump to the instruction with the number x if MEM[a] = 0 stop the program |
The last instruction of a program is always STOP (although there can be more than one STOP instruction). Every program starts with the instruction number 0. Before the start, the contents of the registers can be arbitrary values. Each instruction (including
STOP) takes 1 processor cycle to execute.
Task
Write a program that:
reads the program,
computes the shortest possible running time of the program,
writes the result.
Input
The first line of the input contains an integer n (1 <= n <= 16) being the number of instructions of the program. Each of the next n lines contains one instruction of the program in the format given above. You may assume that the only white characters in the
program are single spaces between successive tokens of each instruction.
program are single spaces between successive tokens of each instruction.
Output
The first and only line of the output should contain the shortest possible running time of the program, measured in processor cycles. If the program cannot stop, output should contain the word HANGS.
Sample Input
5 SET 0 1 JZ 4 0 RANDOM 0 JMP 1 STOP
Sample Output
6
题意：给你n行程序 让你判断程序能否stop 能则输出最小步数 不能则输出HANGS
程序的作用见表格 要注意的是寄存器的初始值是不确定的
思路：从根本上影响程序运行的语句只有JZ一个，其它都是顺序语句或确定的跳转语句。
所以我们计算程序会不会挂掉只需要关注JZ语句的位置。 因为最多只有16条语句，所以最多只有16个影响因素（其实是14个，STOP和JZ不能算的）
因为a,b可以达到32个(状态压缩 内存也吃不消） 而影响因素最多只有14个 故要想到离散化的思想 将能影响JZ的a，b的值映射到一个集合mp[]数组中 然后后面的操作只对mp数组操作就够了 这样状态最多就只有2^14个了 用二进制的思想表示状态 然后判重也很简单了。 （下面所说的a,b 都是指mp[a] mp[b]) 我们将语句中互相影响的因素建图。 例如，AND a b，a的值会被b影响。所以添加一条a->b的边。 构图完成后，进行一次dfs 找出所有能影响JZ程序的a,b的值全部记录下来
因为这些值的初始值会影响结果 所以需枚举出这些值的初始状态 （我也用的是dfs的方法枚举）
然后对这些初始状态往下搜就够了 用bfs dfs 都可以 下面给出两种代码
感想：这题花了我好多天 过程：无法下手->写出来->debug->RE->WA->TLE->AC 虽然过程很漫长 但是最后还是A掉了 真的是太爽了 O(∩_∩)O 1.bfs解法 Memory 5340K Time:16MS
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <queue> using namespace std; int n,m,ans,cnt; int head,tail; int bin[25]; int jz[20]; int mp[35]; int random[20],visran[20]; int city[35][35]; // 建图用 bool vis[16][1<<16]; // 判重用 此时进行到程序的第几部+所有能影响程序的寄存器值的状态 struct Node { int step; int a,b,c,x; } node[25]; struct hehe { int cnt; Node x1; int state1; int kk; } cur,now,q[2000005]; void predfs(int kk) { int i,j; for(i=1; i<=cnt; i++) { if(city[kk][i]&&!visran[i]) { visran[i]=1; random[i]=1; predfs(i); // visran[i]=0; } } } int oper(int x1,int x2,int k) { int i,j,t; if(k==1) t=x1&x2; else if(k==2) t=x1|x2; else if(k==3) t=x1^x2; else if(k==4) t=!x1; else if(k==5) t=x2; else if(k==6) t=x2; return t; } bool bfs() { // printf("k:%d state:%d step:%d\n",k,state,step); int i,j,stp,tta,ttb,ttc,ttx,tst,na,nb,ta,tb,ntst,ncnt; int k; while(head<=tail) { now=q[head]; head++; stp=now.x1.step; tta=now.x1.a; ttb=now.x1.b; ttc=now.x1.c; ttx=now.x1.x; k=now.kk; ntst=now.state1; ncnt=now.cnt; switch(stp) { case 1: case 2: case 3: case 4: case 5: case 6: if(!random[mp[tta]]) { if(!vis[k+1][ntst]) { vis[k+1][ntst]=1; cur.cnt=ncnt+1; cur.kk=k+1; cur.x1=node[k+1]; cur.state1=ntst; q[++tail]=cur; } } else { if(stp==6||stp==4) nb=ttc; else { if(ntst&(1<<(mp[ttb]-1))) nb=1; else nb=0; } if(ntst&(1<<(mp[tta]-1))) na=ta=1; else na=ta=0; na=oper(na,nb,stp); tst=ntst-ta*bin[mp[tta]-1]+na*bin[mp[tta]-1]; if(!vis[k+1][tst]) { vis[k+1][tst]=1; cur.cnt=ncnt+1; cur.kk=k+1; cur.state1=tst; cur.x1=node[k+1]; q[++tail]=cur; } } break ; case 7: if(!random[mp[tta]]) { if(!vis[k+1][ntst]) { vis[k+1][ntst]=1; cur.cnt=ncnt+1; cur.kk=k+1; cur.x1=node[k+1]; cur.state1=ntst; q[++tail]=cur; } } else { tst=ntst|(1<<(mp[tta]-1)); if(!vis[k+1][tst]) { vis[k+1][tst]=1; cur.cnt=ncnt+1; cur.kk=k+1; cur.state1=tst; cur.x1=node[k+1]; q[++tail]=cur; } tst=ntst&(~(1<<(mp[tta]-1))); if(!vis[k+1][tst]) { vis[k+1][tst]=1; cur.cnt=ncnt+1; cur.kk=k+1; cur.state1=tst; cur.x1=node[k+1]; q[++tail]=cur; } } break ; case 8: // printf("pre case 8: ttx:%d state:%d\n",ttx,state); if(!vis[ttx][ntst]) { // printf("case 8: ttx:%d state:%d\n",ttx,state); vis[ttx][ntst]=1; cur.cnt=ncnt+1; cur.kk=ttx; cur.state1=ntst; cur.x1=node[ttx]; q[++tail]=cur; } break ; case 9: if(!(ntst&(1<<(mp[tta]-1)))) { if(!vis[ttx][ntst]) { vis[ttx][ntst]=1; cur.cnt=ncnt+1; cur.kk=ttx; cur.state1=tst; cur.x1=node[ttx]; q[++tail]=cur; } } else { if(!vis[k+1][ntst]) { vis[k+1][ntst]=1; cur.cnt=ncnt+1; cur.kk=k+1; cur.state1=tst; cur.x1=node[k+1]; q[++tail]=cur; } } break ; case 10: ans=ncnt+1; return true; } } return false ; } void enumstate(int k,int sta) { if(k>cnt) // 枚举完一次情况后即可进栈 { // printf("sta:%d\n",sta); cur.cnt=0; cur.state1=sta; cur.x1=node[0]; cur.kk=0; if(!vis[0][sta]) { vis[0][sta]=1; q[++tail]=cur; } return ; } if(!random[k]) enumstate(k+1,sta); else { enumstate(k+1,sta); sta+=bin[k-1]; enumstate(k+1,sta); sta-=bin[k-1]; } } int main() { int i,j,ta,tb,tc,tx; int flag,fjz,xxc; char s[20]; for(i=0; i<=21; i++) { bin[i]=1<<i; } while(~scanf("%d",&n)) { cnt=0; memset(node,-1,sizeof(node)); memset(city,0,sizeof(city)); memset(mp,0,sizeof(mp)); mp[34]=1; xxc=0; for(i=0; i<n; i++) { scanf("%s",s); ta=tb=34; fjz=0; flag=0; if(s[0]=='A') { flag=1; scanf("%d%d",&ta,&tb); node[i].step=1; node[i].a=ta; node[i].b=tb; } else if(s[0]=='O') { flag=1; scanf("%d%d",&ta,&tb); node[i].step=2; node[i].a=ta; node[i].b=tb; } else if(s[0]=='X') { flag=1; scanf("%d%d",&ta,&tb); node[i].step=3; node[i].a=ta; node[i].b=tb; } else if(s[0]=='N') { scanf("%d",&ta); node[i].step=4; node[i].a=ta; } else if(s[0]=='M') { flag=1; scanf("%d%d",&ta,&tb); node[i].step=5; node[i].a=ta; node[i].b=tb; } else if(s[0]=='S'&&s[1]=='E') { scanf("%d%d",&ta,&tc); node[i].step=6; node[i].a=ta; node[i].c=tc; } else if(s[0]=='R') { scanf("%d",&ta); node[i].step=7; node[i].a=ta; } else if(s[0]=='J'&&s[1]=='M') { scanf("%d",&tx); node[i].step=8; node[i].x=tx; } else if(s[0]=='J'&&s[1]=='Z') { scanf("%d%d",&tx,&ta); node[i].step=9; node[i].a=ta; node[i].x=tx; fjz=1; } else { node[i].step=10; } if(mp[ta]==0) mp[ta]=++cnt; // 建一个映射 离散化 if(mp[tb]==0) mp[tb]=++cnt; if(flag) { city[mp[ta]][mp[tb]]=1; // 加边 } if(fjz) { xxc++; jz[xxc]=mp[ta]; } } memset(random,0,sizeof(random)); for(i=1; i<=xxc; i++) // 找出能影响程序的寄存器值 { memset(visran,0,sizeof(visran)); visran[jz[i]]=1; random[jz[i]]=1; predfs(jz[i]); } head=0; tail=-1; memset(vis,0,sizeof(vis)); enumstate(1,0); // 枚举所有初始情况 进栈 if(bfs()) printf("%d\n",ans); // bfs搜索 else printf("HANGS\n"); } return 0; } /* 3 SET 0 1 RANDOM 0 RANDOM 1 ans:HANGS 11 XOR 0 2 SET 0 0 NOT 0 JZ 5 0 JMP 2 AND 1 3 SET 1 1 JZ 10 1 RANDOM 1 JMP 7 STOP ans:14 5 SET 0 1 JZ 4 0 RANDOM 0 JMP 1 STOP ans:6 */2.dfs解法 思路都是一样的 不过代码有点乱 竟然0ms通过了 北大上面第一次排到第3这么前面 O(∩_∩)O
其实我还是感觉下面的代码不够严密（ps：上面的bfs代码是严密的） 不过我的严密dfs代码 一直超时额后来想了想 和cms讨论了一下 觉得这份代码还是严密的 因为JZ是遇0则跳 而枚举初始情况时是先0后1枚举的 能够保证状态相同时步数少的先搜索。所以也就不用回溯了，其实也可以写一个回溯的程序，这样更严密一些，就是时间要的多一点而已。// Memory 484K Time 0MS Code Length 6484B #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <queue> using namespace std; int n,m,ans,cnt; int bin[25]; int jz[20]; int mp[35]; int random[20],visran[20]; int city[35][35]; bool vis[16][1<<15]; struct Node { int step; int a,b,c,x; } node[25]; void predfs(int kk) { int i,j; for(i=1; i<=cnt; i++) { if(city[kk][i]&&!visran[i]) { visran[i]=1; random[i]=1; predfs(i); } } } int oper(int x1,int x2,int k) { int i,j,t; if(k==1) t=x1&x2; else if(k==2) t=x1|x2; else if(k==3) t=x1^x2; else if(k==4) t=!x1; else if(k==5) t=x2; else if(k==6) t=x2; return t; } void dfs(int k,int state,int sstep) { if(ans<=sstep+1) return ; int i,j,stp,tta,ttb,ttc,ttx,tst,na,nb,ta,tb; stp=node[k].step; tta=node[k].a; ttb=node[k].b; ttc=node[k].c; ttx=node[k].x; switch(stp) { case 1: case 2: case 3: case 4: case 5: case 6: if(!random[mp[tta]]) { if(!vis[k+1][state]) { vis[k+1][state]=1; dfs(k+1,state,sstep+1); } } else { if(stp==6||stp==4) nb=ttc; else { if(state&(1<<(mp[ttb]-1))) nb=1; else nb=0; } if(state&(1<<(mp[tta]-1))) na=ta=1; else na=ta=0; na=oper(na,nb,stp); tst=state-ta*bin[mp[tta]-1]+na*bin[mp[tta]-1]; if(!vis[k+1][tst]) { vis[k+1][tst]=1; dfs(k+1,tst,sstep+1); } } break ; case 7: if(!random[mp[tta]]) { if(!vis[k+1][state]) { vis[k+1][state]=1; dfs(k+1,state,sstep+1); } } else { tst=state|(1<<(mp[tta]-1)); if(!vis[k+1][tst]) { vis[k+1][tst]=1; dfs(k+1,tst,sstep+1); } tst=state&(~(1<<(mp[tta]-1))); if(!vis[k+1][tst]) { vis[k+1][tst]=1; dfs(k+1,tst,sstep+1); } } break ; case 8: if(!vis[ttx][state]) { vis[ttx][state]=1; dfs(ttx,state,sstep+1); } else return ; break ; case 9: if(!(state&(1<<(mp[tta]-1)))) { if(!vis[ttx][state]) { vis[ttx][state]=1; dfs(ttx,state,sstep+1); } } else { if(!vis[k+1][state]) { vis[k+1][state]=1; dfs(k+1,state,sstep+1); } } break ; case 10: if(ans>sstep+1) ans=sstep+1; return ; } } void enumstate(int k,int sta) { if(k>cnt) { vis[0][sta]=1; dfs(0,sta,0); return ; } if(!random[k]) enumstate(k+1,sta); else { enumstate(k+1,sta); sta+=bin[k-1]; enumstate(k+1,sta); sta-=bin[k-1]; } } int main() { int i,j,ta,tb,tc,tx; int flag,fjz,xxc; char s[20]; for(i=0; i<=21; i++) { bin[i]=1<<i; } while(~scanf("%d",&n)) { cnt=0; memset(node,-1,sizeof(node)); memset(city,0,sizeof(city)); memset(mp,0,sizeof(mp)); mp[34]=1; xxc=0; for(i=0; i<n; i++) { scanf("%s",s); ta=tb=34; fjz=0; flag=0; if(s[0]=='A') { flag=1; scanf("%d%d",&ta,&tb); node[i].step=1; node[i].a=ta; node[i].b=tb; } else if(s[0]=='O') { flag=1; scanf("%d%d",&ta,&tb); node[i].step=2; node[i].a=ta; node[i].b=tb; } else if(s[0]=='X') { flag=1; scanf("%d%d",&ta,&tb); node[i].step=3; node[i].a=ta; node[i].b=tb; } else if(s[0]=='N') { scanf("%d",&ta); node[i].step=4; node[i].a=ta; } else if(s[0]=='M') { flag=1; scanf("%d%d",&ta,&tb); node[i].step=5; node[i].a=ta; node[i].b=tb; } else if(s[0]=='S'&&s[1]=='E') { scanf("%d%d",&ta,&tc); node[i].step=6; node[i].a=ta; node[i].c=tc; } else if(s[0]=='R') { scanf("%d",&ta); node[i].step=7; node[i].a=ta; } else if(s[0]=='J'&&s[1]=='M') { scanf("%d",&tx); node[i].step=8; node[i].x=tx; } else if(s[0]=='J'&&s[1]=='Z') { scanf("%d%d",&tx,&ta); node[i].step=9; node[i].a=ta; node[i].x=tx; fjz=1; } else { node[i].step=10; } if(mp[ta]==0) mp[ta]=++cnt; if(mp[tb]==0) mp[tb]=++cnt; if(flag) { city[mp[ta]][mp[tb]]=1; } if(fjz) { xxc++; jz[xxc]=mp[ta]; } } memset(random,0,sizeof(random)); for(i=1; i<=xxc; i++) { memset(visran,0,sizeof(visran)); visran[jz[i]]=1; random[jz[i]]=1; predfs(jz[i]); } ans=100000000; memset(vis,0,sizeof(vis)); enumstate(1,0); if(ans<100000000) printf("%d\n",ans); else printf("HANGS\n"); } return 0; }