Xâu cách đều

Đề bài

Mô tả

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

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

  • 1n105.
  • st chỉ chứa các ký tự 01, 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=00011, đế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 3 vị trí st 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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0