Giải bài trực tuyến

Hệ thống chiếu sáng của rạp hát có 2n bóng đèn được xếp thành 2 hàng mỗi hàng có n bóng. Mỗi bóng có 2 trạng thái là được bật sáng hoặc tắt, ban đầu tất cả các đèn đều được tắt.

Những người thợ trang trí muốn bật một số bóng đèn sao cho có thể tạo thành hình ảnh đẹp mắt. Hệ thống điều khiển chỉ cho phép ta mỗi một lần chỉ có thể đổi trạng thái từ bật sang tắt hoặc từ tắt sang bật của 2 bóng đèn ở cùng cột hoặc 1 số bóng đèn liên tiếp ở cùng hàng.

Yêu cầu:

• Cho trước trạng thái cuối cùng của hệ thống đèn mà những người thợ trang trí mong muốn.
• Tính số lần bật hoặc tắt ít nhất để được trạng thái đó.

Hình ảnh dưới đây minh họa 7 bước để đạt trạng thái cuối cùng :

Dữ liệu:

• Dòng đầu tiên chứa số nguyên n là số bóng đèn ở mỗi hàng ((1 ≤ n ≤ 10 000).
• 2 dòng tiếp theo, mỗi dòng là trạng thái của mỗi hàng đèn tại thời điểmcuối cùng, số 1 biểu thị 1 bóng đèn đang sáng và 0 là 1 bóng đèn đang tắt.

Kết quả:

• Đưa ra số lần bật hoặc tắt ít nhất để được trạng thái theo yêu cầu.

Ví dụ:

Dữ liệu :
20
11101101111000101010
01111101100000010100

Kết quả :
7