Polygon is a game for one player that starts on a polygon with N vertices, like the one in Figure 1, where N=4. Each vertex is labelled with an integer and each edge is labelled with either the symbol + or the symbol * . The edges are numbered from 1 to N. On the first move, one of the edges is removed. Subsequent moves involve the following steps: pick an edge E and the two vertices V1 and V2 that are linked by E; and replace them by a new vertex, labelled with the result of performing the operation indicated in E on the labels of V1 and V2. The game ends when there are no more edges, and its score is the label of the single vertex remaining. Consider the polygon of Figure 1. The player started by removing edge 3. After that, the player picked edge 1, then edge 4, and, finally, edge 2. The score is 0. Write a program that, given a polygon, computes the highest possible score and lists all the edges that, if removed on the first move, can lead to a game with that score.
Polygon is a game for one player that starts on a polygon with N vertices, like the one in Figure 1, where N=4. Each vertex is labelled with an integer and each edge is labelled with either the symbol + (addition) or the symbol * (product). The edges are numbered from 1 to N. On the first move, one of the edges is removed. Subsequent moves involve the following steps: pick an edge E and the two vertices V1 and V2 that are linked by E; and replace them by a new vertex, labelled with the result of performing the operation indicated in E on the labels of V1 and V2. The game ends when there are no more edges, and its score is the label of the single vertex remaining. Consider the polygon of Figure 1. The player started by removing edge 3. After that, the player picked edge 1, then edge 4, and, finally, edge 2. The score is 0. Write a program that, given a polygon, computes the highest possible score and lists all the edges that, if removed on the first move, can lead to a game with that score.
