# version "programmation dynamique" de l'algorithme de rendu de pièces de monnaie, avec memoisation
# type:ignore
def rendu_dynamique(z,n):
    if z==0:
        return []
    if n==0 or z<P[0]:
        return L
    if z<P[n-1]:
        return rendu_dynamique(z,n-1)
    R1=[P[n-1]]+rendu_dynamique(z-P[n-1],n)
    R2=rendu_dynamique(z,n-1)
    if len(R1)<=len(R2):
        if show:
            print("G",end='')
        return R1
    else:
        if show:
            print("D",end='')
        return R2


def memoize(f):
    memo={}
    def helper(z,n):
        if (z,n) not in memo:            
            memo[z,n]=f(z,n)
        return memo[z,n]
    return helper


from time import *
show=0
L=[0]*1000
P=[2,5,10,20,50,100,200]
z=int(input("Montant à rendre: "))
rendu_dynamique=memoize(rendu_dynamique)
t0=time()
R=rendu_dynamique(z,len(P))
t=time()-t0
if show:
    print("")
if sum(R)==z:
    print("Pièces rendues:",R)
else:
    print("Rendu exact impossible!")
print("Temps de calcul:",t,"secondes")