[Cần Thơ - TST - 2025] Bài 1: Biến đổi chuỗi nhị phân

Xem dạng PDF

Gửi bài giải

Điểm: 10,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Cho hai chuỗi nhị phân st có cùng độ dài ~n~, mỗi ký tự chỉ có thể là ~0~ hoặc ~1~, các phần tử trong hai chuỗi được đánh thứ tự từ ~1~ đến ~n~. Hai chuỗi này biểu diễn cấu hình trạng thái của hai hệ thống độc lập. Do yêu cầu đồng bộ dữ liệu, cần thực hiện các thao tác hoán đổi để đưa hai chuỗi này về trạng thái giống hệt nhau. Một thao tác được định nghĩa như sau:

  • Chọn một vị trí ~i~ trong chuỗi s và một vị trí ~j~ trong chuỗi t.
  • Hoán đổi giá trị ~s_i~ và ~t_j~.

Yêu cầu: Hãy xác định số thao tác ít nhất để hai chuỗi trở nên giống hệt nhau.

INPUT

  • Dòng đầu chứa số nguyên dương ~n~ cho biết độ dài của hai chuỗi.
  • Dòng thứ hai chứa chuỗi nhị phân s.
  • Dòng thứ ba chứa chuỗi nhị phân t.

OUTPUT

  • Nếu không thể hoán đổi thì ghi ra ~-1~.
  • Ngược lại:
    • Dòng đầu ghi số nguyên ~k~ cho biết số thao tác ít nhất.
    • ~k~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~i~ và ~j~ cho biết hai chỉ số trong st được chọn ở thao tác đó. Nếu có nhiều phương án, ghi ra một phương án bất kỳ.

SAMPLE INPUT 1

4
0101
0011

SAMPLE OUTPUT 1

2
3 3
3 2

SAMPLE INPUT 2

3
000
111

SAMPLE OUTPUT 2

-1

SUBTASKS

Subtask Điểm Ràng buộc
1 ~30\%~ ~n \le 10~
2 ~40\%~ ~n \le 10^2~
3 ~30\%~ ~n \le 10^5~

Bình luận

Hãy đọc nội quy trước khi bình luận.


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