Ô kích hoạt và không kích hoạt sau k ngày

Ở đây chúng ta sẽ xem một bài toán thú vị. Giả sử một mảng nhị phân kích thước n được cho (n > 3). Giá trị true hoặc 1 biểu thị trạng thái kích hoạt, 0 hoặc false biểu thị không kích hoạt. Một số k cũng được cho. Chúng ta phải tìm các ô kích hoạt hoặc không kích hoạt sau k ngày. Sau mỗi ngày, trạng thái của ô thứ i sẽ được kích hoạt nếu ô trái và ô phải không giống nhau, nếu chúng giống nhau thì sẽ không kích hoạt. Ô trái nhất và phải nhất không có ô trước và sau nó. Do đó ô trái nhất và phải nhất luôn là 0.

Hãy xem một ví dụ để hiểu ý tưởng. Giả sử mảng là {0, 1, 0, 1, 0, 1, 0, 1}, và k = 3. Hãy xem nó thay đổi theo ngày như thế nào.

• Sau 1 ngày mảng sẽ là {1, 0, 0, 0, 0, 0, 0, 0}
• Sau 2 ngày mảng sẽ là {0, 1, 0, 0, 0, 0, 0, 0}
• Sau 3 ngày mảng sẽ là {1, 0, 1, 0, 0, 0, 0, 0}

Vậy có 2 ô kích hoạt và 6 ô không kích hoạt

Thuật toán

activeCellKdays(arr, n, k)

begin
  make a copy of arr into temp
  for i in range 1 to k, do
    temp[0] := 0 XOR arr[1]
    temp[n-1] := 0 XOR arr[n-2]
    for each cell i from 1 to n-2, do
      temp[i] := arr[i-1] XOR arr[i+1]
    done
    copy temp to arr for next iteration
  done
  count number of 1s as active, and number of 0s as inactive, then return the values.
end

Ví dụ

#include <iostream>
using namespace std;

void activeCellKdays(bool arr[], int n, int k) {
  bool temp[n]; //temp giữ bản sao của arr
  for (int i=0; i<n ; i++)
    temp[i] = arr[i];
  for(int i = 0; i<k; i++){
    temp[0] = 0^arr[1]; //set giá trị cho ô trái
    temp[n-1] = 0^arr[n-2]; //set giá trị cho ô phải
    for (int i=1; i<=n-2; i++) //cho tất cả ô trung gian nếu trái và phải không giống nhau, đặt 1
      temp[i] = arr[i-1] ^ arr[i+1];
    for (int i=0; i<n; i++)
      arr[i] = temp[i]; //copy lại temp vào arr cho lần lặp tiếp theo
  }
  int active = 0, inactive = 0;
  for (int i=0; i<n; i++)
    if (arr[i])
      active++;
    else
      inactive++;
  cout << "Active Cells = "<< active <<", Inactive Cells = " << inactive;
}

main() {
  bool arr[] = {0, 1, 0, 1, 0, 1, 0, 1};
  int k = 3;
  int n = sizeof(arr)/sizeof(arr[0]);
  activeCellKdays(arr, n, k);
}

Kết quả

Active Cells = 2, Inactive Cells = 6