C++で数の累乗の重みを使って天秤を平衡させる方法

問題文

ある数の累乗となる値を持つ重りを使用して、天秤を平衡させます。

問題の説明

この問題では、天秤式のはかりが与えられます。重さ T と、ある数 a の累乗となる値を持つ複数の重りが与えられます。これらの重りを使って、天秤の両皿を平衡させる必要があります。

このとき、成立すべき等式は次のとおりです。

T + (a の累乗) = (別の a の累乗)

なお、各累乗の値に対応する重りはそれぞれ1個しか存在しないことに注意してください。

例

T = 12 : a = 4

この場合、次のようにして重りを平衡させることができます。

12 + 4 = 16

この問題を解くためには、T を a の累乗の和として表現する必要があります。そのために、T の記数法を10進法から a 進法へと変換します。

ケース1：変換結果が 0 と 1 のみの場合

基数変換した結果が 1 と 0 のみで構成されている場合、1 の位に対応する重りを加算的に組み合わせるだけで、T の値を作ることができます。

例を見てみましょう。

T = 10 : a = 3

10 を 3 進法に変換すると「101」になります。

つまり、T は 3⁰ と 3²(1 + 9)= 10 として表せるため、平衡可能です。

ケース2：変換結果に 0 と 1 以外の値が含まれる場合

基数変換した結果に 1 と 0 以外の値が含まれる場合、平衡させるには追加の操作が必要です。ここで解が存在するための必須条件は、変換後の各桁の値が (a − 1) であることです。この場合、その桁に対応する累乗の重りを T 側へ移し、代わりに基数表現の上位の桁を 1 増やします(繰り上がり処理)。

例を見てみましょう。

T = 7 : a = 3

7 を 3 進法に変換すると「21」になります。

ここで 3¹ を T 側へ移し、反対側を 1 増やすと、数は 8 となり、これは 3 進法で「22」→ 繰り上がって「101」、すなわち (9 + 1) として表されます。これにより平衡が可能になります。

以上のケースに基づいて、この問題を解くプログラムを作成します。

実装例(C++)

#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;
}

出力

Balance is possible

アルゴリズムのポイント

このプログラムの動作を簡単に整理すると、次のようになります。

• 基数変換： T を a 進法に変換し、各桁の値を配列に格納します。
• 桁のチェック： 各桁が 0、1、(a−1)、a のいずれでもない場合、その重りの組み合わせでは平衡できないため false を返します。
• 繰り上がり処理： 桁の値が (a−1) または a の場合、その重りを相手側に回す代わりに、上位の桁へ 1 を加算します。
• 判定： すべての桁を処理できれば、平衡が可能であると判断します。

計算量は基数変換に伴う O(log_aT) であり、非常に効率的なアルゴリズムです。