Problema da porção do amor

From AdonaiMedrado.Pro.Br
Jump to: navigation, search
Problema adaptado de MakingPotions do TopCoder.

Dificuldade única

Uma bruxa deseja fazer uma porção do amor com o menor custo possível. Para executar esta tarefa ela combina diversas porções de um livro de receitas que possui fórmulas no seguinte formato:

S=I0S0+...+InSn

Onde:

  • I0...In são números inteiros positivos entre 1 e 9 (apenas um dígito).
  • S0...Sn são nomes de porções ou ingredientes.
  • S é a porção resultante.
  • todos os nomes de ingredintes/porções estão em letras minúsculas.

Pode haver mais de uma forma de fazer uma porção, neste caso pode-se usar qualquer uma delas.

Os ingredientes podem ser comprados no mercado a um custo.

Faça um programa para auxiliar a bruxa nesta tarefa. O programa deve receber as seguintes informações de entrada:

  1. um número inteiro N (0<=N<=100) com o número de ingredientes disponíveis no mercado.
  2. N ingredientes, um por linha com no máximo 100 caracteres cada.
  3. N inteiros positivos, um por linha com valores entre o limite fechado de 1 e 100.
  4. um número inteiro K (1<=K<=100) com o número de formulas disponíveis.
  5. K formulas, uma por linha com no máximo 1000 caracteres cada.

A saída deverá ser o menor custo possível para se obter a porção do amor.