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 2 + 1 1 = 3 1 + 1 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 1 = 2 1 + 1 2 + 1 3 + 1 * 4.
Subtasks
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, w1, w2, … , wn, representing the weights of people.
0 < n <= 2048
0 < Wi
Output Format
Print the balanced see-saw which is the first solution in one line. And use ‘v’ to represent the balancing point.
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 2 + 1 1 = 3 1 + 1 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 1 = 2 1 + 1 2 + 1 3 + 1 * 4.
Subtasks
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, w1, w2, … , wn, representing the weights of people. 0 < n <= 2048 0 < Wi
Output Format
Print the balanced see-saw which is the first solution in one line. And use ‘v’ to represent the balancing point.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2