LIGHTS - Lights

Giới hạn
  • Thời gian: 0.24s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

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 :

0

00000000000000000000

00000000000000000000

1

111 00000000000000000

00000000000000000000

2

111000 1 0000000000000

000000 1 0000000000000

3

111000 1 0000000000000

0 11111011 00000000000

4

1110110 1111 000000000

01111101100000000000

5

11101101111000 11111 0

01111101100000000000

6

111011011110001 0 1110

011111011000000 1 0000

7

11101101111000101 0 10

01111101100000010 1 00

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

  • Người up: aukcwe
  • Nguồn bài: Croatian Regional Competition in Informatics 2006