Chương trình C++ cân bằng cái cân bằng các trọng lượng là lũy thừa của một số

Đề bài - Cân bằng cái cân bằng các trọng lượng là lũy thừa của một số.

Mô tả - Cho một cái cân lưỡng bàn. Cho trọng lượng T và một số trọng lượng khác có giá trị là lũy thừa của một số a. Cần cân bằng hai đĩa cân bằng các trọng lượng cho trước.

Dựa trên đó ta có phương trình:

T + (một lũy thừa của a) = (một lũy thừa khác của a)

Lưu ý: Chỉ có đúng một trọng lượng tương ứng với một giá trị lũy thừa.

Ví dụ

T = 12, a = 4

Sử dụng các giá trị dưới, ta cân bằng được như sau:

12 + 4 = 16

Để giải bài toán, cần biểu diễn T dưới dạng lũy thừa của a. Đổi cơ số của T từ cơ số 10 sang cơ số a.

TRƯỜNG HỢP 1 - Sau khi đổi cơ số, nếu biểu diễn chỉ có 1 và 0. Thì các trọng lượng ở vị trí 1 có thể dùng để cộng tạo thành giá trị T.

Ví dụ: T = 10, a = 3. Đổi cơ số 10 sang 3 được 101. Ta dùng 3⁰ và 3² (1 + 9) = 10.

TRƯỜNG HỢP 2 - Nếu biểu diễn có các giá trị khác 0, 1. Điều kiện bắt buộc để có giải là biểu diễn cơ số có chữ số (a - 1). Lúc này, chuyển lũy thừa đó sang phía T và tăng chữ số trong biểu diễn cơ số lên 1.

Ví dụ: T = 7, a = 3. Đổi cơ số 7 sang 3 được 021. Chuyển 3¹ sang phía T và tăng phía kia lên 1. Ta được số 10 biểu diễn là 101 (9 + 1). Có thể cân bằng.

Dựa trên các trường hợp trên, viết chương trình giải bài toán.

Ví dụ mã nguồn

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

bool isBalancePossible(int T, int a) {
    vector<int> baseForm;
    while (T) {
        baseForm.push_back(T % a);
        T /= a;
    }
    baseForm.push_back(0);
    for (int i = 0; i < baseForm.size(); i++) {
        if (baseForm[i] != 0 && baseForm[i] != 1 && baseForm[i] != (a - 1) && baseForm[i] != a)
            return false;
        if (baseForm[i] == a || baseForm[i] == (a - 1))
            baseForm[i + 1] += 1;
    }
    return true;
}

int main() {
    int T = 21;
    int a = 4;
    if (isBalancePossible(T, a))
        cout << "Balance is possible" << endl;
    else
        cout << "Balance is not possible" << endl;
    return 0;
}

Kết quả đầu ra

Balance is possible