โปรแกรม C++ ตรวจสอบว่าสามารถเอาหินออกจากกล่องหมดได้หรือไม่

มี N กล่องเรียงวงกลม กล่อง i มีหิน A[i] ก้อน การดำเนินการ: เลือกกล่อง i สำหรับ j=1..N นำหิน j ก้อนออกจากกล่อง (i+j)th (วนรอบ) ห้ามถ้ากล่องนั้นมีหินไม่พอ ต้องการทราบว่าสามารถนำหินออกหมดได้หรือไม่

ตัวอย่าง: A=[4,5,1,2,3] ผลลัพธ์: True (1) (เริ่มจากกล่องที่ 2)

ขั้นตอนการแก้ปัญหา (Mathematical Analysis)

1. sum = ΣA[i], p = N(N+1)/2 (ผลรวม 1..N)
2. ถ้า sum % p != 0 → false (จำนวนการดำเนินการต้องเป็นจำนวนเต็ม)
3. k = sum / p (จำนวนรอบการดำเนินการ)
4. คำนวณ b[i] = a[i] - a[(i%N)+1] (ความต่างระหว่างกล่องติดกัน)
5. ถ้า Σb[i] != 0 → false
6. ตรวจสอบทุก i: (b[i] + k) % N == 0 และ b[i] + k ≥ 0 → true มิฉะนั้น false

ตัวอย่างโค้ด C++

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

bool solve(vector<int> A) {
    int n = A.size();
    vector<int> a(n+1), b(n+1);
    int sum = 0, p = n * (n + 1) / 2;
    for (int i = 1; i <= n; i++) { a[i] = A[i-1]; sum += a[i]; }
    if (sum % p != 0) return false;
    int k = sum / p;
    for (int i = 1; i <= n; i++) b[i] = a[i] - a[i % n + 1];
    sum = 0;
    for (int i = 1; i <= n; i++) { a[i] = b[i]; sum += a[i]; }
    if (sum != 0) return false;
    for (int i = 1; i <= n; i++)
        if ((a[i] + k) % n != 0 || a[i] + k < 0) return false;
    return true;
}

int main() {
    vector<int> A = {4, 5, 1, 2, 3};
    cout << solve(A) << endl;
}

อินพุต / เอาต์พุต

Input: {4, 5, 1, 2, 3}

Output: 1