1768 . P-蹺蹺板 (Seesaw)
TopCoder
Tags
Description
傳說中，P教授擁有一個蹺蹺板，叫作P-蹺蹺板。P-蹺蹺板是個長直且質量可忽略的板子，上面有$N$個等距的座位，編號為$0$到$N-1$，每個座位都只能坐一個人。特別的是，P-蹺蹺板的支點並不是固定的，使用者可以將支點架在任何一個座位的正下方。
如果支點左右的力矩相同，那麼蹺蹺板將會平衡。例如若$N=5$，五個座位上面的重量依序為$2,1,5,3,1$，若將支點架在$2$號座位下方，則左邊力矩$\ =2\times 2 + 1\times 1 = 3\times 1 + 1\times 2=\ $右邊力矩，故蹺蹺板會平衡。
有一天，P教授叫了$N$個人過來，請他們依序坐在P-蹺蹺板上，嘗試保持平衡。然而，由於每個人的體重不盡相同，而且支點沒辦法架在坐位之間，要找到平衡十分困難。
這時， P教授用他多年玩蹺蹺板的經驗，一眼看出了他們現在坐的順序有一個性質：至少存在一個$0\leq x<\max(1,\lfloor{\frac{N}{2}}\rfloor)$，使得如果把最前面$x$個人和最後面$x$個人交換，那麼一定可以找到一個支點使得蹺蹺板平衡。所謂把最前面$x$個人和最後面$x$個人交換，指的是鏡像交換，例如若$x=2$，代表把座位編號為$0$和$N-1$上面的人交換、座位編號為$1$和$N-2$上面的人交換；若$x=0$，代表完全不交換。
P教授把這個性質告訴了這$N$個人，決定考驗他們能不能將蹺蹺板平衡。給你每個位置目前坐的人的體重，你能幫助他們找到正確的交換方式與支點的位置嗎？
Input Format
輸入第一行有一個正整數$N$。
接下來一行有$N$個正整數$a_0,a_1,\cdots ,a_{N-1}$，$a_i$代表編號$i$座位上面坐的人的體重。
本題共有五組測試資料。
第一組測試資料$N\leq 500$，$a_i\leq 500$，且保證不需要交換即可達成平衡（即$x=0$），共10分。
第二組測試資料$N\leq 500$，$a_i\leq 500$，共10分。
第三組測試資料$N\leq 5000$，$a_i\leq 5000$，共10分。
第四組測試資料$N\leq 200000$，$a_i\leq 20000$，共35分。
第五組測試資料$N\leq 20000000$，$a_i\leq 20000$，共35分。
Output Format
請輸出兩個非負整數，以一個空白隔開。
第一個數字是$x$，意義如題目所述；第二個數字$P$代表要把支點擺在編號$P$的座位下面。
如果有很多種平衡方法，請輸出$x$最小的那組解。
Sample Input 1
2 1 5 3 1
Sample Output 1
Sample Input 2
1 1 2 1 3 11
Sample Output 2
Hints
（雖然這是北市賽模擬，不過為了出這題，只好給大家用long long了(?)）
注意事項：
使用C++作答的同學，請在程式碼開頭加上#include<cstdio>，並利用scanf讀入資料。使用cin讀入資料可能會因為效率太差以致於程式執行時間超過限制。
scanf 常用的讀入方式如下：
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。
Problem Source
改編自Judge Girl 50087（2017年臺大資工系計算機程式設計第五週單班小考）。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 10 |
| 2 | 0~9 | 10 |
| 3 | 0~14 | 10 |
| 4 | 0~19 | 35 |
| 5 | 0~25 | 35 |