IL
но без 4 циклов, так как про теорему не знал
Size: a a a
2020 October 02
ЕЗ
Тоже ведь квадрат
Самая примитивная динамика будет за N sqrt N работать. Но учитывая, что слагаемых не больше 4х будет, можно за линию. Достаточно посчитать вспомогательную динамику dp[x] = можно ли разложить в сумму двух квадратов.
DD
Не факт, что будет минимум
тогда dp-шку надо мутить
С
Самая примитивная динамика будет за N sqrt N работать. Но учитывая, что слагаемых не больше 4х будет, можно за линию. Достаточно посчитать вспомогательную динамику dp[x] = можно ли разложить в сумму двух квадратов.
Как вычислить dp[x] без дополнительного перебора?
ЕЗ
Так перебор за линию же работать будет
for i = 1 .. sqrt(N) for j = 1 .. sqrt(N) dp[i*i+j*j]=true
for i = 1 .. sqrt(N) for j = 1 .. sqrt(N) dp[i*i+j*j]=true
С
Так перебор за линию же работать будет
for i = 1 .. sqrt(N) for j = 1 .. sqrt(N) dp[i*i+j*j]=true
for i = 1 .. sqrt(N) for j = 1 .. sqrt(N) dp[i*i+j*j]=true
А точняк, там же до корня)
С
А я мутил 4 цикла (
IL
А я мутил 4 цикла (
Век живи, век учись!
IL
До сих пор учусь фишкам решения подобного рода задач, не особо эффективно правда
A
Тебя бы забанил )
За обзывание нейронкой.
За обзывание нейронкой.
Типа, «ты кого нейронкой назвал, кожаный мешок?!». Чую, уже совсем немного осталось, будет кибертолерантность, Neuron Lives Matters и вот это вот всё... 😆
ДС
все мы нейронки
ДС
просто веса аналоговые а не дискретные
v
Дмитрий Сураев
все мы нейронки
Тогда просто выведут термин "искусственная нейронная сеть")
R
Так перебор за линию же работать будет
for i = 1 .. sqrt(N) for j = 1 .. sqrt(N) dp[i*i+j*j]=true
for i = 1 .. sqrt(N) for j = 1 .. sqrt(N) dp[i*i+j*j]=true
но ведь даже для числа в 1М это даст 298797 элементов
R
в чем суть dp если на числа в районе 1 миллиарда потребуется занять всю память?
ДС
Тогда просто выведут термин "искусственная нейронная сеть")
ИНС vs ННС
AK
столько сообщений, началися раик?
O
Нет(
ДС
нене точно не начился, не беспокойся пожалуйста
IL
столько сообщений, началися раик?
я лично тебе напишу когда начнется