Chương trình C++ tìm thứ tự đặt vàng lên cân không bị 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ố x. Có n miếng vàng, miếng thứ i có trọng lượng A[i]. Chúng ta đặt lần lượt n miếng này lên cân. Tuy nhiên, cân có một lỗi đặc biệt: nếu tổng trọng lượng trên cân chính xác bằng x, nó sẽ nổ. Ta phải kiểm tra xem có thể đặt tất cả n miếng vàng lên cân theo một thứ tự nào đó mà không làm nổ cân trong quá trình hay không. Nếu có thể, hãy tìm thứ tự đó. Nếu không, trả về "IMPOSSIBLE".

Ví dụ

Nếu đầu vào là A = [1, 2, 3, 4, 8] và x = 6, đầu ra có thể là [8, 1, 2, 3, 4] (các thứ tự khác cũng hợp lệ).

Giải thuật

1. Tính tổng tất cả phần tử trong mảng. Nếu tổng bằng x, trả về "IMPOSSIBLE" vì bất kể thứ tự nào, bước cuối cùng sẽ luôn gây nổ.
2. Duyệt qua mảng, tích lũy tổng tiền tố. Nếu tại vị trí i tổng tiền tố bằng x, hoán đổi A[i] và A[i+1] (đẩy phần tử gây nổ sang sau), sau đó tiếp tục.
3. In ra mảng sau khi đã điều chỉnh.

Mã C++

#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 / Đầu ra

Input: { 1, 2, 3, 4, 8 }, 6
Output: 1, 2, 4, 3, 8,