# -*- coding: utf-8 -*-
####ID 30-coins

#### Άσκηση: Γράψτε μια συνάρτηση σε python:
####
####    def partitions(amount, coins)
####
#### όπου amount είναι ένας ακέραιος αριθμός και coins είναι μια λίστα διαφορετικών θετικών ακεραίων. Η λίστα coins
#### παριστάνει τα είδη των νομισμάτων που έχουμε διαθέσιμα και ο αριθμός amount παριστάνει το ποσό το οποίο θέλουμε
#### να παραστήσουμε με μια συλλογή από αυτά τα νομίσματα. Η συνάρτηση θα πρέπει να επιστρέφει με πόσους τρόπους μπορεί
#### το ποσό amount να γραφεί σαν άθροισμα ποσών από τη λίστα coins (διαφορετική σειρά γραφής των προσθετέων δε δημιουργεί
#### διαφορετικούς τρόπους παράστασης).
####
#### Για παράδειγμα, αν τα διαθέσιμα ποσά είναι 1, 2, 5 και θέλουμε να δημιουργήσουμε το ποσό 5 τότε υπάρχουν 4 τρόποι
#### να το κάνουμε αυτό:
####
####  5  1+1+1+1+1  1+2+2  1+1+1+2.
####
#### Αν amount <= 0 ή αν η λίστα coins είναι κενή τότε η συνάρτησή σας θα πρέπει να επιστρέφει 0. 
####
#### Γράφετε τον κώδικά σας αποκλειστικά ανάμεσα στις γραμμές START και STOP παρακάτω.
#### Δεν πρέπει να πειράξετε καθόλου τις υπόλοιπες γραμμές
####
#### Για να τρέξετε το πρόγραμμά σας (αποθηκευμένο στο αρχείο user.py) δίνετε την εντολή
####
####    python user.py

#############################################################################
#### ΔΕΝ ΠΡΕΠΕΙ να υπάρχουν εντολές print ή input στο πρόγραμμά σας παρακάτω.
#############################################################################

#### Μην αλλάξετε ό,τι είναι από την επόμενη γραμμή και πάνω
####START Από δω και κάτω γράφετε το πρόγραμμά σας.--------------------------

def partitions(amount, coins):
    C = sorted(coins, reverse=True)
    if amount == 0:
        return 1
    elif amount < 0:
        return 0
    elif len(C) == 0:
        return 0
    else:
       return partitions(amount-C[0], C) + partitions(amount, C[1:])

####STOP Μην αλλάξετε ό,τι είναι από τη γραμμή αυτή και κάτω----------------
Amount = int(raw_input("Please give the amount: "))
Coins = input("Please gibe the list of coins (different, positive integers): ")
print "input = %r\noutput = %r" % ((Amount, Coins), partitions(Amount, Coins))