TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

86.6% (84/97)

Submission's AC Ratio

30.9% (169/547)

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:
5
2 1 5 3 1

輸入範例2:
6
1 1 2 1 3 11

Sample Output

輸出範例1:
0 2

輸出範例2:
2 1

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

For Testdata: 0 ~ 4, Score: 10
For Testdata: 0 ~ 9, Score: 10
For Testdata: 0 ~ 14, Score: 10
For Testdata: 0 ~ 19, Score: 35
For Testdata: 0 ~ 25, Score: 35
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 262144 262144
1 5000 262144 262144
2 5000 262144 262144
3 5000 262144 262144
4 5000 262144 262144
5 5000 262144 262144
6 5000 262144 262144
7 5000 262144 262144
8 5000 262144 262144
9 5000 262144 262144
10 5000 262144 262144
11 5000 262144 262144
12 5000 262144 262144
13 5000 262144 262144
14 5000 262144 262144
15 5000 262144 262144
16 5000 262144 262144
17 5000 262144 262144
18 5000 262144 262144
19 5000 262144 262144
20 3900 262144 262144
21 3900 262144 262144
22 3900 262144 262144
23 3900 262144 262144
24 3900 262144 262144
25 3900 262144 262144