Chương trình C ++ để kiểm tra chúng tôi có thể loại bỏ tất cả các viên đá bằng cách chọn các hộp

Giả sử chúng ta có một mảng A với N phần tử. Xét có N hộp và chúng được xếp thành một hình tròn. Hộp thứ i chứa A [i] đá. Chúng ta phải kiểm tra xem chúng ta có thể lấy hết đá ra khỏi các hộp hay không bằng cách thực hiện liên tục thao tác:Chọn một hộp nói hộp thứ i. Đối với mỗi j trong phạm vi từ 1 đến N, loại bỏ chính xác j viên đá khỏi hộp thứ (i + j). Ở đây hộp thứ (N + k) được gọi là hộp thứ k. Thao tác này không thể được thực hiện nếu một hộp không chứa đủ số lượng đá.

Vì vậy, nếu đầu vào là A =[4, 5, 1, 2, 3], thì đầu ra sẽ là Đúng, vì chúng ta có thể loại bỏ tất cả các viên đá bằng cách bắt đầu từ hộp thứ hai.

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

n := size of A
Define an array a of size (n + 1)
Define an array b of size (n + 1)
sum := 0, p := n * (n + 1)
for initialize i := 1, when i <= n, update (increase i by 1), do:
   a[i] := A[i - 1]
   sum := sum + a[i]
if sum mod p is not equal to 0, then:
   return false
k := sum / p
for initialize i := 1, when i <= n, update (increase i by 1), do:
   b[i] := a[i] - a[(i mod n) + 1]
sum := 0
for initialize i := 1, when i <= n, update (increase i by 1), do:
   a[i] := b[i]
   sum := sum + a[i]
if sum is not equal to 0, then:
   return false
for initialize i := 1, when i <= n, update (increase i by 1), do:
   if (a[i] + k) mod n is not equal to 0 or a[i] + k < 0, then:
      return false
return true

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;
bool solve(vector<int> A) {
   int n = A.size();
   vector<int> a(n + 1);
   vector<int> 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;
}

Đầu vào

{ 4, 5, 1, 2, 3 }

Đầu ra

1