โปรแกรม C++ หาลำดับการวางทองบนเครื่องชั่งน้ำหนักโดยไม่ให้ระเบิด

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A ที่มี n องค์ประกอบที่แตกต่างกัน และตัวเลขอีกตัวหนึ่งคือ x มีทอง n ชิ้น โดยชิ้นที่ i มีน้ำหนักเท่ากับ A[i] เราจะวางทอง n ชิ้นนี้บนเครื่องชั่งน้ำหนักทีละชิ้น แต่เครื่องชั่งมีข้อบกพร่องที่แปลกประหลาด: หากน้ำหนักรวมบนเครื่องชั่งเท่ากับ x อย่างแน่นอน เครื่องจะระเบิด เราต้องตรวจสอบว่าสามารถวางทองทั้ง n ชิ้นบนเครื่องชั่งในลำดับใดลำดับหนึ่งได้หรือไม่ โดยไม่ให้เครื่องระเบิดระหว่างกระบวนการ หากทำได้ ให้หาลำดับนั้น หากไม่ทำได้ ให้ตอบว่า "IMPOSSIBLE"

ตัวอย่าง: หากอินพุตคือ A = [1, 2, 3, 4, 8]; x = 6 ผลลัพธ์จะเป็น [8, 1, 2, 3, 4] (ลำดับอื่นๆ ก็ถูกต้องเช่นกัน)

ขั้นตอนการแก้ปัญหา

s := 0
n := ขนาดของ A
สำหรับ i := 0 ถึง n-1 ทำ:
    s := s + A[i]
ถ้า s เท่ากับ x แล้ว:
    คืนค่า "IMPOSSIBLE"
s := 0
สำหรับ i := 0 ถึง n-1 ทำ:
    s := s + A[i]
    ถ้า s เท่ากับ x แล้ว:
        พิมพ์ A[i+1], A[i]
        เพิ่ม i ขึ้น 1
        ข้ามส่วนที่เหลือ ไปรอบถัดไป
    พิมพ์ A[i]

ตัวอย่างโค้ด 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);
}

อินพุต

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

เอาต์พุต

1, 2, 4, 3, 8,