TopCoder

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

User's AC Ratio

87.4% (90/103)

Submission's AC Ratio

32.3% (183/567)

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

No. Testdata Range Score
1 0~4 10
2 0~9 10
3 0~14 10
4 0~19 35
5 0~25 35

Testdata and Limits

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