একটি বাইনারি তালিকা (১ ও ০) এবং একটি মান k দেওয়া আছে। প্রতিটি মান একটি জেল খানার অবস্থা: ১=দখল, ০=খালি। প্রতিদিন একটি খানার দুটি পাশের খানা উভয় দখল বা উভয় খালি হলে সেটি দখল হয়, অন্যথায় খালি হয়। প্রথম ও শেষ খানার অবস্থা সবসময় ০ থাকে। k দিন পর অবস্থা বের করতে হবে।
উদাহরণ: nums = [1,0,1,0,0,0,0,0], k=1 হলে আউটপুট [0,1,1,0,1,1,1,0]।
সমাধানের ধাপসমূহ
- next_day_state() ফাংশন দিয়ে পরবর্তী দিনের অবস্থা গণনা করুন
- প্রথম ও শেষ ইন্ডেক্স ০ সেট করুন
- 1 থেকে 6 পর্যন্ত লুপে পাশের দুটি খানা সমান কিনা যাচাই করুন
- সাইকেল ডিটেকশন ব্যবহার করে বড় k হ্যান্ডেল করুন
- চূড়ান্ত অবস্থা ফেরত দিন
উদাহরণ কোড
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))
ইনপুট
[1, 0, 1, 0, 0, 0, 0, 0], 1
আউটপুট
[0, 1, 1, 0, 1, 1, 1, 0]
