เซลล์ Active และ Inactive หลังจาก k วัน

ที่นี่เราจะดูปัญหาที่น่าสนใจ สมมติว่ามีอาร์เรย์ไบนารีขนาด n (n > 3) ค่า true หรือ 1 แสดงสถานะ active ส่วน 0 หรือ false แสดง inactive อีกตัวเลข k ก็ได้รับมา เราต้องหาว่าหลังจาก k วัน เซลล์ไหน active ไหน inactive หลังจากทุกวัน สถานะของเซลล์ที่ i จะเป็น active ถ้าตัวข้างซ้ายและข้างขวาไม่เหมือนกัน ถ้าเหมือนกันจะเป็น inactive เซลล์สุดซ้ายและสุดขวาไม่มีเซลล์ก่อนและหลัง จึงมีค่าเป็น 0 เสมอ

มาดูตัวอย่าง: อาร์เรย์ = {0, 1, 0, 1, 0, 1, 0, 1}, k = 3

• หลัง 1 วัน: {1, 0, 0, 0, 0, 0, 0, 0}
• หลัง 2 วัน: {0, 1, 0, 0, 0, 0, 0, 0}
• หลัง 3 วัน: {1, 0, 1, 0, 0, 0, 0, 0}

ดังนั้นมี active 2 เซลล์ และ inactive 6 เซลล์

อัลกอริทึม

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

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

#include <iostream>
using namespace std;

void activeCellKdays(bool arr[], int n, int k) {
    bool temp[n];
    for (int i = 0; i < n; i++)
        temp[i] = arr[i];
    for (int i = 0; i < k; i++) {
        temp[0] = 0 ^ arr[1];
        temp[n-1] = 0 ^ arr[n-2];
        for (int i = 1; i <= n-2; i++)
            temp[i] = arr[i-1] ^ arr[i+1];
        for (int i = 0; i < n; i++)
            arr[i] = temp[i];
    }
    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;
}

int 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);
}

ผลลัพธ์

Active Cells = 2, Inactive Cells = 6