{
Solution for task GAME
-------- --- ---- ----
The following simple observation leads to a solution of the task:
Since the game board initially contains an even number of elements arranged
in a sequence, when the first player moves one end of the sequence is in odd
and the other end is in even position. Therefore the first player can always
select element either from odd or even position.
The algorithm pre-process the contents of the initial board before staring the
game to compute the values OddSum and EvenSum, the sum of the elements in odd
positions and the sum of the elements in even positions, respectively.
If OddSum>=EvenSum then the first player always selects from odd position
and force the second player to select from even position. The case
OddSum=EvenSum;
End {Preprocess};
Procedure Playing;
{ Global input variable: N, Board, Odds }
{ Global output variable: Sel }
Var M,i:Word;
C1, { move of the first player }
C2:Char; { move of the second player }
Head, { position of the left end of the board }
Tail:1..MaxN; { position of the right end of the board }
Begin
Sel:=0;
Head:=1; Tail:=N;
M:=N Div 2; { number of moves for one player}
For i:=1 To M Do Begin
If Odds Then Begin {select from the odd position}
If Odd(Head) Then Begin
Sel:=Sel+Board[Head];
Inc(Head);
C1:='L';
End Else Begin
Sel:=Sel+Board[Tail];
Dec(Tail);
C1:='R';
End;
End Else Begin {select from the even position}
If Odd(Head) Then Begin
Sel:=Sel+Board[Tail];
Dec(Tail);
C1:='R';
End Else Begin
Sel:=Sel+Board[Head];
Inc(Head);
C1:='L';
End;
End {Odd-Even};
MyMove(C1); { perform the move }
YourMove(C2); { obtain the second player's move }
If C2='L' Then Inc(Head)
Else Dec(Tail);
End{For i};
End;
Procedure WriteOut;
Var OutFile: Text;
Begin
Assign(OutFile,'output.txt'); Rewrite(OutFile);
WriteLn(OutFile,Sel,' ',Sum-Sel);
Close(OutFile);
End;
Begin { Program }
ReadInput;
Preprocess;
StartGame;
Playing;
WriteOut;
End.
{Scientific Committee IOI'96}