{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"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\u0027s 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. \r\u003cbr\u003e\r\u003cbr\u003eTom\u0027s 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. \r\u003cbr\u003e\r\u003cbr\u003eBelow, MEM[a] stands for the contents of the a-th register, 0 \u0026lt;\u003d a, b \u0026lt; 32, 0 \u0026lt;\u003d x \u0026lt; n, 0 \u0026lt;\u003d c \u0026lt;\u003d 1. \r\u003cbr\u003e\r\u003cbr\u003eThe instruction set is as follows: \r\u003cbr\u003e\r\u003cbr\u003e\u003ctable border\u003d\"2\" cellpadding\u003d\"8\" cellspacing\u003d\"3\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd width\u003d\"110\"\u003eInstruction\u003c/td\u003e\u003ctd\u003eSemantics\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\r\u003cbr\u003eAND a b\r\u003cbr\u003eOR a b\r\u003cbr\u003eXOR a b\r\u003cbr\u003eNOT a\r\u003cbr\u003eMOV a b\r\u003cbr\u003eSET a c\r\u003cbr\u003eRANDOM a\r\u003cbr\u003eJMP x\r\u003cbr\u003eJZ x a\r\u003cbr\u003eSTOP\r\u003cbr\u003e\u003c/td\u003e\u003ctd\u003e\r\u003cbr\u003eMEM[a] :\u003d MEM[a] and MEM[b] \r\u003cbr\u003eMEM[a] :\u003d MEM[a] or MEM[b] \r\u003cbr\u003eMEM[a] :\u003d MEM[a] xor MEM[b]\r\u003cbr\u003eMEM[a] :\u003d not MEM[a]\r\u003cbr\u003eMEM[a] :\u003d MEM[b]\r\u003cbr\u003eMEM[a] :\u003d c\r\u003cbr\u003eMEM[a] :\u003d random value (0 or 1)\r\u003cbr\u003ejump to the instruction with the number x\r\u003cbr\u003ejump to the instruction with the number x if MEM[a] \u003d 0\r\u003cbr\u003estop the program\r\u003cbr\u003e\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\r\u003cbr\u003eThe 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. \r\u003cbr\u003eTask\r\u003cbr\u003eWrite a program that:\r\u003cbr\u003e\r\u003cbr\u003ereads the program, \r\u003cbr\u003ecomputes the shortest possible running time of the program, \r\u003cbr\u003ewrites the result. \r\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer n (1 \u0026lt;\u003d n \u0026lt;\u003d 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. "}},{"title":"Output","value":{"format":"HTML","content":"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. "}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\nSET 0 1\r\nJZ 4 0\r\nRANDOM 0\r\nJMP 1\r\nSTOP\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}