Chương trình tìm trạng thái phòng tù sau k ngày bằng Python

Cho danh sách nhị phân nums (trạng thái phòng tù: 1 có người, 0 trống) và số ngày k. Mỗi ngày: phòng có 2 láng giềng cùng trạng thái (cả 2 đều 1 hoặc cả 2 đều 0) → thành 1, ngược lại thành 0. Phòng đầu và cuối luôn thành 0. Tìm trạng thái sau k ngày.

Ví dụ: nums=[1,0,1,0,0,0,0,0], k=1 → [0,1,1,0,1,1,1,0].

Giải thuật

• Hàm next_day_state(cells): tạo bản sao, đặt 2 đầu = 0, với mỗi ô 1..6: nếu cells[j-1] == cells[j+1] thì 1 else 0.
• Phát hiện chu kỳ: lưu các trạng thái đã thấy vào map seen.
• Nếu gặp trạng thái lặp: k = k % len(seen), chạy tiếp k bước.
• Trả về trạng thái cuối.

Ví dụ minh họa

import copy
class Solution:
    def next_day_state(self, cells):
        new_cells = copy.copy(cells)
        new_cells[0] = 0
        new_cells[7] = 0
        for j in range(1, 7):
            if cells[j-1] == cells[j+1]:
                new_cells[j] = 1
            else:
                new_cells[j] = 0
        return new_cells
    def solve(self, cells, N):
        seen = dict()
        flag, i = False, 0
        while i < N:
            ns = self.next_day_state(cells)
            if tuple(ns) not in seen:
                seen[tuple(ns)] = True
            else:
                flag = True
                break
            cells = ns
            i += 1
        if flag:
            N = N % len(seen)
            i = 0
            while i < N:
                ns = self.next_day_state(cells)
                i += 1
                cells = ns
        return cells

ob = Solution()
nums = [1, 0, 1, 0, 0, 0, 0, 0]
k = 1
print(ob.solve(nums, k))

Đầu vào

[1, 0, 1, 0, 0, 0, 0, 0], 1

Đầu ra

[0, 1, 1, 0, 1, 1, 1, 0]