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 s
và t
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ỗit
. - 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
s
vàt
đượ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