a256. 自動平衡蹺蹺板

Content

請你幫蹺蹺板設定一個自動平衡系統，蹺蹺板上有 $N$ 個物品擺成一排，當在第 $i$ 格時，左右力矩接相等的話，則第 $i$ 格為支點。舉例來說，若 $5$ 個物品重量依序為 $[2, 1, 5, 3, 1]$，則支點為 $5$ ，因為 $2 \times 2 + 1 \times 1 = 3 \times 1 + 1 \times 2$，其中 $5$ 並不會造成任何力矩。因為所有的物品重量皆為正整數，因此可以確保不會有多個支點同時存在。

為了找到適合的支點，我們透過以下兩個步驟：

從左到右依序嘗試將支點放在物品$i$上，如果能找到平衡的支點則直接輸出並結束程式。
若找不到平衡點，則將第一個與最後一個物品對調，再重複進行步驟1；若仍無法找到平衡點，再將第二個與倒數第二個對調…，以此類推直到找到平衡的支點為止。

題目保證依此步驟一定能夠找到支點，只要找到支點後即可輸出結果並結束程式。

Input

第一航輸入一個整數 $N$，代表人數。$1 \leq N \leq 2048$

第二行輸入初始排列的狀況，依序輸入每個物品的重量 $w_1, w_2, w_3 ... w_N$。題目保證不會超過200

子題分數：

第一子題 30 分：第一回合就會找到答案（不用做到步驟2）
第二子題 70 分：無其他限制

Output

輸出平衡時的人數字，其中支點請用 'v' 表示。

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

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 0.5s , <1K
公開測資點#1 (5%): 0.5s , <1K
公開測資點#2 (5%): 0.5s , <1K
公開測資點#3 (5%): 0.5s , <1K
公開測資點#4 (5%): 0.5s , <1M
公開測資點#5 (5%): 0.5s , <1M
公開測資點#6 (10%): 0.5s , <1K
公開測資點#7 (10%): 0.5s , <1K
公開測資點#8 (10%): 0.5s , <1K
公開測資點#9 (10%): 0.5s , <1M
公開測資點#10 (10%): 0.5s , <1M
公開測資點#11 (10%): 0.5s , <1M
公開測資點#12 (10%): 0.5s , <1K

Hint ：

範例二說明：
在第一回合無法找到支點，因此我們將第一個物品與最後一個物品對調，序列變成$[11, 1, 2, 1, 3, 1]$。
第二回合仍無法找到支點，因此我們將第二個物品與倒數第二個物品對調，序列變成$[11, 3, 2, 1, 1, 1]$。
第三回合時，我們可以找到支點為 $3$ 。

Tags:

出處:

judgegirl [管理者： zero(管理員) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」