Chương trình C ++ để tìm thứ tự xếp vàng trên cân mà không làm nổ nó

Giả sử chúng ta có một mảng A với n phần tử phân biệt và một số khác x. Có n miếng vàng. Khối lượng vàng thứ i là A [i]. Chúng ta sẽ đặt lần lượt n miếng này lên bàn cân. Nhưng chiếc cân có một khuyết điểm bất thường:nếu tổng trọng lượng trên đó là x chính xác, nó sẽ phát nổ. Chúng tôi phải kiểm tra xem chúng tôi có thể đặt tất cả n miếng vàng lên cân theo một số thứ tự mà không làm nổ cân trong quá trình này hay không. Nếu chúng ta có thể, hãy tìm đơn đặt hàng đó. Nếu không thể, hãy đánh dấu "KHÔNG THỂ CÓ ĐƯỢC".

Vì vậy, nếu đầu vào là A =[1, 2, 3, 4, 8]; x =6 thì đầu ra sẽ là [8, 1, 2, 3, 4], các đơn hàng khác cũng hợp lệ

Các bước

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

1, 2, 4, 3, 8,