IBM Ponder This #302 · 2023 年 6 月

老鼠在 $k\times k\times k$ 网格内，从 $(1,1,1)$、时间 $t=1$ 出发。每格有一单位奶酪，但只在某些时刻出现。若鼠在时刻 $t$ 位于格 $(a,b,c)$ 且奶酪存在，就将其收集；该格奶酪以后不再出现。

每单位时间可以等待，或只沿 X、Y、Z 的正方向前进一步。例如时刻 $t=13$ 位于 $(3,5,1)$，则在 $t=14$ 可到 $(3,5,1)$（等待 W）、$(4,5,1)$（向右 R）、$(3,6,1)$（向上 U）、$(3,5,2)$（向前 F）。时刻 $n$ 老鼠离开，不能再收集。

奶酪出现时间由线性同余生成器 $f(x)=(ax+c)modm$ 决定，其中 a=$1103515245$、c=$12345$、m=$2^{31}$。格 $(a,b,c)$ 在时间 $t$ 有奶酪，当且仅当存在 $0\le x<n/2$ 使 $t=f(a\cdot b\cdot c+x)modn$。

例如 $n=20$、$(a,b,c)=(3,5,1)$ 时，出现时刻 $t$ 的集合为 $\{1,3,4,5,6,7,8,9,10,12\}$。$k=5$、$n=20$ 时最多得十单位，路径可为 FFRFWFWRRRUUUWWWUWW。

任务：对 $k=30$、$n=100$ 求最大奶酪数，第一行给数量，第二行给路径。

附加问题：对 $k=50$、$n=200$ 求解，但允许左 L、下 D、后 B，且同一格奶酪在每次出现时都可以再次收集。

解答

认真尝试后再打开

待补充。