#P17545. [JAG 2026 Summer Camp #2] Robot Damage
[JAG 2026 Summer Camp #2] Robot Damage
Problem Description
A laboratory has a straight test track, which can be regarded as a number line, and a robot that moves along it. At the beginning of each experiment, the robot is stationary at the origin.
Two walls are placed on the track, one at a negative coordinate and the other at a positive coordinate. The robot cannot pass through the walls and can move only within the closed interval between them.
The robot has a button. When the button is pressed, the robot performs the following phases in order.
- Suppose that the robot is at coordinate at the beginning of phase . It attempts to move along the number line toward coordinate . It moves to the right if and to the left if .
- If no wall blocks its path, the robot takes one minute to reach its destination. Its speed is zero at the beginning of the phase. It then accelerates and decelerates, reaching the destination at speed zero. Its speed is positive at every intermediate point of the movement.
- If a wall lies strictly between its current position and its destination, the robot collides with the wall during the movement and ends the phase at the wall.
After completing all phases, the robot stops at its current position. If the button is pressed again, it performs the same phases again, starting from that position.
Every time the robot collides with a wall at positive speed, it takes one point of damage. However, it takes no damage in either of the following cases.
- Its destination is exactly at a wall, so it reaches the wall at speed zero.
- It is already touching a wall at the beginning of a phase and attempts to move beyond that wall. In this case, it does not move.
In other words, the robot takes damage during a phase if and only if a wall lies strictly between its position at the beginning of the phase and its intended destination. The amount of damage does not depend on its speed at the collision, as long as the speed is positive.
You are given queries. The queries are independent. The -th query describes the following experiment.
- Place the walls at coordinates and , and place the robot at the origin.
- Press the button a total of times, waiting for the previous button press to finish before pressing it again. Do not move the robot between button presses.
Determine the total amount of damage taken by the robot during this experiment.
You are given test cases. Solve each of them.
Input Format
The input contains one or more test cases. The first line contains an integer , the number of test cases (). The descriptions of the test cases follow, each in the following format.
N
V_1 V_2 ... V_N
Q
W_1 T_1
W_2 T_2
...
W_Q T_Q
The integer is the number of phases performed on each button press (). For each , the integer represents the displacement attempted in phase (, ).
The integer is the number of queries (). For each , the integers and represent the distance from the origin to each wall and the number of button presses, respectively, in the -th query (, ).
The sum of over all test cases does not exceed . The sum of over all test cases does not exceed .
Output Format
For each test case, output lines. The -th line should contain the answer to the -th query.
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
Hint
In the first test case, query causes collisions at in phases and , for points of damage. In query , both collisions at occur during the second button press.
In the second test case, the robot never hits a wall at positive speed, so it takes no damage.