Минимальное количество квадратных чисел
Дано целое число
n. Нужно найти такое минимальное количество квадратных чисел (1, 4, 9, 16, 25, 36 и т.д.), которые в сумме дают n. Сколько таких чисел вам понадобится?Входные данные
На вход подается одно целое число
n (1 ≤ n ≤ 60000).Выходные данные
Необходимо вывести минимальное количество квадратных чисел, которые суммируются до
n.Примеры
Input | Output |
344 | 3 |
Пояснение
Constraints
Time limit: 9 seconds
Memory limit: 512 MB
Output limit: 1 MB