RobotHerb

作者：吕欣
关键词：模拟，找规律

题意简述

某机器人在平面上原点处，它有一个长度为 $n(\leq50)$ 的命令序列，其中第 $i$ 个命令中它会向当前方向移动 $a[i]$ 个位置，然后顺时针旋转 $a[i]\times 90$ 度，它会重复执行这个命令序列 $T$ 次，求它最后停下来的位置和原点的曼哈顿距离。

约定：$T, a[i]\leq10^9, n\leq 50$

算法分析

不难发现，无论机器人执行一次命令序列之后方向如何旋转，它重复执行 $4$ 次命令序列之后总能回到原来的方向，所以每 $4$ 次命令序列使它产生的位移是相同的。

我们暴力模拟 $4$ 次命令序列，就能知道 $4\times\lfloor{\frac T4}\rfloor$ 次命令序列的执行使它产生的位移，同时它现在恢复了初始的朝向，我们对 $T\mod 4$ 的零散部分再模拟一遍即可得到它最终的的位置 $(x,y)$，答案即为 $\left| x\right|+\left|y\right|$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$