Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

LIGHTS - Lights

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

11100000000000000000

00000000000000000000

2

11100010000000000000

00000010000000000000

3

11100010000000000000

01111101100000000000

4

11101101111000000000

01111101100000000000

5

11101101111000111110

01111101100000000000

6

11101101111000101110

01111101100000010000

7

11101101111000101010

01111101100000010100

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

Được gửi lên bởi:Kaiel
Ngày:2008-10-10
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C CSHARP CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:Croatian Regional Competition in Informatics 2006

hide comments
2018-12-18 05:03:10
solution : https://bit.ly/2eGhgab
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.