IL
опечатка
Size: a a a
2020 October 02
IL
простите
k
ну и вроде по какой-то теореме там не больше 4 слагаемых будет
С
На последнем собесе
Мне тоже на последнем собесе в такси ее дали. Я начал вспоминать алгебру и уходить в комплексные числа
С
ну и вроде по какой-то теореме там не больше 4 слагаемых будет
Вот вот
IL
ну я оптимизированный перебор лишь придумал, ибо ничего не знал(да и не знаю)
С
Я так и не понял, зачем эта задача
k
оптимизированный - это за сколько?
IL
оптимизированный - это за сколько?
не помню
IL
но я предложил перебор с парой эвристик которые заведомо плохие варианты отсекают
IL
но все еще медленно и плохо
IL
за 20 минут лучше не придумал
k
ну если 4 вложенных цикла до корня(n), то за квадрат как раз найдется разложение
k
ну оно даже быстрее будет, но мне тяжко считать
ЕЗ
Ну очевидно же что динамикой за линию можно)
С
Ну очевидно же что динамикой за линию можно)
Тоже ведь квадрат
DD
Хотя и сейчас сходу я вряд ли придумаю решение
А как бы ты решал?
А как бы ты решал?
ну, первое, что пришло в голову:
while (n != 0) {
const unsigned x = sqrt(n);
std::cout << x << ' ';
n -= x * x;
}
while (n != 0) {
const unsigned x = sqrt(n);
std::cout << x << ' ';
n -= x * x;
}
С
ну, первое, что пришло в голову:
while (n != 0) {
const unsigned x = sqrt(n);
std::cout << x << ' ';
n -= x * x;
}
while (n != 0) {
const unsigned x = sqrt(n);
std::cout << x << ' ';
n -= x * x;
}
Не факт, что будет минимум
IL
ну если 4 вложенных цикла до корня(n), то за квадрат как раз найдется разложение
попытался поискать код который написал после, но толком не нашел
IL
но примерно такая идея и была