Xâu cách đều

Đề bài

Mô tả

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≤n≤105.
  • 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.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0