Lights Off

Điểm: 1,00 (OI)

Giới hạn thời gian: 4.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

Bessie cần tắt tất cả đèn trong trang trại. Cô có hai xâu bit độ dài $N$ ( $2 \leq N \leq 20$ ): một biểu diễn trạng thái đèn và một biểu diễn công tắc.

Mỗi bước gồm:

Bật/tắt đúng một công tắc (toggle)
Với mỗi công tắc đang bật, toggle đèn tương ứng
Xoay vòng dãy công tắc sang phải một vị trí

Với mỗi cặp (đèn, công tắc), tìm số bước tối thiểu để tắt tất cả đèn.

Dữ liệu vào

Dòng đầu: $T$ (số truy vấn, $1 \leq T \leq 2 \times 10^{5}$ ) và $N$
$T$ dòng tiếp: mỗi dòng gồm hai xâu bit độ dài $N$ (trạng thái đèn và công tắc)

Dữ liệu ra

Với mỗi truy vấn, in ra số bước tối thiểu.

Ràng buộc

$2 \leq N \leq 20$
$1 \leq T \leq 2 \times 10^{5}$
Giới hạn thời gian: 4 giây

Ví dụ

Input	Output	Giải thích
4 3 000 101 101 100 110 000 111 000	0 1 3 2	Truy vấn 1: đèn đã tắt hết. Truy vấn 2: cần 1 bước.

Bình luận

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