Giới thiệu

Magicka™ là một trò chơi hành động phiêu lưu được phát triển bởi Arrowhead Game Studios. Trong Magicka, bạn đóng vai một pháp sư, triệu hồi và kết hợp các nguyên tố để tạo ra các phép thuật (Magicks). Bài toán này có ý tưởng tương tự, nhưng không yêu cầu bạn phải từng chơi Magicka.

Lưu ý: "triệu hồi" (invoke) ở đây là một thuật ngữ kỹ thuật trong bài toán này, bạn không cần quan tâm đến nghĩa tiếng Anh thông thường của nó.

Đề bài

Là một pháp sư, bạn có thể triệu hồi tám nguyên tố, gọi là các nguyên tố "cơ bản". Mỗi nguyên tố cơ bản là một ký tự duy nhất từ tập {Q, W, E, R, A, S, D, F}. Khi bạn triệu hồi một nguyên tố, nó sẽ được thêm vào cuối danh sách nguyên tố của bạn. Ví dụ: nếu bạn triệu hồi W rồi sau đó triệu hồi A (gọi tắt là "triệu hồi WA"), danh sách nguyên tố của bạn sẽ là [W, A].

Chúng tôi sẽ chỉ định các cặp nguyên tố cơ bản có thể kết hợp để tạo thành các nguyên tố không cơ bản (18 chữ cái in hoa còn lại). Ví dụ, Q và F có thể kết hợp để tạo thành T. Nếu hai nguyên tố trong một cặp xuất hiện ở cuối danh sách nguyên tố, thì cả hai nguyên tố đó sẽ ngay lập tức bị xóa bỏ và được thay thế bằng nguyên tố mà chúng tạo thành. Trong ví dụ trên, nếu danh sách nguyên tố là [A, Q, F] hoặc [A, F, Q] tại bất kỳ thời điểm nào, nó sẽ trở thành [A, T].

Chúng tôi cũng sẽ chỉ định các cặp nguyên tố cơ bản xung khắc với nhau. Sau khi bạn triệu hồi một nguyên tố, nếu nó không được kết hợp ngay lập tức để tạo thành nguyên tố khác, và nó xung khắc với một nguyên tố nào đó đã có trong danh sách nguyên tố, thì toàn bộ danh sách nguyên tố của bạn sẽ bị xóa sạch.

Ví dụ, giả sử Q và F kết hợp tạo thành T. R và F xung khắc với nhau. Khi đó, việc triệu hồi các chuỗi sau (theo thứ tự từ trái sang phải) sẽ có kết quả như sau:

• QF → [T] (Q và F kết hợp thành T)
• QEF → [Q, E, F] (Q và F không thể kết hợp vì chúng không bao giờ cùng nằm ở cuối danh sách)
• RFE → [E] (F và R xung khắc, nên danh sách bị xóa; sau đó E được triệu hồi)
• REF → [] (F và R xung khắc, nên danh sách bị xóa)
• RQF → [R, T] (QF kết hợp thành T, nên danh sách không bị xóa)
• RFQ → [Q] (F và R xung khắc, nên danh sách bị xóa)

Cho một danh sách các nguyên tố cần triệu hồi, danh sách nguyên tố cuối cùng sẽ là gì?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ dữ liệu, \(T\). \(T\) bộ dữ liệu tiếp theo. Mỗi bộ dữ liệu nằm trên một dòng duy nhất, chứa các thành phần sau cách nhau bởi dấu cách:

Đầu tiên là một số nguyên \(C\), tiếp theo là \(C\) chuỗi, mỗi chuỗi chứa ba ký tự: hai nguyên tố cơ bản theo sau là một nguyên tố không cơ bản. Điều này cho biết hai nguyên tố cơ bản đó kết hợp tạo thành nguyên tố không cơ bản. Tiếp theo là một số nguyên \(D\), tiếp theo là \(D\) chuỗi, mỗi chuỗi chứa hai ký tự: hai nguyên tố cơ bản xung khắc với nhau. Cuối cùng là một số nguyên \(N\), tiếp theo là một chuỗi duy nhất chứa \(N\) ký tự: chuỗi các nguyên tố cơ bản mà bạn cần triệu hồi. Bạn sẽ triệu hồi chúng theo thứ tự xuất hiện trong chuỗi (ký tự ngoài cùng bên trái trước, v.v.), từng cái một.

Dữ liệu ra

Với mỗi bộ dữ liệu, xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ dữ liệu (bắt đầu từ 1) và y là một danh sách theo định dạng "[e\(_0\), e\(_1\), ...]" trong đó e\(_i\) là nguyên tố thứ \(i\) của danh sách nguyên tố cuối cùng. Vui lòng xem ví dụ để biết định dạng cụ thể.

Ràng buộc

• \(1 \le T \le 100\).
• Mỗi cặp nguyên tố cơ bản chỉ có thể xuất hiện cùng nhau trong tối đa một quy tắc kết hợp, mặc dù chúng có thể vừa nằm trong một quy tắc kết hợp vừa xung khắc với nhau.
• Không có nguyên tố cơ bản nào xung khắc với chính nó.
• Khác với trò chơi Magicka, không có giới hạn về độ dài của danh sách nguyên tố.

Phân nhóm

• Test set 1 (Visible): \(0 \le C \le 1\), \(0 \le D \le 1\), \(1 \le N \le 10\).
• Test set 2 (Hidden): \(0 \le C \le 36\), \(0 \le D \le 28\), \(1 \le N \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
0 0 2 EA
1 QRI 0 4 RRQR
1 QFT 1 QF 7 FAQFDFQ
1 EEZ 1 QE 7 QEEEERA
0 1 QW 2 QW

Case #1: [E, A]
Case #2: [R, I, R]
Case #3: [F, D, T]
Case #4: [Z, E, R, A]
Case #5: []

Nguồn

Google Code Jam 2011, Vòng loại, bài Magicka.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.