Разложить число на сумму не более, чем восьми кубов

Question

Дана следующая задача: есть число N (N <= 2 * 10 ^ 9), требуется разложить его на сумму не более, чем восьми кубов натуральных чисел (если это невозможно - вывести IMPOSSIBLE). Если есть несколько ответов - вывести любой. Я написала следующее:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector <long long> cubes, cubes2;
long long n, a, n1;
int f(int counter) {
    if (counter > 8) {
        return -1;
    }
    if (n <= 0) {
        return 1;
    }
    cubes.push_back((long long)cbrt(n));
    n -= pow((long long)cbrt(n), 3);
    f(counter += 1);
}
int f2(int counter) {
    if (counter > 8) {
        return -1;
    }
    if (n1 <= 0) {
        return 1;
    }
    if ((long long)cbrt(n1) - 1 < 2) {
        cubes2.push_back((long long)cbrt(n1));
        n1 -= pow((long long)cbrt(n1), 3);
    }
    else {
    cubes2.push_back((long long)cbrt(n1) - 1);
    n1 -= pow((long long)cbrt(n1) - 1, 3);
    }
    f2(counter += 1);
}
int main() {
    int j;
    cin >> n;
    n1 = n;
    f(0);
    f2(0);
    if (cubes.size() <= 8) {
        for (int i = 0; i < cubes.size(); i++) {
            cout << cubes[i] << " ";
        }
    }
    else if (cubes2.size() <= 8) {
        for (int i = 0; i < cubes2.size(); i++) {
            cout << cubes2[i] << " ";
        }
    }
    else {
        cout << "IMPOSSIBLE";
    }
}

Увы, это работает не всегда. Например, это не работает на числах 1079 и 79 - выводит IMPOSSIBLE, хотя это возможно. Для того, чтобы это работало, нужно как - то скомбинировать f и f2, поскольку, например, при разложении числа 1079 сначала должна сработать функция f, а потом всегда f2. Да, при разложении кубы могут повторяться, т.е. 17 раскладывается как 2 2 1. Так же необязательно выводить оптимальное разложение, например, для числа 9 приемлемым вариантом будет 2 1.

Answer 1

Кубов, которые могут участвовать в разложении, всего 1259. Предвычислим их и сложим в таблицу - теперь это просто слагаемые.

Для данного числа N найдём (например, бинарным поиском) максимальный возможный куб Q в таблице и попробуем решить задачу для меньшей размерности N-Q. Не получается - пройдём в цикле по меньшим кубам.

Таким образом, получится рекурсивная функция с аргументами N и Count (ограничение на 8). Если N равно нулю - нашли.

Решённые подзадачи можно складывать в словарь для оптимизации (подвид динамического программирования)

Answer 2

Перевел идеи MBo в код.

#include <stack>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

vector<int> cbs;

bool solve(int N, stack<int>& sol, int count, map<int, int>& no) {

    if (N == 0) return true;

    if (N != 0 && count == 0) return false;

    for (int i = cbs.size() - 1; i >= 0; --i) {

        if (cbs[i] > N) continue;

        if (cbs[i] == N) {
            sol.push(i + 1);
            return true;
            }

        if (no[N - cbs[i]] < count) {
            sol.push(i + 1);

            if (solve(N - cbs[i], sol, count - 1, no)) return true;
            else no[N - cbs[i]] = count;

            sol.pop();
            }
        }

    return false;
    }


int main() {
    for (int i = 1; i <= 1259; ++i) cbs.push_back(i * i * i);

    stack<int> sol;
    map<int, int> no;
    int N;
    cin >> N;

    if (solve(N, sol, 8, no)) {
        while (!sol.empty()) {
            cout << sol.top() << " ";
            sol.pop();
            }
        }
    else cout << "IMPOSSIBLE";

    cout << endl;
    }

Answer 3

У меня оно сдалось, когда я предпосчитал сумму пар кубов. Таким образом, уже на 6ти кубах будет известно разложится всё на 8 или нет. И рекомендуется использовать unordered_map.

#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long i64;

int n;

int m3 = 1260;  // maximum cube to be < 2e9
unordered_map<i64, pair<int, int>> cubes2;

bool rec(i64 s, int x, int k) {
    if (x * x * x > n || s > n) return false;

    if (cubes2.count(n - s)) {
        auto p = cubes2[n - s];
        if (p.first) cout << p.first << ' ';
        if (p.second) cout << p.second << ' ';
        return true;
    }

    if (k == 6) return false;

    if (rec(s, x + 1, k)) return true;

    if (rec(s + x * x * x, x, k + 1)) {
        cout << x << ' ';
        return true;
    }

    return false;
}


int main() {
    cin >> n;

    for (int x = 0; x < m3; x++) {
        for (int y = x; y < m3; y++) {
            i64 s = x * x * x + y * y * y;
            if (s > 2000000000) break;
            cubes2[s] = make_pair(x, y);
        }
    }
    
    if (!rec(0, 1, 0)) {
        cout << "IMPOSSIBLE";
    }
}

cubes2 - это unordered_map, ключ - это сумма пары кубов, значение - нужная пара кубов. Аргументы rec: s - набранная сумма, x - значит следующее число в разложении не менее x (к сумме добавится куб икса, если икс будет взят), k - сколько чисел набрали.

БЛОГ НА HUSL

Разложить число на сумму не более, чем восьми кубов

Ответы (3 шт):