Problem : 44 - A game

Problem Statistics

Solved Member: 40　　Submission: 112　　User Tried: 45

Statement:

這是一個兩個人玩的遊戲，遊戲盤上放有一排正整數。

兩位玩家輪流玩。當輪到時，玩家就從這一排數字的最左端或最右端的二個數字中選擇一個。被選到的數字就從遊戲盤上除去。當所有數字都被選取除去後，遊戲就結束。如果第一個遊戲者所選取的數字總和跟第二位遊戲者所選取的數字總和一樣大或更大時，則第一個遊戲者就贏得勝利。

二位遊戲者一定做全局考量最好的選擇。

此遊戲由第一位遊戲者開始先選取。

假如此遊戲盤上一開始就有偶數個數字，則第一位遊戲者一定有一個必勝的策略，你要寫出策略的程式，好讓第一位遊戲者勝利。

請寫一個程式來計算第一位玩家(先拿者)的分數，以及第二位玩家的分數。

Input:Output:

第一行包含這個遊戲大小的起始值N，N是偶數且2<=N<=1000，接下來的N行中，每一行都有一個數字，代表著遊戲盤上的數字，排列次序為由左至右，每一個數字最大為10000。

輸出檔的第一行應有兩個數字，第一個數字是第一個遊戲者所選取的數字的總和，而第二個數字是第二位遊戲者所選取的數字的總和。

Sample Input:Sample Output:

6
4 7 2 9 5 2

18 11

HINT:

40%測資滿足：
2<=N<=100
每一個數字最大為200

Source:

IOI 1996

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	65536kb
1-1	1000ms	65536kb	10
1-2	1000ms	65536kb
1-3	1000ms	65536kb
1-4	1000ms	65536kb
2-1	1000ms	65536kb	10
2-2	1000ms	65536kb
2-3	1000ms	65536kb
2-4	1000ms	65536kb
3-1	1000ms	65536kb	10
3-2	1000ms	65536kb
3-3	1000ms	65536kb
3-4	1000ms	65536kb
4-1	1000ms	65536kb	10
4-2	1000ms	65536kb
4-3	1000ms	65536kb
4-4	1000ms	65536kb
5-1	1000ms	65536kb	10
5-2	1000ms	65536kb
6-1	1000ms	65536kb	10
6-2	1000ms	65536kb
7-1	1000ms	65536kb	10
7-2	1000ms	65536kb
8-1	1000ms	65536kb	10
8-2	1000ms	65536kb
9-1	1000ms	65536kb	10
9-2	1000ms	65536kb
10-1	1000ms	65536kb	10
10-2	1000ms	65536kb