Xâu cách đều

Điểm: 2,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho hai xâu nhị phân $s$ và $t$ cùng có độ dài $n$ (chỉ gồm các ký tự 0 và 1).

Khoảng cách Hamming giữa hai xâu cùng độ dài là số vị trí $i$ mà ký tự tại vị trí đó của hai xâu khác nhau.

Hãy tìm một xâu nhị phân $p$ có độ dài $n$ sao cho khoảng cách Hamming từ $p$ đến $s$ bằng khoảng cách Hamming từ $p$ đến $t$ . Nếu không tồn tại xâu như vậy, hãy in ra impossible.

Nếu có nhiều xâu $p$ thỏa mãn, in ra bất kỳ xâu nào.

Dữ liệu vào

Dòng đầu chứa xâu $s$ .
Dòng thứ hai chứa xâu $t$ .

Dữ liệu ra

In ra một xâu nhị phân $p$ độ dài $n$ thỏa mãn yêu cầu, hoặc impossible nếu không tồn tại.

Ràng buộc

$1 \leq n \leq 10^{5}$ .
$s$ và $t$ chỉ chứa các ký tự 0 và 1, và có cùng độ dài.

Ví dụ

Input	Output	Giải thích
0001 1011	1001	Khoảng cách từ $p = 1001$ đến $s = 0001$ là $1$ , đến $t = 1011$ cũng là $1$ . Có nhiều xâu hợp lệ khác như $0010$ , $0011$ , $0110$ , $0111$ , $1000$ , $1100$ , $1101$ .
000 111	impossible	Có $3$ vị trí $s$ và $t$ khác nhau (số lẻ), nên không thể chia đều khoảng cách.

Bình luận

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