# Mohó algoritmus az érmék minimális számának megtalálásához

def moho_cimletezes(osszeg):
    cimletek=[1,2,5,10,20,50,100,500,1000]
    cimlet_db={
        1:0,2:0,5:0,10:0,
        20:0,50:0,100:0,
        500:0,1000:0
    }
    felhasznalt_cimletek = []
    i=-1
    while i>=-len(cimletek):            # negatív index: visszafelé haladunk
        while osszeg>=cimletek[i]:      # keressük a lehető legnagyobb címletet
            osszeg-=cimletek[i]         # csökkentjük vele az összeget
            felhasznalt_cimletek.append(cimletek[i]) # elhelyezzük a listánkban
            cimlet_db[cimletek[i]]+=1   # a felhasznált címlet darabszámát növeljük
        i-=1    #index csökkentése (azaz balra lépés a címleteken)

    for i in range(len(felhasznalt_cimletek)):
        print(felhasznalt_cimletek[i], end=' ')
    print('\nDarabra:')
    for c, db  in reversed(cimlet_db.items()): #.items(): dict key és value együtt
        if db!=0:
            print(c,':',db)
    

# >>>>>>>>>>>>>>>>>> F Ő M O D U L >>>>>>>>>>>>>>>>>>>
if __name__ == '__main__':
    valtando=int(input('A cimletezendő összeg: '))
    print('A megadott összeg minimális cimletezése:')
    moho_cimletezes(valtando)