Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Problem 1: A Game 
发信站: 哈工大紫丁香 (2002年03月29日13:54:14 星期五), 站内信件

IOI'96 Day 1
Problem 1: A Game
Consider the following two-player game. The game board consists of a sequenc
e of positive integers. The two players move alternately. When a player move
s, he selects a number from either the left or the right end of the sequence
. The selected number is deleted from the board. The game is over when all n
umbers have been selected. The first player wins if the sum of the numbers h
e has selected is at least as much as selected by the second player. The sec
ond player plays his best.
The first player starts the game.
If the board initially contains an even number of elements, then the first p
layer has a winning strategy. You are to write a program that implements the
 strategy of the first player to win the game. The second player's response 
is provided by a given computer program. The two players communicate with th
ree procedures of the module Play that is made available to you. These proce
dures are StartGame, MyMove and YourMove. The first player should initiate t
he game by executing the parameterless procedure StartGame. If the first pla
yer selects a number from the left end, he executes the procedure MyMove('L'
). Similarly, executing the instruction MyMove('R') sends a message to the s
econd player indicating that the first player has selected a number from the
 right end. The second player, i.e. the machine moves immediately, and the f
irst player can learn this move by executing the instruction YourMove(C), wh
ere C is a character type variable(in C/C++ you write this as YourMove(&C)).
 The value of C is 'L' or 'R' depending on whether the selection has been ma
de either from the left or the right end.
　
Input Data
The first line of file INPUT.TXT contains the size N of the initial board. N
 is even and 2<=N<=100. The remaining N lines contain one number in each lin
e, the contents of the initial board in left to right order. Each number is 
at most 200.
　
Output Data
When the game is over, your program should write the final result of the gam
e to the file OUTPUT.TXT. The file contains two numbers in the first line. T
he first number is the sum of the numbers selected by the first player and t
he second number is the sum of the numbers selected by the second player. Yo
ur program must play a game and the output must correspond to the game playe
d.
　
Example Input and Output
Figure 1 gives an input file containing an initial board description and a p
ossible output file.
　
----------------------------------------------------------------------------
----
INPUT.TXT
6
4
7
2
9
5
2
OUTPUT.TXT
15 14

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]