Número mínimo de quadrados perfeitos
Dado um inteiro
n, pretende-se encontrar o menor número possível de quadrados perfeitos (1, 4, 9, 16, 25, 36, etc.) cuja soma seja igual a n. Quantos quadrados perfeitos escolherias?Entrada
A entrada contém um único inteiro
n (1 ≤ n ≤ 60000).Saída
O programa deve imprimir o número mínimo de quadrados perfeitos que escolherias.
Exemplos
Entrada | Saída |
344 | 3 |
Explicação
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB