顯示包含「BFS」標籤的文章。顯示所有文章
顯示包含「BFS」標籤的文章。顯示所有文章

2010年7月28日星期三

ICPC 2929 Hang or not to hang

題意:


給定一個 program(LOC ≤ 16)
有 ≤ 32 個 boolean variable(值 = 0 或 1)
instruction 有以下 10 種:

 
每個 instruction 執行時間花費 1 cycle(包括 STOP)

variable 的起始狀態是隨機
問,程序最早結束時間可以是多少?
是否對任何起始狀態,都會「Loop死」?



枚舉全 232 variable 的起始狀態再逐一 simulate
顯然會超出 時間/memory 限制...

細心一想... 所謂 randomness 其實只是 JZ 指令