폭발하지 않고 체중계에 금을 적재하는 순서를 찾는 C++ 프로그램

n개의 개별 요소와 또 다른 숫자 x가 있는 배열 A가 있다고 가정합니다. n개의 금이 있습니다. i번째 금 무게는 A[i]입니다. 우리는 이 n개의 조각을 한 번에 한 조각씩 체중계에 올려놓을 것입니다. 그러나 저울에는 특이한 결함이 있습니다. 저울의 총 무게가 정확히 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,