Numero minimo di quadrati perfetti
Dato un intero
n, è richiesto di trovare il minor numero possibile di quadrati perfetti (1, 4, 9, 16, 25, 36, ecc.) che, sommati tra loro, diano come risultato n. Quanti quadrati perfetti useresti?Dati in ingresso
L’input contiene un singolo intero
n (1 ≤ n ≤ 60000).Dati in uscita
Il programma deve stampare il numero minimo di quadrati perfetti scelti.
Esempi
Ingresso | Uscita |
344 | 3 |
Spiegazione
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB