trang chủ / đề bài / icpcwf22_z

Khôi phục khảo cổ

Đề bài

Mô tả

Giáo sư Ai Cập học nổi tiếng Z Mummer đang khám phá một ngôi mộ mới được phát hiện ở Luxor và tìm thấy một công trình bí ẩn. Trên một bức tường có một hàng gồm k phiến đá hình kim tự tháp (hình tam giác). Mỗi phiến đá khắc ba chữ tượng hình: một chữ ankh (ở đỉnh), một con mắt Horus (ở góc dưới bên trái) và một con cò quăm ibis (ở góc dưới bên phải). Cạnh bức tường có n cần gạt. Vừa thận trọng thử nghiệm, vừa đề phòng bẫy, giáo sư nhận ra rằng mỗi cần gạt xoay một số kim tự tháp theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, để một chữ tượng hình khác hướng lên trên. Gạt một cần ngược trở lại sẽ xoay đúng các kim tự tháp đó theo chiều ngược lại, về vị trí ban đầu. Các cần gạt hoạt động hoàn toàn độc lập với nhau: gạt hay gạt ngược một cần luôn có cùng tác dụng, bất kể các cần khác đang ở trạng thái nào.

Ban đầu (khi chưa gạt cần nào), mọi kim tự tháp đều có chữ ankh hướng lên trên. Xoay một kim tự tháp theo chiều kim đồng hồ đưa chữ ở góc dưới bên trái lên đỉnh, nên chữ hướng lên lần lượt đổi theo vòng ankh → mắt Horus → ibis → ankh; xoay ngược chiều kim đồng hồ thì đổi theo vòng ngược lại.

Hình dưới minh hoạ một bức tường với k=3 kim tự tháp và n=2 cần gạt. Cần thứ nhất xoay kim tự tháp thứ nhất theo chiều kim đồng hồ, kim tự tháp thứ hai ngược chiều kim đồng hồ và không tác động lên kim tự tháp thứ ba. Cần thứ hai xoay cả ba kim tự tháp theo chiều kim đồng hồ. Đây chính là ví dụ 1.

Bức tường với 3 kim tự tháp và 2 cần gạt

Tò mò, giáo sư Mummer ghi lại tác dụng riêng của từng cần gạt. Trở về trường đại học sau chuyến khảo sát, bà giao cho một sinh viên nhiệm vụ vất vả: liệt kê tất cả 2n cấu hình kim tự tháp (một số cấu hình có thể trùng nhau) đạt được bằng cách gạt một tập con nào đó của các cần, để nghiên cứu thêm. Sau nhiều đêm tính toán cẩn thận, cuối cùng sinh viên cũng làm xong và bắt đầu thu dọn giấy tờ. Nhưng tai hoạ ập đến: cậu vô tình làm đổ mực và phá huỷ hoàn toàn ghi chép gốc của giáo sư, nơi duy nhất ghi lại tác dụng riêng của từng cần gạt.

Cơ hội duy nhất để thoát khỏi cơn thịnh nộ của giáo sư Mummer là khôi phục ghi chép gốc từ danh sách các cấu hình kim tự tháp. Việc này không thể làm hoàn toàn rõ ràng (chẳng hạn, không có cách nào phân biệt các thứ tự khác nhau của cùng một tập cần gạt). Nhưng chỉ cần các cần gạt khôi phục được vẫn cho đúng danh sách cấu hình đã tính, sai sót khó có thể bị phát hiện (ít nhất là cho đến khi sinh viên đã tốt nghiệp).

Nói cách khác: hãy tìm n cần gạt sao cho khi xét cả 2n tập con các cần gạt, mỗi cấu hình trong danh sách xuất hiện đúng số lần đã cho.

Dữ liệu vào

Dòng đầu tiên gồm ba số nguyên n, k và t, trong đó n (1≤n≤40) và k (1≤k≤5) lần lượt là số cần gạt và số kim tự tháp, còn t (1≤t≤3k) là số cấu hình kim tự tháp khác nhau.

Tiếp theo là t dòng mô tả các cấu hình khác nhau có thể đạt được. Mỗi dòng gồm một xâu độ dài k mô tả cấu hình và một số nguyên f (1≤f≤2n) là số cách gạt cần (số tập con các cần gạt) khác nhau cho ra cấu hình này. Cấu hình được mô tả bằng các chữ cái A, E và I: ký tự thứ j cho biết chữ tượng hình hướng lên trên ở kim tự tháp thứ j, A là ankh, E là mắt Horus (eye), I là ibis.

Các cấu hình đã cho đôi một khác nhau, tổng các giá trị f trên t dòng bằng 2n, và dữ liệu đảm bảo có ít nhất một danh sách cần gạt cho ra đúng tập hợp có lặp các cấu hình đã cho.

Dữ liệu ra

In ra n dòng mô tả một tập cần gạt cho ra đúng tập hợp có lặp các cấu hình đã cho. Mỗi dòng mô tả một cần gạt bằng một xâu độ dài k gồm các ký hiệu +, - hoặc 0. Ký hiệu thứ j mô tả tác dụng của cần gạt lên kim tự tháp thứ j: + nếu cần xoay kim tự tháp theo chiều kim đồng hồ, - nếu xoay ngược chiều kim đồng hồ, 0 nếu không xoay kim tự tháp này.

Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

  • 1≤n≤40, 1≤k≤5, 1≤t≤3k.
  • 1≤f≤2n, tổng các f bằng 2n.
  • Luôn tồn tại ít nhất một đáp án.

Ví dụ

Input Output Giải thích
2 3 4
EEE 1
EIA 1
IAE 1
AAA 1
+-0
+++
Không gạt cần nào: AAA. Chỉ gạt cần 1: EIA. Chỉ gạt cần 2: EEE. Gạt cả hai: kim tự tháp 1 xoay thuận hai lần (I), kim tự tháp 2 xoay ngược rồi thuận (A), kim tự tháp 3 xoay thuận một lần (E), được IAE.
3 2 2
IA 4
AA 4
-0
00
00
Hai cần không tác động lên kim tự tháp nào; cần còn lại xoay kim tự tháp 1 ngược chiều kim đồng hồ (A thành I). Mỗi cấu hình AA, IA đạt được bằng 4 tập con.

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