# version "gloutonne" de l'algorithme de rendu de pièces de monnaie, avec illustration des étapes intermédiaires
# type:ignore
def rendu_glouton(z,n):
    if show:
        print("Montant:",z,", Pièces:",P[0:n])
    if z==0:
        return []
    if n==0 or z<P[0]:
        print("Rendu exact impossible!")
        return []
    if z<P[n-1]:
        return rendu_glouton(z,n-1)
    return [P[n-1]]+rendu_glouton(z-P[n-1],n)


show=1
P=[1,2,5,10,20,50]
z=int(input("Montant à rendre: "))
if show:
    print("Etapes intermédiaires:")
R=rendu_glouton(z,len(P))
print("Pièces rendues:",R)