E06 - Reverse Alchemying

Le problème

Reverse Alchemying

Indices

• Une solution qui utilise la récursivité est facile à écrire.

Solution

🐍 Script Python

"""
author: Franck CHAMBON
problem: https://prologin.org/train/2013/semifinal/reverse_alchemying
"""

nb_ingredients, nb_recettes = map(int, input().split())

recettes = dict()
for _ in range(nb_recettes):
    numeros = tuple(map(int, input().split()))
    recettes[numeros[0]] = numeros[1:]

ingredients = [input() for _ in range(nb_ingredients)]

def affiche(id_produit: int) -> None:
    if id_produit in recettes:
        for id_sous_produit in recettes[id_produit]:
            affiche(id_sous_produit)
        print(ingredients[id_produit], end=" = ")
        ingredients_produit = (ingredients[i] for i in recettes[id_produit])
        print(" + ".join(ingredients_produit))

affiche(0)
# récursivement, affiche avant les ingrédients nécessaires avec leur formule

# et les produits de base
for id_produit in range(nb_ingredients):
    if id_produit not in recettes:
        print(ingredients[id_produit], end=" ")
# Il y aura une espace à la fin en trop, mais le juge accepte cela, ici.