Chương trình C++ kiểm tra có lấy hết đá khỏi các hộp vòng tròn không

Mô tả bài toán

N hộp xếp vòng tròn, hộp i có A[i] đá. Phép toán: chọn hộp i, với mỗi lấy đá từ hộp (i+j) (mod N). Không được lấy nếu hộp không đủ đá. Kiểm tra có thể lấy hết đá không.

Ví dụ

A=[4,5,1,2,3]. Đầu ra: True (1) (bắt đầu từ hộp 2).

Thuật toán (Toán học + Kiểm tra điều kiện)

1. Tổng đá sum phải chia hết cho . Gọi (số lần thực hiện phép toán).
2. Tính sai phân .
3. Tổng phải = 0.
4. Với mọi , (a[i]+k) % N == 0 và = 0.

Đoạn mã 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;
    return 0;
}

Đầu vào / Đầu ra

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

Output: 1