SB
Хотя подраздел задач тот же
Size: a a a
2020 March 05
IZ
Можете помочь плиз с алгоритмом? Это задача несложная, надо решить за час, но я до конца не понимаю. Ну очевидно цикл от 0 до n, внутри его цикл по квадратам от 0 до i. Правда это очень медленно работает и не совсем понятно что делать с этими квадратами(
Надо же с больших начинать, нет?
SB
Надо же с больших начинать, нет?
Не знаю, я тупой
SB
Наверное да
SB
Но как там квадраты то взять?
SB
У больших
SB
А как эту задачу можно привести к какой-нибудь популярной задаче с уже имеющимся алгоритмом?
A
ну то есть надо число разбить на сумму квадратов. Можно попытаться сделать это жадным образом, но я не уверен, что жадный даст минимум. Но контрпример сходу придумать не могу
SB
ну то есть надо число разбить на сумму квадратов. Можно попытаться сделать это жадным образом, но я не уверен, что жадный даст минимум. Но контрпример сходу придумать не могу
Да, это и есть
SB
Число разбить на сумму квадратов, да так чтобы кол-во квадратом было наименьшим
A
https://www.geeksforgeeks.org/minimum-number-of-squares-whose-sum-equals-to-given-number-n/ - первый результат в гугле
A
делают полным обходом всех вариантов.
SB
делают полным обходом всех вариантов.
На 10 в 5 не ляжет?
A
там мемоизация работает полным ходом и перебирать надо не так много вариантов на самом деле
K
Вроде как была формула, когда 2 и 3, а максимум возможно 4
A
плюс можно делать раннее отсечение, если знаешь минимум
K
Для 2 даже могу вспомнить
A
то есть если сразу смог найти в 4, то более длинные с этого момента просто игнорируешь
A
вон там по ссылке в решениях есть
if (n <= 3)
return n;
if (n <= 3)
return n;
A
а, не, n это число просто.