Zaphod Beeblebrox incumbiu Marvin de levar a tripulação da Coração de Ouro para um jantar no Restaurante no Fim do Universo. Para guiar a nave até o destino, Marvin precisará utilizar o gerador de improbabilidade infinita. Mas é necessário tomar muito cuidado com o gerador, pois mesmo um simples erro poderia transformar a nave em um vaso de petúnias ou em uma baleia.

O gerador de improbabilidade infinita é um dispositivo utilizado para cruzar distâncias interestelares. Ele é composto por um conjunto de circuitos geradores de eventos improváveis e é controlado por um painel com várias alavancas seletoras, que podem ser empurradas para cima ou para baixo. Cada circuito está conectado a algumas das alavancas e basta que uma delas esteja na posição correta para que o circuito seja ativado.

Por exemplo, suponha que um circuito esteja conectado a duas das alavancas e se ligue à saída de energia de cima da primeira alavanca e à saída de baixo da segunda. Nesse caso, o circuito será ativado se Marvin empurrar as duas alavancas para cima. O circuito também será ativado se ele empurrar as duas para baixo, ou se empurrar a primeira para cima e a segunda para baixo. De fato, a única maneira de desligar o circuito é empurrando a primeira alavanca para baixo e a segunda para cima.

Cada circuito está associado a um número inteiro maior ou igual a um, que é a improbabilidade do evento correspondente. A improbabilidade do evento criado pelo gerador de improbabilidade infinita é a soma dos pesos dos circuitos ativados. Quanto maior a improbabilidade do evento criado, mais improvável será o destino da nave (que é o que queremos, quando se trata de chegar no Restaurante no Fim do Universo!). Assim, Marvin deseja empurrar cada alavanca para cima ou para baixo de forma a maximizar a improbabilidade do evento criado.

Sendo um robô pelo menos 50 mil vezes mais inteligente que qualquer ser humano, Marvin poderia resolver esse problema rapidamente. Mas como ele tinha que imprimir os convites para o jantar, Zaphod Beeblebrox delegou a você, o novato da Coração de Ouro, a tarefa de criar um programa improbabilidade que resolva esse problema.

Sentindo-se levemente bondoso, Marvin explicou-lhe que cada solução corresponde a uma configuração possível das posições das alavancas. Assim, você pode enumerar todas as soluções utilizando um algoritmo recursivo e basta guardar a solução com maior improbabilidade. Porém, como o número de soluções é exponencial e há muitas alavancas, seria bom utilizar um algoritmo baseado em backtracking. Nessa técnica, ele continuou, podemos parar de explorar um certo caminho se soubermos que ele levará a uma solução com improbabilidade menor do que a da melhor solução já encontrada.

Outra dica, disse, é começar com uma solução razoavelmente boa antes de iniciar o algoritmo de backtracking. Marvin sugeriu computar a improbabilidade da solução com todas as alavancas empurradas para cima e da solução com todas as alavancas empurradas para baixo. Ele afirmou que pelo menos uma dessas duas soluções tem improbabilidade igual ou maior que metade do peso total dos circuitos, mas não esclareceu por quê, então você ainda precisa se convencer disso.

Finalmente, ele recomendou que primeiro você implementasse e testasse o algoritmo recursivo de enumeração e só depois se preocupasse em adicionar uma condição para evitar fazer chamadas recursivas. Além disso, ele avisou que deve haver diversas estratégias para otimizar o código e torná-lo mais rápido para esta tarefa, mas que era melhor começar com um algoritmo mais simples. Antes que você pudesse mostrar seu código ao Marvin, ele ficou entediado e perdeu o interesse, então é melhor que você procure um monitor para mostrar e conversar sobre seu programa.

Entrada

A primeira linha contém o número $c$ de circuitos e o número $a$ de alavancas. Cada uma das $c$ linhas seguintes contém a descrição de um circuito. Cada linha contém um inteiro $p$ indicando o peso do circuito, um inteiro $n$ indicando o número de alavancas a que o circuito se conecta e, para cada uma dessas alavancas, temos +x ou -x, dependendo se a alavanca de índice x deve estar para cima ou para baixo. Dica: para ler a descrição de uma alavanca, você pode utilizar uma especificação do scanf como " %c%d" ou parecida, ou então a função atoi que converte uma string para um inteiro.

7 4
1 2 -2 -3
2 2 -0 -3
2 3 +0 +2 +3
1 2 -0 -1
1 2 -0 +1
2 2 -0 +2
2 3 -0 +1 +3

Saída

A primeira linha da saída deve conter a improbabilidade máxima do evento criado. A segunda linha deve conter uma configuração das alavancas em ordem de índice que corresponde a essa improbabilidade. Cada alavanca de índice x será representada por +x ou -x, dependendo se ela deverá ser empurrada para cima ou para baixo. A sua configuração não precisa ser idêntica à dos arquivos de teste, desde que atinja o mesmo valor.

11
-0 -1 +2 -3

← Anterior Voltar