← 返回题目列表

Codeforces · 1609/H

H. 推机器人

中文机器翻译题面 查看原题

数轴上放置了 $$$n$$$ 个机器人。最初,第$$$i$$$占据单位段$$$[x_i, x_i + 1]$$$。每个机器人都有一个程序,由$$$k$$$指令组成,编号从$$$1$$$到$$$k$$$。机器人在一个周期内执行指令。每条指令都由一个整数来描述。我们将第 $$$i$$$ 机器人的第 $$$j$$$ 指令对应的数字表示为 $$$f_{i, j}$$$。

机器人的初始放置对应于时间$$$0$$$。从 $$$t$$$ ($$$0 \le t$$$) 到 $$$t + 1$$$ 的一秒内,发生以下过程:

1. 每个机器人执行其指令列表中的第 $$$(t \bmod k + 1)$$$ 条指令。机器人编号 $$$i$$$ 的编号为 $$$F = f_{i, (t \bmod k + 1)}$$$。如果该数字为负数(小于零),则机器人尝试用力 $$$|F|$$$ 向左移动。如果数字为正(大于零),则机器人正尝试用力 $$$F$$$ 向右移动。否则,机器人什么也不做。
2. 让我们使用以下算法将机器人想象地分成连续的组: 最初,每个机器人属于自己的组。 让我们总结一组机器人指令对应的数字。请注意,我们对数字进行求和,而不是取绝对值。将该总和表示为 $$$S$$$。我们说整个群体一起移动,并按照与单个机器人相同的规则用力 $$$S$$$ 进行移动。也就是说,如果 $$$S$$$ 为负数,则该群体试图用力 $$$|S|$$$ 向左移动。如果 $$$S$$$ 为正,则该群体正试图用力 $$$S$$$ 向右移动。否则,该小组什么也不做。 如果一个群体试图移动,并且在移动方向上接触到另一群体,那么让我们将他们联合起来。如果一组最外面的机器人占据相邻的单元段,则一组正在接触另一组。 继续这个过程,直到群体停止团结。
3. 每个机器人沿着其组的移动方向移动$$$1$$$,或者如果其组不移动则保持在原地。但有一个例外。
4. 例外情况是,如果有两组机器人,正好被一个单位段划分,则左侧组尝试向右移动,右侧组尝试向左移动。我们将左侧组中的总和表示为 $$$S_l$$$,将右侧组中的总和表示为 $$$S_r$$$。如果$$$|S_l| \le |S_r|$$$ 只有正确的组才会移动。否则,只有左边的组会移动。
5. 请注意,一组机器人不会粘在一起。他们将来可能会分开。分组的划分是虚构的,仅需要了解机器人在一秒钟内如何移动 $$$[t, t + 1]$$$。

一秒钟内发生的过程的图示:

矩形代表机器人。矩形内的数字对应于机器人的指令。最终分组用弧线标记。以下是机器人移动后的位置。最右边的两组中只有左边的动了。这是因为这两群人试图靠近对方,结果却被恰好隔开了一个单位段。

查看示例以更好地理解该过程。

您需要回答几个问题。第 $$$a_i$$$ 个机器人在 $$$t_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$$$ 行包含机器人程序的描述。这些行的第 $$$i$$$ 包含 $$$k$$$ 整数 $$$f_{i, j}$$$ ($$$|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}$$$)。

输出

对于每个问题,在新行上输出一个整数。第$$$a_i$$$个机器人在$$$t_i$$$时刻占据的单位段左边界坐标。

示例

输入 #1

2 1
0 4
1
-1
8
1 0
2 0
1 1
2 1
1 2
2 2
1 3
2 3

输出 #1

0
4
1
3
1
2
1
2

输入 #2

2 1
0 4
2
-1
8
1 0
2 0
1 1
2 1
1 2
2 2
1 3
2 3

输出 #2

0
4
1
3
2
3
3
4

输入 #3

2 2
0 1
1 -1
-1 1
4
1 0
1 1
1 2
1 3

输出 #3

0
0
-1
0

输入#4

1 3
0
3 -2 1
3
1 5
1 10
1 15

输出#4

1
4
5

输入 #5

4 3
-8 -4 2 5
-1 3 0
1 -3 -4
2 -5 2
-1 -4 2
5
3 12
4 18
4 11
1 6
1 10

输出 #5

6
9
6
-8
-9