canuc80k2703·4/50

Năm Chuỗi Kết Quả

Nộp bài trên LQDOJ

Bài 27 · Bitset

Cho hai chuỗi nhị phân và có cùng độ dài. Mỗi phép toán dưới đây được thực hiện độc lập tại từng vị trí: AND, OR, XOR, đảo và đảo .

Input

  • Dòng đầu chứa số nguyên .
  • Dòng thứ hai chứa chuỗi .
  • Dòng thứ ba chứa chuỗi .

Output

  • In năm dòng theo thứ tự: . Mỗi dòng phải có đúng ký tự.

Constraints

  • .
  • và chỉ gồm và đều có độ dài .

Scoring

  • Subtask ( số điểm): .
  • Subtask ( số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

6
101100
110010

Output

100000
111110
011110
010011
001101

Giải thích: Ở mỗi cột, hai bit được xử lý theo bảng chân trị. Chẳng hạn cột đầu là nên AND và OR bằng , XOR bằng ; phép NOT chỉ đổi thành và ngược lại.

Lời giải tóm tắt
  • Mô hình và ý tưởng: Duyệt từng vị trí, chuyển hai ký tự thành bit và ghi đồng thời năm chuỗi kết quả.
  • Chứng minh tính đúng đắn: Tại từng vị trí, năm ký tự được tính đúng theo bảng chân trị. Vì các vị trí độc lập, ghép các kết quả vị trí tạo đúng năm chuỗi toàn cục.
  • Độ phức tạp: O(n) thời gian và O(n) bộ nhớ cho năm chuỗi đầu ra.
  • Lỗi cài đặt thường gặp: dùng ~ trực tiếp lên char; nhầm OR với XOR.