Minimale Anzahl perfekter Quadratzahlen
Gegeben ist eine ganze Zahl
n. Die Aufgabe besteht darin, so wenige perfekte Quadratzahlen (1, 4, 9, 16, 25, 36 usw.) wie möglich zu finden, deren Summe genau n ergibt. Wie viele dieser Quadratzahlen würden Sie wählen?Eingabe
Die Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 60000).Ausgabe
Das Programm soll die minimale Anzahl perfekter Quadratzahlen ausgeben, die zur Summe
n beitragen.Beispiele
Eingabe | Ausgabe |
344 | 3 |
Erklärung
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB