CF1609H Pushing Robots

有 $n$ 个机器人被放置在数轴上。最初，第 $i$ 个机器人占据区间 $[x_i, x_i + 1]$。每个机器人有一个由 $k$ 条指令组成的程序，指令编号从 $1$ 到 $k$。机器人按照循环顺序依次执行这些指令。每条指令由一个整数描述。我们用 $f_{i, j}$ 表示第 $i$ 个机器人第 $j$ 条指令对应的整数。 机器人的初始位置对应时间 $0$。在从时间 $t$（$0 \le t$）到 $t+1$ 的一秒内，发生如下过程： 1. 每个机器人执行其指令列表中的第 $(t \bmod k + 1)$ 条指令。第 $i$ 个机器人取数 $F = f_{i, (t \bmod k + 1)}$。如果 $F$ 为负数（小于零），机器人试图以 $|F|$ 的力度向左移动；如果 $F$ 为正数（大于零），机器人试图以 $F$ 的力度向右移动；如果 $F$ 为零，机器人不动。 2. 假想将机器人分为连续的若干组，分组方式如下： - 初始时，每个机器人单独为一组。 - 对于一组内的所有机器人，将它们本轮指令对应的整数相加，记为 $S$。整个组作为一个整体移动，移动规则与单个机器人相同：若 $S$ 为负，组以 $|S|$ 的力度向左移动；若 $S$ 为正，组以 $S$ 的力度向右移动；若 $S=0$，组不动。 - 若某组试图移动，并且在其移动方向上与另一组相邻（即最外侧的机器人占据相邻的单位区间），则将两组合并为一组。 - 重复上述过程，直到无法继续合并为止。 3. 每个机器人按照其所在组的移动方向移动 $1$ 单位，若组不动则原地不动。但有一个例外。 4. 例外情况：若存在两组机器人，恰好被一个单位区间隔开，且左侧组试图向右移动，右侧组试图向左移动。设左组的和为 $S_l$，右组的和为 $S_r$。若 $|S_l| \le |S_r|$，则只有右组移动；否则，只有左组移动。 5. 注意，同一组内的机器人不会永久粘连，未来可能会再次分开。分组仅为理解每一秒 $[t, t+1]$ 内机器人的移动方式而设。 下图展示了一秒内的过程：  矩形表示机器人，矩形内的数字为机器人的指令。最终的分组用弧线标出。下方为机器人移动后的状态。只有最右侧的两个组中左侧的组移动了，因为这两组试图相向移动，且中间仅隔一个单位区间。 请参考样例以更好地理解过程。 你需要回答若干个问题。对于每个问题，求出在时间 $t_i$ 时，第 $a_i$ 个机器人的位置。

第一行包含两个整数 $n$ 和 $k$，分别表示机器人的数量和每个机器人程序中的指令数（$1 \le n \le 100$，$1 \le k \le 50$）。 第二行包含 $n$ 个整数 $x_i$，表示机器人在时刻 $0$ 的位置（$-10^9 \le x_1 < x_2 < \dots < x_n < 10^9$）。 接下来 $n$ 行，每行 $k$ 个整数 $f_{i, j}$，描述第 $i$ 个机器人的程序（$|f_{i, j}| \le 10^6$）。 接下来一行包含一个整数 $q$，表示询问的数量（$1 \le q \le 1000$）。 接下来 $q$ 行，每行两个整数 $a_i$ 和 $t_i$，表示需要查询在时刻 $t_i$ 时第 $a_i$ 个机器人的位置（$1 \le a_i \le n$，$0 \le t_i \le 10^{18}$）。

对于每个询问，输出一个整数，表示在时刻 $t_i$ 时第 $a_i$ 个机器人所占据的单位区间的左端点坐标。

由 ChatGPT 4.1 翻译