Ngôn ngữ Go được thiết kế với API đơn giản và hỗ trợ đa luồng. Đội Code Jam muốn đẩy hai mục tiêu này tới giới hạn nên đề xuất một ngôn ngữ mới: Go++.

Go++ có một thanh ghi lưu một giá trị Boolean, 0 hoặc 1, ban đầu bằng 0. Ngôn ngữ có ba lệnh:

• 0: đặt thanh ghi thành 0.
• 1: đặt thanh ghi thành 1.
• ?: in giá trị hiện tại của thanh ghi.

Đơn giản phải không? Để hỗ trợ đa luồng, hai chương trình Go++ khác nhau có thể chạy đồng thời và dùng chung thanh ghi. Mỗi lệnh được thực thi nguyên tử, nghĩa là một lệnh phải kết thúc hoàn toàn trước khi lệnh tiếp theo bắt đầu. Hai chương trình có thể được xen kẽ theo bất kỳ cách nào miễn là thứ tự tương đối của các lệnh trong từng chương trình được giữ nguyên.

Ví dụ, hai chương trình 1? và ?0 chỉ có sáu cách xen kẽ sau; ở đây ký hiệu các lệnh của chương trình thứ hai bằng phần gạch chân trong bản gốc để phân biệt:

• <u>?0</u>1? in 01 vì thanh ghi ban đầu là 0.
• <u>?</u>1<u>0</u>? in 00.
• <u>?</u>1?<u>0</u> in 01.
• 1<u>?0</u>? in 10.
• 1<u>?</u>?<u>0</u> in 11.
• 1?<u>?0</u> in 11.

Chuỗi đầu ra luôn chỉ gồm 0 và 1, không bao giờ có ?, vì ? không phải một trạng thái của thanh ghi.

Thông thường, lập trình viên viết chương trình để tạo đầu ra mong muốn; ở đây bạn phải viết hai chương trình không thể tạo ra một đầu ra không mong muốn. Bạn được cho chuỗi “xấu” \(B\) độ dài \(L\) và tập \(G\) gồm \(N\) chuỗi “tốt”, tất cả đều dài \(L\). Hãy tạo hai chương trình Go++ (không nhất thiết cùng độ dài) sao cho khi chạy như trên, chúng có thể tạo ra mọi chuỗi trong \(G\), nhưng không thể tạo ra \(B\). Chúng có thể tạo thêm các chuỗi không thuộc \(G\) và khác \(B\). Tổng cộng hai chương trình phải có đúng \(L\) lệnh ?, và tổng số lệnh không được vượt quá 200.

Ví dụ, với \(B=\) 11 và \(G=\{\) 10, 00 \(\}\), hai chương trình ? và 10?1 là một đáp án hợp lệ: chúng sinh được mọi chuỗi trong \(G\) nhưng không thể sinh \(B\) với bất kỳ cách xen kẽ nào. Chúng cũng có thể sinh 01, nhưng điều đó được phép. Hai chương trình 1? và ?0 không hợp lệ vì có thể sinh \(B\) như ví dụ sáu cách ở trên. Hai chương trình 00 và ?? cũng không hợp lệ vì không sinh được mọi chuỗi trong \(G\).

Hãy tạo hai chương trình thỏa mãn, hoặc xác định rằng nhiệm vụ là IMPOSSIBLE.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm ba dòng. Dòng đầu chứa \(N,L\): số chuỗi trong \(G\) và độ dài của \(B\) cũng như mọi chuỗi trong \(G\). Dòng thứ hai chứa \(N\) chuỗi phân biệt độ dài \(L\) thuộc \(G\). Dòng thứ ba chứa chuỗi xấu \(B\) độ dài \(L\). Tất cả các chuỗi chỉ gồm 0 và 1.

Dữ liệu ra

Với mỗi bộ test, in Case #x: IMPOSSIBLE nếu không có hai chương trình thỏa mãn. Nếu có, in Case #x: y z, trong đó y,z là hai chương trình. Tổng số lệnh không vượt quá 200; mỗi chương trình có ít nhất một lệnh; tổng cộng phải có đúng \(L\) lệnh ?.

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le100\).
• \(1\le L\le50\).
• Các chuỗi trong \(G\) đôi một khác nhau.

Phân nhóm

Test Set 1 (Small, hiển thị)

\(B\) chỉ gồm các ký tự 1.

Test Set 2 (Large, ẩn)

\(B\) có thể là chuỗi 0 và 1 bất kỳ.

Đ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ụ

3
2 2
10 00
11
3 2
11 10 00
01
4 2
00 01 10 11
11

Case #1: ? 10?1
Case #2: 1?? 0
Case #3: IMPOSSIBLE

Nguồn

Google Code Jam 2016, Vòng 3, bài Go++.

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