#P17545. [JAG 2026 Summer Camp #2] Robot Damage
[JAG 2026 Summer Camp #2] Robot Damage
题目描述
某实验室有一条可以视为数轴的直线测试轨道,以及一个沿轨道移动的机器人。每次实验开始时,机器人都静止在原点。
轨道上放置了两面墙,一面位于负坐标,另一面位于正坐标。机器人无法穿过墙,只能在两面墙之间的闭区间内移动。
机器人上有一个按钮。按下按钮后,机器人依次执行以下 个阶段。
- 假设第 个阶段开始时机器人位于坐标 。它尝试沿数轴向坐标 移动。若 ,则向右移动;若 ,则向左移动。
- 如果没有墙阻挡,机器人用一分钟抵达目标位置。在阶段开始时,它的速度为零,随后加速、减速,并以零速度抵达目标位置。在移动过程的每个中间位置,它的速度都大于零。
- 如果一面墙严格位于当前位置和目标位置之间,机器人就会在移动过程中撞上墙,并在墙边结束当前阶段。
完成全部 个阶段后,机器人停在当前位置。若再次按下按钮,它就从该位置出发,再执行一遍相同的 个阶段。
每当机器人以正速度撞上墙时,就会受到一点伤害。但在以下两种情况下,它不会受到伤害。
- 目标位置恰好位于墙边,因此机器人以零速度抵达墙边。
- 阶段开始时机器人已经贴着墙,并尝试越过这面墙。此时机器人不会移动。
换言之,当且仅当一面墙严格位于阶段开始时的位置与预定目标位置之间,机器人才会在该阶段受到伤害。只要碰撞时速度为正,伤害量就与具体速度无关。
给定 次询问,询问之间相互独立。第 次询问描述如下实验。
- 将墙放在坐标 和 ,将机器人放在原点。
- 总共按下按钮 次,每次都等上一次按钮触发的动作完成后再按。两次按按钮之间不移动机器人。
求机器人在这次实验中受到的总伤害。
给定 组测试数据,请分别求解。
输入格式
输入包含一组或多组测试数据。第一行包含一个整数 ,表示测试数据组数()。随后依次给出各组测试数据,每组格式如下。
N
V_1 V_2 ... V_N
Q
W_1 T_1
W_2 T_2
...
W_Q T_Q
整数 表示每次按下按钮后执行的阶段数()。对于每个 ,整数 表示第 个阶段尝试移动的位移(,)。
整数 表示询问次数()。对于每个 ,整数 分别表示第 次询问中原点到每面墙的距离以及按按钮的次数(,)。
所有测试数据的 之和不超过 , 之和不超过 。
输出格式
对于每组测试数据,输出 行。第 行包含第 次询问的答案。
4
4
1 -8 6 -7
2
5 1
9 2
3
1 -2 1
1
1 100
2
3 4
2
8 2
8 10000
2
1000000000 -1000000000
1
10 1000000000000
2
2
0
1
1
2000000000000
提示
在第一组测试数据中,第 次询问会在第 和第 个阶段于 处发生碰撞,共受到 点伤害。第 次询问中,两次在 处发生的碰撞都出现在第二次按下按钮之后。
在第二组测试数据中,机器人从未以正速度撞上墙,因此没有受到伤害。