C++で数値を表現するための最小の演算子

正の整数xがあるとすると、x（op1）x（op2）x（op3）x ...の形式の式を記述します。ここで、op1、op2などは演算子です。また、これらの演算子は、加算、減算、乗算、または除算のいずれかになります。たとえば、x =3の場合、3の値である3 * 3/3 + 3-3と書くことができます。いくつかのルールがありますが、これらは次のとおりです-

• 除算演算子（/）は有理数を返します。

• 括弧はどこにも配置されていません。

• 通常の演算の順序を使用します。乗算と除算は、加算と減算よりも優先されます。

• 単項否定演算子は許可されていません。

式が指定されたターゲットと等しくなるように、演算子の数が最も少ない式を作成する必要があります。したがって、演算子の数が最も少なくなります。

したがって、入力がx =4、target =15の場合、15を4 * 4- 4/4

これを解決するには、次の手順に従います-

• ターゲットがxと同じ場合、-

  • x>ターゲットの場合、-

    • （x-ターゲット）* 2および（ターゲット* 2）-1の最小値を返す

• 合計：=x、t：=0

• 合計<ターゲット、実行-

  • 合計：=合計* x

  • （tを1増やします）

• 合計がターゲットと同じである場合、-

  • tを返す

• l：=inf、r：=inf

• sum-target targetの場合、-

  • r：=leastOpsExpressTarget（x、sum-target）

• l：=leastOpsExpressTarget（x、target-（sum / x））

• 1+最小のlとrを返す

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int leastOpsExpressTarget(int x, int target) {
      if(target == x) return 0;
      if(x > target){
         return min((x - target) * 2, (target * 2) - 1);
      }
      lli sum = x;
      int t = 0;
      while(sum < target){
         sum *= x;
         t++;
      }
      if(sum == target) return t;
      int l = INT_MAX;
      int r = INT_MAX;
      if(sum - target < target){
         r = leastOpsExpressTarget(x, sum - target) + t;
      }
      l = leastOpsExpressTarget(x, target - (sum / x)) + t - 1;
      return min(l, r) + 1;
   }
};
main(){
   Solution ob;
   cout << (ob.leastOpsExpressTarget(4, 15));
}

入力

4, 15

出力

3