Polígono (adaptado de OBI)

Polígono é um jogo individual que começa com N vértices, como no exemplo da Figura 1, onde N = 4. Cada vértice é rotulado com um número inteiro e cada aresta é rotulada ou com o símbolo + (adição) ou com o símbolo * (produto). As arestas são numeradas de 1 a N.

Figura 1. Representação gráfica de um polígono

Na primeira jogada, uma das arestas é removida. Jogadas seguintes envolvem os seguintes passos:

• escolha uma aresta E e dois vértices V₁ and V₂ que são ligados por E, e
• substitua E, V₁ e V₂ por um novo vértice, rotulado com o valor resultante da operação indicada por E sobre os valores V₁ and V₂.

O jogo termina quando não há mais arestas, e a sua pontuação é o rótulo do vértice remanescente.

Exemplo de jogo

Considere o polígono da Figura 1. O jogador iniciou o jogo removendo a aresta 3. O efeito da jogada é mostrado na Figura 2.

 
Figura 2. Removendo a aresta 3

 Continuando, o jogador escolheu a aresta 1,

 
Figura 3. Escolhendo a aresta 1

e, em seguida, a aresta 4,

 
Figura 4. Escolhendo a aresta 4

 e, finalmente, a aresta 2. A pontuação obtida é 0.

 
Figura 5. Escolhendo a aresta 2

1. Tarefa

Escreva um programa que dado um polígono compute a máximo valor possível para este polígono, conforme descrito acima. Também devem ser identificadas todas as arestas que se removidas no primeiro movimento conduz em o jogo a este valor.

2. Dados de Entrada

O arquivo POLYGON.IN descreve um polígono com N vértices. Ele contém duas linhas:

• A primeira linha contém o inteiro N;
• A segunda linha contém os rótulos das arestas 1, ..., N, intercalados com os rótulos dos vértices (primeiro o do vértice
  entre as arestas 1 e 2, depois o do vértice entre as arestas 2 e 3, e assim por diante, até o vértice entre as arestas N e 1), todos
  separados por um espaço.

Exemplo de entrada

4
+ -7 + 4 * 2 * 5

(Esta entrada corresponde ao exemplo da Figura 1. A segunda linha começa com o rótulo do vértice 1)

3. Dados de Saída

O arquivo POLYGON.OUT descreve a saída. Ele contém duas linhas:

• Na primeira linha do arquivo seu programa deve escrever a maior pontuação possível para o polígono dado como entrada;
• Na segunda linha seu programa deve escrever a lista de todas as arestas que, se removidas na primeira jogada, podem levar à pontuação máxima. As arestas devem ser escritas em ordem crescente, separadas por um espaço.

Exemplo de saída

33
1 2

(Esta saída corresponde ao exemplo de entrada acima)

4. Restrições

• 3 <= N <= 50
• Para qualquer sequência de jogadas, os rótulos dos vértices estão no intervalo [-32768,32767].