50087. See-Saw

I'm a slow walker, but I never walk backwards.

Write a program to switch people in a seesaw and find a balancing point.

Task Description

We have a see-saw of positive integers. Imagine that we have a stick of $n$ cells, and a sequence of $n$ positive integers, where each integer is sitting within a cell. A seesaw is balanced at positive $i$ if we support the seesaw at $i_{th}$ cell then the torque from two sides is the same. For example, let $n$ be $5$ and the numbers are $2$, $1$, $5$, $3$, and $1$. Then we can get a balanced see-saw when the balancing point is at $5$, because $2\times 2+1\times 1 = 3\times 1+1\times 2$. Note that since all numbers are positive so there is only one balancing point. Also note that $5$ is at the support and will not have any torque.

We find a balanced see-saw by repeating the following two steps. In the first step, we search the balancing point from left to right. If we can find a balancing point then we stop and report its position. Otherwise we go to the second step, where we switch the first and the last integers, then repeat step $1$. In the next iteration if we still cannot find a balancing point, we switch the second and second to the last integers, and repeat step $1$. We repeat this two-step iteration until we find a balancing point. We guarantee that this iteration will find a balancing point. Once you find a solution, please output the answer and end the program.

Let us consider an example. Let $n$ be $6$ and the numbers are $1$, $1$, $2$, $1$, $3$, and $11$. In the first iteration, there is no balancing point, so we switch the first and the last integers and the sequence becomes $11$, $1$, $2$, $1$, $3$, and $1$. However, there is still no balancing point in the second iteration, so we switch the second and the second to the last integers again and the sequence now becomes $11$, $3$, $2$, $1$, $1$, and $1$. In the third iteration, we finally find the balancing point at $3$, since $11\times 1=2\times 1+1\times 2+1\times 3+1\times 4$.

Subtask

  • 30 points: The first iteration will find a solution, i.e., you do not need to do the second step (to switch people).
  • 70 points: Two steps are necessary.

Input Format

The input contains only one test case. The first line contains one integer $n$, representing the number of sequence. The second line contains $n$ integers, $w_{1}$, $w_{2}$, … , $w_{n}$, representing the weights of people.

  • $0 \lt n \lt = 2048$
  • $0 \lt w_{i}$

Output Format

Print the balanced see-saw which is the first solution in one line. And use ‘v’ to represent the balancing point.

Note that there is no space at the end of line.

Sample Input 1

5
2 1 5 3 1

Sample Output 1

2 1 v 3 1

Sample Input 2

6
1 1 2 1 3 11

Sample Output 2

11 v 2 1 1 1

Discussion