Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2626
Polygon Game

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Polygon game is a game played by one person. At the beginning, there is a polygon of n vertexes. Every vertex is assigned a integer number, and each edge is assigned a operator eithor "+" or "*". Each edge is ordered from 1 to n.

The first step of the game is to delete a edge from the polygon. The following n-1 steps is operated as followed:
(1)Select an edge E(including the two vertexes connected by the edge V1 and V2);
(2)Replace the edge with a new vertex. The value of the vertex is the values of V1 and V2 operated by edge E.
The game is ended after all the edges are deleted; The score of the game is the integer value of the left vertex. Our goal is to get the highest score according to a given polygon.


The input will consist of a series of test cases. Each test case begins with a line of positive integer n, the number of edges of the polygon(3<=n<=50). And then the values of vertexes and operators of edges, in clockwise op[1],v[1],op[2],v[2],...,op[n],v[n], where op[i] represents the operator corresponding to the ith edge, and v[i] represents the value of the ith vertex. i=1,...,n. The value of each vertex is between -10 and 10. The input n = 0 denotes the end of the file.


For each case, just output one number: the largest value of the left vertex. One number per line.

Sample Input:
+ 3 + 4 * 2
+ 2 * 4 + 6 * 8
Sample Output:

Author: JIANG, Yongli
Source: ZOJ Monthly, November 2005
Submit    Status