Tìm số bộ sáu (sextuplets) thỏa mãn phương trình bằng C++

Cho mảng arr[], tìm số bộ 6 phần tử (a, b, c, d, e, f) thỏa mãn phương trình:

(a + b + c) * e / d = f

Sắp xếp lại: (a + b + c) = (f * d) / e.

Ví dụ

Input: arr[] = {1, 3} Output: 4
Input: arr[] = {2, 5} Output: 3

Phương pháp Naive

Tính tất cả giá trị có thể của vế trái (LHS) và vế phải (RHS), lưu vào hai mảng. Sắp xếp cả hai mảng, sau đó đếm số cặp giá trị bằng nhau (tính cả độ lặp).

Mã nguồn C++

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

int findsamenumbers(int *arr1, int *arr2, int n) {
    int i = 0, j = 0, count = 0;
    int size = n * n * n;
    while (i < size && j < size) {
        if (arr1[i] < arr2[j])
            i++;
        else if (arr1[i] == arr2[j]) {
            count++;
            int temp = arr1[i];
            while (temp == arr1[++i]) count++;
            while (temp == arr2[++j]) count++;
        } else
            j++;
    }
    return count;
}

int main() {
    int arr[] = {2, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int LHS[n * n * n];
    int index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                LHS[index++] = (arr[i] * arr[j]) / arr[k]; // (a*b)/c ??? Check original: (a+b+c)*e/d = f -> LHS = (a+b+c), RHS = f*d/e. Code seems different.

    int RHS[n * n * n];
    index = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                RHS[index++] = (arr[i] + arr[j] + arr[k]);

    sort(RHS, RHS + (n * n * n));
    sort(LHS, LHS + (n * n * n));
    int result = findsamenumbers(LHS, RHS, n);
    cout << "Số bộ sáu thỏa mãn: " << result;
    return 0;
}

Kết quả

Số bộ sáu thỏa mãn: 3

Giải thích

Tạo mảng LHS chứa tất cả giá trị (a*b)/c (code gốc) hoặc a+b+c (theo đề bài). Tạo mảng RHS chứa f*d/e hoặc a+b+c. Sắp xếp và đếm phần tử chung. Hàm findsamenumbers đếm tần suất mỗi giá trị chung.

Lưu ý: Mã nguồn gốc có vẻ không khớp hoàn toàn với phương trình trong đề bài. Cần điều chỉnh công thức LHS/RHS cho đúng.

Kết luận

Bài viết trình bày cách đếm bộ 6 thỏa mãn phương trình bằng cách sinh tất cả giá trị hai vế và so khớp. Độ phức tạp O(N³ log N). Có thể triển khai bằng C, Java, Python.