Sao kê 3: Mặt nạ

Xem PDF

Điểm: 550 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Hôm nay, tôi sẽ kể cho các bạn \(1\) câu chuyện nghe tuy hơi bựa nhưng mà có thật về sự thành lập của LQDOJ:

Vào năm 2020-2021, một trình duyệt mới chuyên chia sẻ các ý tưởng về ra đề và code, và cũng là nơi để giao lưu học hỏi đã được tạo ra tên là LQDOJ. Trong những năm đầu thì LQDOJ đã rất thành công với hơn 1000 ý tưởng ra đề và hơn 500000 bài nộp(không chắc có đúng không). Nhưng theo các bạn nhớ có thì từ xa xưa đã có 1 ông vua nào đó đã chuyên đi chép code và một ông thì gáy hơi bị to trong bài https://lqdoj.edu.vn/problem/desksbd và để nối tiếp sự nghiệp thì vẫn có 1 tổ chức ở ẩn đã được tạo ra chuyên CHÉP CODE VÀ IF TEST. Từ đó, các admin đã bắt đầu vào công cuộc điều tra bằng cách sao kê rất nhiều bài submiss của các coder rồi sẽ phát hiện và AB tất cả bài nộp chép code và if test. Người ta gọi thời đại này là VƯỜN SAO KÊ. Trong đó, có 1 nhóm gồm 4 người đã góp phần rất nhiều vào việc giúp admin sao kê, họ được mệnh danh là TỨ HOÀNG[và tôi là 1 trong số đó(đùa thôi hehe)]. Các thành viên gồm: WuTan, vinhntndu, SPyofgamehhoangcpascal. Họ cũng là những người đang trong công cuộc tìm ra kẻ đầu sỏ của tổ chức – là người đang giữ tài khoản huyền thoại ONE PIECE. Để tìm ra tài khoản huyền thoại đó thì họ phải vượt qua một số thử thách. VÀ ĐÂY CHÍNH LÀ PHẦN III: MẶT NẠ:

Sau một thời gian dài tra cứu các bạn trong LQDOJ và truy tìm, các bạn đã tới được chỗ của imbigbrain – kẻ cầm đầu hội chép code nhưng chẳng ai chịu xông vào bắt hắn ra cả :))) , cuối cùng admin, bộ tứ hoàng, bác sĩ John Huy HậuSherlock Hải đã phải tới tận hang ổ của imbigbrain và cho nó vào nhà giam. Nhưng mọi chuyện vẫn chưa kết thúc, các admin và bộ tứ hoàng phải đột nhập vào tài khoản ONE PIECE để xóa hết dữ liệu chép code, if test trong suốt thời gian vừa qua của tài khoản ONE PIECE đó. Nhưng vừa khi đột nhập vô acc thì bộ tứ hoàng gặp một rắc rối mới: một mặt nạ đã được gửi cho admin, admin đã sao lưu rồi đã gửi chiếc mặt nạ đó cho bộ tứ hoàng. Mặt nạ là một hình vuông chỉ chứa \(2\) bit \(0\)\(1\)(khá giống mật mã trong SAO KÊ 2). Phía sau mặt nạ có một số nút như sau:

  • Nút \(1\): Thay đổi trạng thái của các bit trong \(1\) hàng
  • Nút \(2\): Thay đổi trạng thái của các bit trong \(1\) cột
  • Nút \(3\): Thay đổi trạng thái của bit trong \(1\) ô

Nhiệm vụ của bộ tứ hoàng là phải biến đổi các bit trong ma trận sao cho ma trận đó chỉ có đúng bit \(0\) hoặc \(1\). Nhưng vấn đề bộ tứ hoàng lại gặp phải đó là phải sử dụng nút \(3\) ít lần nhất có thể. Nếu chỉ cần đổi bit sai \(1\) nút theo mật mã tối ưu nhất mà imbigbrain đã cài đặt thì mật mã coi như không thể mở acc được(mãi mãi...). Với cái trình não to của bác sĩ John Huy HậuSherlock Hải thì cũng phải đầu hàng (coi bộ não của imbigbrain còn to hơn ta tưởng tượng). Nhưng mà gọi đầu hàng thì hơi phèn, phải gọi là quá dễ nhưng mà nhường lại cho các bạn coder của LQDOJ đấy, các lập trình viên ơi. Hãy giúp bộ tứ hoàng, bác sĩ John Huy HậuSherlock Hải giải quyết vấn đề này nhé! Nếu hoàn thành thử thách thì các bạn sẽ được món quà rất là giá trị đó là thêm bài AC và điểm hehe và big brain não to hơn ta tưởng tượng sẽ trở thành pig brain :)))!

Input

  • Dòng \(1\) gồm duy nhất \(1\) số \(n(n\le 20)\)
  • \(N\) dòng tiếp theo, mỗi dòng gồm \(n\) số liền kề nhau chỉ các bit của
    mặt nạ.

Output

  • Dòng \(1\) xuất số lần ít nhất sử dụng nút \(3\). Sau đó các dòng tiếp
    theo xuất ma trận sau khi sử dụng nút \(3\) nhiều lần hợp lý. Nếu có
    nhiều kết quả, hãy xuất kết quả có thứ tự từ điển nhỏ nhất có thể.

Example

Test 1

Input
2
11
01
Output
1
01 
01
Note

Giải thích: Ta có thể chuyển sang mặt nạ bit \(0\) như sau(Dấu \(x\) chỉ rằng đổi bit ở hàng hay cột)


Bình luận


  • 1
    huyhau6a2    9:23 p.m. 15 Tháng 3, 2022 đã chỉnh sửa

    Solution bài 3

    Author: huyhau6a2


    \(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

    \(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

    \(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)



    \(\color{orange}{\text{Hướng dẫn và Tiếp cận}}\)

    Nhận xét: Ta có thể chuyển đề đơn giản về sử dụng nút \(1\)\(2\) sao cho sử dụng nút \(3\) ít lần có thể và thỏa mãn tttđ nhỏ nhất có thể

    Giải: Bài này là bitmask cơ bản:

    • Đầu tiên, ta sẽ sinh bitmask độ dài \(n\). Với mỗi bitmask, ta có thể thực hiện \(O(n)\) để tìm cách đổi tối ưu

    • Giả sử với \(1\) bitmask có cách tối ưu hơn, ta cập nhật ma trận kết quả

    • Cuối cùng xuất ma trận là xong!


    \(\color{green}{\text{Code tham khảo }}\): Approach

    \(^{^{\color{purple}{\text{Độ phức tạp : }} O()\ \color{purple}{\text{thời gian}}\ ||\ O()\ \color{purple}{\text{bộ nhớ}}}}\)

    C++
    //Không có code đâu, tự code đi hehe!
    
    • 1 bình luận nữa