Đếm tất cả bộ ba có tổng bằng lập phương hoàn hảo trong C++

Cho mảng n số nguyên, nhiệm vụ là đếm tất cả các bộ ba (triplets) có tổng bằng một lập phương hoàn hảo (perfect cube).

Lập phương hoàn hảo là gì?

Là số bằng lập phương của một số nguyên: 1, 8, 27, 64, 125... Tổng bộ ba tối đa 15000, nên chỉ có 24 lập phương có thể (1³ đến 24³). Sử dụng quy hoạch động (DP) để tối ưu.

Ví dụ

Input - array[] = {5, 2, 18, 6, 3} Output - Number of Triplets = 1

Giải thích - 18+6+3 = 27 (3³). Không bộ ba nào khác.

Input - array[] = {1, 2, 3, 4, 5} Output - Number of Triplets = 2

Giải thích - 1+2+5=8 (2³), 1+3+4=8 (2³).

Phương pháp tiếp cận (Dynamic Programming)

• Tiền xử lý: arrd[i][j] = số lần giá trị j xuất hiện từ arr[0] đến arr[i]
• Duyệt tất cả cặp (i,j) với i < j
• Với mỗi lập phương k³ (k=1..24), tính rem = k³ - (arr[i]+arr[j])
• Nếu rem > 0, cộng thêm số lần rem xuất hiện sau vị trí j: arrd[n-1][rem] - arrd[j][rem]

Ví dụ code C++

#include <bits/stdc++.h>
using namespace std;

int arrd[1001][15001];

void compute(int ar[], int num) {
    for (int i = 0; i < num; ++i) {
        for (int j = 1; j <= 15000; ++j) {
            if (i == 0)
                arrd[i][j] = (j == ar[i]);
            else
                arrd[i][j] = arrd[i-1][j] + (ar[i] == j);
        }
    }
}

int countTriplets(int ar[], int num) {
    compute(ar, num);
    int ans = 0;
    for (int i = 0; i < num - 2; ++i) {
        for (int j = i + 1; j < num - 1; ++j) {
            for (int k = 1; k <= 24; ++k) {
                int cube = k * k * k;
                int rem = cube - (ar[i] + ar[j]);
                if (rem > 0)
                    ans += arrd[num-1][rem] - arrd[j][rem];
            }
        }
    }
    return ans;
}

int main() {
    int ar[] = {5, 2, 18, 6, 3};
    int num = sizeof(ar) / sizeof(ar[0]);
    cout << "Number of Triplets are= " << countTriplets(ar, num);
    return 0;
}

Kết quả

Number of Triplets are= 1