Coin change

Dato un sistema monetario composto da n monete, ognuna con un valore positivo , si richiede di ottenere una somma totale x utilizzando il minor numero possibile di monete.

Per esempio, se i valori delle monete sono e vogliamo ottenere 11, la scelta ottimale sarebbe 1 + 5 + 5 ⇒ 3 monete.

Input

La prima riga dell’input contiene due interi n (1 ≤ n ≤ 100) e x (1 ≤ x ≤ ).

La riga successiva contiene n interi separati da spazio (1 ≤ ≤ ).

Output

Il programma deve stampare il numero minimo di monete necessario per ottenere x. Se non è possibile formare la somma desiderata, il programma deve stampare -1.

Esempi

Ingresso	Uscita
3 11 1 5 7	3
3 12 1 5 7	2

Spiegazione

11 → 1 + 5 + 5
12 → 5 + 7

Tutorial

Notate che la strategia Greedy, cioè prendere sempre la moneta più grande possibile, non funziona. Il primo esempio lo mostra chiaramente. Se vogliamo ottenere 11 e prendiamo prima la moneta da 7, ci resta 4 da formare, per cui servono quattro monete da 1, arrivando a 5 monete totali. La vera soluzione, invece, ne richiede solo 3 (5 + 5 + 1).

Definiamo uno stato d[i], che rappresenta il numero minimo di monete richiesto per formare la somma i. Se inizializziamo e aggiorniamo correttamente il vettore d fino a x, la risposta definitiva sarà proprio d[x].

All’inizio possiamo impostare tutti i valori di d a infinito (che significa “non è possibile formare tale somma”) eccetto d[0], che è 0 (ottenibile con 0 monete):

c = [...]
x = ...
d = [0] + [float('inf')] * x      # d[0] è 0 e d[1...x] è inizialmente infinito

Poi, per ogni valore da 1 a x, proviamo a determinare il numero minimo di monete necessario per ottenerlo. Se stiamo considerando un certo valore num, testiamo tutte le monete possibili per vedere se possiamo arrivare a num sommando il valore della moneta a uno stato già noto (num - ). Se migliora (ossia riduce) la quantità di monete necessarie, aggiorniamo d[num]. Quindi, per ogni num da 1 a x, valutiamo tutti i precedenti stati possibili e proviamo a migliorare d[num]:

for num in range(1, x + 1):       # Itera su tutti i numeri da 1 a x
    for ci in c:                  # Tenta di migliorare d[num] con tutte le monete
        if num - ci >= 0:         # Se è possibile ottenere num con la moneta ci
            d[num] = min(d[num], d[num - ci] + 1)
print(d[x])

d[num] = min(d[num], d[num - ci] + 1) è il centro della soluzione. A ogni iterazione cerchiamo di migliorare d[num] se è possibile farlo via num - . In sostanza, prendiamo il numero minimo di monete necessario per formare num - e aggiungiamo 1 per usare la moneta .

Al termine dell’elaborazione di tutti i numeri con tutte le monete, la risposta è semplicemente il valore di d[x].

Simuliamo l’algoritmo sull’esempio:

c = [1, 5, 7] e x = 11

d = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
num = 1 (cerchiamo di migliorare il numero di monete per la somma 1)
ci = 1 ⇒ d[1] = d[0] + 1 = 1 ⇒ d = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ num - ci < 0
ci = 7 ⇒ num - ci < 0
num = 2 (cerchiamo di migliorare il numero di monete per la somma 2)
ci = 1 ⇒ d[2] = d[1] + 1 = 2 ⇒ d = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ num - ci < 0
ci = 7 ⇒ num - ci < 0
num = 3 (cerchiamo di migliorare il numero di monete per la somma 3)
ci = 1 ⇒ d[3] = d[2] + 1 = 3 ⇒ d = [0, 1, 2, 3, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ num - ci < 0
ci = 7 ⇒ num - ci < 0
num = 4 (cerchiamo di migliorare il numero di monete per la somma 4)
ci = 1 ⇒ d[4] = d[3] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ num - ci < 0
ci = 7 ⇒ num - ci < 0
num = 5 (cerchiamo di migliorare il numero di monete per la somma 5)
ci = 1 ⇒ d[5] = d[4] + 1 = 5 ⇒ d = [0, 1, 2, 3, 4, 5, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ d[5] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, ∞, ∞, ∞, ∞, ∞, ∞]
ci = 7 ⇒ num - ci < 0
num = 6 (cerchiamo di migliorare il numero di monete per la somma 6)
ci = 1 ⇒ d[6] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, ∞, ∞, ∞, ∞, ∞]
ci = 5 ⇒ non aggiorna
ci = 7 ⇒ num - ci < 0
num = 7 (cerchiamo di migliorare il numero di monete per la somma 7)
ci = 1 ⇒ d[7] = d[6] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 3, ∞, ∞, ∞, ∞]
ci = 5 ⇒ non aggiorna
ci = 7 ⇒ d[7] = d[0] + 1 = 1 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, ∞, ∞, ∞, ∞]
num = 8 (cerchiamo di migliorare il numero di monete per la somma 8)
ci = 1 ⇒ d[8] = d[7] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, ∞, ∞, ∞]
ci = 5 ⇒ non aggiorna
ci = 7 ⇒ non aggiorna
num = 9 (cerchiamo di migliorare il numero di monete per la somma 9)
ci = 1 ⇒ d[9] = d[8] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, ∞, ∞]
ci = 5 ⇒ non aggiorna
ci = 7 ⇒ non aggiorna
num = 10 (cerchiamo di migliorare il numero di monete per la somma 10)
ci = 1 ⇒ d[10] = d[9] + 1 = 4 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, ∞]
ci = 5 ⇒ d[10] = d[5] + 1 = 2 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, ∞]
ci = 7 ⇒ non aggiorna
num = 11 (cerchiamo di migliorare il numero di monete per la somma 11)
ci = 1 ⇒ d[11] = d[10] + 1 = 3 ⇒ d = [0, 1, 2, 3, 4, 1, 2, 1, 2, 3, 2, 3]
ci = 5 ⇒ non aggiorna
ci = 7 ⇒ non aggiorna
print(d[11]) ⇒ stampa 3

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB