それを爆発させることなく体重計で金をロードする順序を見つけるためのC++プログラム

n個の異なる要素を持つ配列Aと、別の数xがあるとします。金はn個あります。 i番目の金の重さはA[i]です。このn個を一度に1個ずつ体重計に載せます。しかし、スケールには異常な欠陥があります。スケールの総重量が正確にxの場合、爆発します。プロセス中にスケールを爆発させることなく、n個すべての金貨をある順序でスケールに配置できるかどうかを確認する必要があります。可能であれば、その順序を見つけてください。不可能な場合は、「不可能」とマークしてください。

したがって、入力がA =[1、2、3、4、8]のような場合; x =6の場合、出力は[8、1、2、3、4]になり、他の注文も有効になります

ステップ

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

s := 0
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   s := s + A[i]
if s is same as x, then:
   return "IMPOSSIBLE"
s := 0
for initialize i := 0, when i < n, update (increase i by 1), do:
   s := s + A[i]
   if s is same as x, then:
      print A[i + 1], A[i]
      (increase i by 1)
      Ignore following part, skip to the next iteration
   print A[i]

例

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

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

void solve(vector<int> A, int x) {
   int s = 0;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      s += A[i];
   }
   if (s == x) {
      cout << "IMPOSSIBLE";
      return;
   }
   s = 0;
   for (int i = 0; i < n; i++) {
      s += A[i];
      if (s == x) {
         cout << A[i + 1] << ", " << A[i] << ", ";
         i++;
         continue;
      }
      cout << A[i] << ", ";
   }
}
int main() {
   vector<int> A = { 1, 2, 3, 4, 8 };
   int x = 6;
   solve(A, x);
}

入力

{ 1, 2, 3, 4, 8 }, 6

出力

1, 2, 4, 3, 8,