Vòng Đèn Nhấp Nháy

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ bóng đèn được sắp xếp thành vòng tròn (đánh số $1$ đến $N$ , bóng $N$ liền kề với bóng $1$ ). Tại mỗi bước thời gian, mỗi bóng đèn bật/tắt dựa theo trạng thái của bóng đèn bên trái nó ở bước trước:

Nếu bóng bên trái đang bật ( $1$ ), bóng hiện tại đổi trạng thái (0→1 hoặc 1→0).
Nếu bóng bên trái đang tắt ( $0$ ), bóng hiện tại giữ nguyên.

Bóng bên trái của bóng $i$ là bóng $i - 1$ (bóng bên trái của bóng $1$ là bóng $N$ ).

Cho trạng thái ban đầu của $N$ bóng đèn và số bước thời gian $B$ , hãy xác định trạng thái của từng bóng sau $B$ bước.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $B$
$N$ dòng tiếp theo: trạng thái ban đầu của bóng $1, 2, \dots, N$ (mỗi dòng là $0$ hoặc $1$ )

Dữ liệu ra

$N$ dòng — trạng thái của từng bóng sau $B$ bước (mỗi dòng là $0$ hoặc $1$ ).

Ràng buộc

$3 \leq N \leq 16$
$1 \leq B \leq 10^{15}$

Ví dụ

Input	Output	Giải thích
5 6 1 0 0 0 0	1 1 1 0 1	Bắt đầu với bóng 1 bật, sau 6 bước trạng thái là [1,1,1,0,1].
8 85202215938696 0 0 1 0 0 0 1 1	0 0 0 0 0 0 0 0	Với $B$ rất lớn, cần phát hiện chu kỳ để tính nhanh.

Bình luận

Không có bình luận tại thời điểm này.