P5016 [NOIP 2018 Junior] Dragon-Tiger Battle

NOIP2018 Junior T2.

Xuanxuan and Kaikai are playing a game called *Dragon-Tiger Battle*. The game board is a line segment with $n$ barracks on it (numbered from left to right as $1 \sim n$). The distance between two adjacent barracks is $1$ centimeter, so the board is a line segment of length $n-1$ centimeters. Barrack $i$ contains $c_i$ engineers. Figure 1 below shows an example with $n=6$:  Xuanxuan is on the left, representing the “Dragon”; Kaikai is on the right, representing the “Tiger”. They take barrack $m$ as the boundary: engineers on the left belong to the Dragon side, engineers on the right belong to the Tiger side, and the engineers in barrack $m$ are undecided and do not belong to either side. The momentum of a barrack is defined as: (number of engineers in the barrack) $ \times $ (distance from the barrack to barrack $m$). The power of a side is defined as: the sum of the momentum of all barracks belonging to that side. Figure 2 below shows an example with $n = 6, m = 4$, where red is the Dragon side and yellow is the Tiger side:  During the game, at some moment, reinforcements arrive from the sky: a total of $s_1$ engineers suddenly appear in barrack $p_1$. As a friend of Xuanxuan and Kaikai, you know that if the difference in power between the Dragon and Tiger becomes too large, they will not want to continue playing. To keep the game going, you need to choose a barrack $p_2$ and send all $s_2$ engineers in your hand to barrack $p_2$, so that the difference in power between the two sides is as small as possible. Note: The engineers you send will have the same side affiliation as the engineers already in that barrack (if they land in barrack $m$, they do not belong to any side).

The first line contains a positive integer $n$, representing the number of barracks. The next line contains $n$ positive integers, separated by single spaces. The $i$-th positive integer represents the initial number of engineers $c_i$ in barrack $i$. The next line contains four positive integers, separated by single spaces, representing $m, p_1, s_1, s_2$.

Output one line containing a positive integer, namely $p_2$, the index of the barrack you choose. If multiple indices achieve the optimal result at the same time, output the smallest index.

**Explanation for Sample 1** See Figure 2 in the problem description. The two sides are divided by barrack $m=4$. There are $s_1=5$ engineers that suddenly appear in barrack $p_1=6$. The Dragon side’s power is: $$2 \times (4-1)+3 \times (4-2)+2 \times (4-3) = 14$$ The Tiger side’s power is: $$2 \times (5 - 4) + (3 + 5) \times (6 - 4) = 18$$ When you send your $s_2 = 2$ engineers to barrack $p_2 = 2$, the Dragon side’s power becomes: $$14 + 2 \times (4 - 2) = 18$$ At this time, the two sides have equal power. **Explanation for Sample 2** The two sides are divided by barrack $m = 5$. There are $s_1 = 1$ engineers that suddenly appear in barrack $p_1 = 4$. The Dragon side’s power is: $$1 \times (5 - 1) + 1 \times (5 - 2) + 1 \times (5 - 3) + (1 + 1) \times (5 - 4) = 11$$ The Tiger side’s power is: $$16 \times (6 - 5) = 16$$ When you send your $s_2 = 1$ engineers to barrack $p_2 = 1$, the Dragon side’s power becomes: $$11 + 1 \times (5 - 1) = 15$$ At this time, the difference in power between the two sides can be minimized. **Constraints** $1 < m < n$, $1 \le p_1 \le n$. For $20\%$ of the testdata, $n = 3, m = 2, c_i = 1, s_1, s_2 ≤ 100$. Another $20\%$ of the testdata has $n ≤ 10, p_1 = m, c_i = 1, s_1, s_2 ≤ 100$. For $60\%$ of the testdata, $n ≤ 100, c_i = 1, s_1, s_2 ≤ 100$. For $80\%$ of the testdata, $n ≤ 100, c_i, s_1, s_2 ≤ 100$. For $100\%$ of the testdata, $n ≤ 10^5$, $c_i, s_1, s_2 ≤ 10^9$. Translated by ChatGPT 5