NOIP '18 Junior P2 - The Big Battle

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

Xuanxuan and Kaikai are playing a game called "The Big Battle". The board of the game is a line segment with n barracks (labelled 1 \sim n from left to right). The distance between any two adjacent numbered barracks is always 1 cm, that is, the board is a line segment of length n-1 cm. There are c_i soldiers in barracks i.

The figure below is an example of n = 6:

Xuanxuan is on the left, representing "Dragon"; Kaikai is on the right, representing "Tiger". They used the barracks m as the dividing line. The soldiers on the left of the dividing line belong to the Dragon army, and the soldiers on the right of the line belong to the Tiger army. Soldiers in the barracks numbered m are very tangled; thus they do not belong to either side.

The strength of a barracks is defined as the number of soldiers in the barracks \times the distance from the barracks to the barracks m; the total strength of an army participating in the game is defined as the sum of the strength of all barracks belonging to this army.

The figure below is an example of n = 6, m = 4, where red is the Dragon army and yellow is the Tiger army:

During the game, at a certain moment, a total of s_1 soldiers suddenly appeared in the barracks p_1. As friends of Xuanxuan and Kaikai, you know that if there is a huge difference in total strength between the Dragon army and Tiger army, Xuanxuan and Kaikai will not be willing to continue playing. In order to continue the game, you need to choose a barracks p_2, and send out all s_2 soldiers to barracks p_2, so that the difference in total strength between the two sides is as small as possible.

The soldiers you are sending out belong to the army in the barracks you sent them out to (if you sent them into the barracks m, they will not belong to any army).

Input Specification

The first line of the input contains a positive integer n, representing the number of barracks.

The next line contains n space-separated positive integers, and the i-th positive integer represents the initial number of soldiers c_i in barracks i.

The next line contains four space-separated positive integers, representing m, p_1, s_1, s_2 respectively.

Output Specification

Output a single line containing a positive integer, p_2, representing the barracks you choose to send the soldiers to. If there are multiple optimal barracks, output the barracks with the smallest label.

Sample Input 1

6
2 3 2 3 2 3
4 6 5 2

Sample Output 1

2

Explanation for Sample 1

The two sides are divided by barracks m = 4, and s_1 = 5 soldiers suddenly appear in barracks p_1 = 6.

The total strength of Dragon army is 2 \times (4-1) + 3 \times (4-2) + 2 \times (4-3) = 14.

The total strength of Tiger army is 2 \times (5-4) + (3+5) \times (6-4) = 18.

When you send s_2 = 2 soldiers to the barracks p_2 = 2, Dragon army's total strength becomes 14 + 2 \times (4-2) = 18.

At this time, the two sides are equal in total strength.

Sample Input 2

6
1 1 1 1 1 16
5 4 1 1

Sample Output 2

1

Explanation for Sample 2

The two sides are divided by barracks m = 5, and s_1 = 1 soldiers suddenly appear in barracks p_1 = 4.

The total strength of Dragon army is 1 \times (5-1) + 1 \times (5-2) + 1 \times (5-3) + (1+1) \times (5-4) = 11.

The total strength of Tiger army is 16 \times (6-5) = 16.

When you send s_2 = 1 soldiers to the barracks p_2 = 1, Dragon army's total strength becomes 11 + 1 \times (5-1) = 15.

At this time, the difference between the two sides is minimized.

Constraints

1 < m < n, 1 \le p_1 \le n

For 20\% of the data, n = 3, m = 2, c_i = 1, s_1, s_2 \le 100.

There is another 20\% of the data, n \le 10, p_1 = m, c_i = 1, s_1, s_2 \le 100.

For 60\% of the data, n \le 100, c_i = 1, s_1, s_2 \le 100.

For 80\% of the data, n \le 100, c_i, s_1, s_2 \le 100.

For 100\% of the data, n \le 10^5, c_i, s_1, s_2 \le 10^9.

Problem translated to English by Tommy_Shan.


Comments

There are no comments at the moment.