“Guess My Word”, gọi tắt là GMW, là trò chơi dành cho hai người rất phổ biến trong giới học sinh Iran. Gọi hai người chơi là A và B. Ban đầu, A chọn một từ trong một bộ từ mà cả hai đều biết và ghi nhớ từ đó. Sau đó, trên một tờ giấy mà B nhìn thấy, A vẽ một hàng gồm \(n\) đoạn thẳng ngang ngắn, trong đó \(n\) là số chữ cái của từ đã chọn.
B cố gắng đoán từ, từng chữ cái một. Mỗi lượt, B chọn một chữ cái và nói cho A biết. A trả lời theo quy tắc sau:
- Nếu chữ cái B chọn có trong từ, A viết nó phía trên đoạn thẳng ở đúng vị trí tương ứng. Nếu từ đã hoàn chỉnh, tức là mọi chữ cái đều đã được viết ra, B thắng.
- Nếu chữ cái đó không có trong từ, A viết nó bên dưới đoạn thẳng ngoài cùng bên trái còn chỗ trống ở phía dưới. Nếu không thể viết vì tất cả các chỗ phía dưới đều đã bị chiếm, tức là B đã đoán sai \(n\) lần trước đó, thì B thua và A thắng. Sau khi thắng, A phải tiết lộ từ đã chọn cho B.
Ví dụ, A chọn từ RED, còn B lần lượt đoán A, E, C, D, B, R. Diễn biến như sau; dấu gạch ngang biểu thị một chữ cái chưa được viết ra.
B thắng ở lượt cuối. Nếu B đoán S thay cho R ở lượt đó thì B đã thua.
Aidin rất thích trò chơi này. Cậu nhận thấy nếu bộ từ đủ lớn và có những từ thích hợp, A có thể gian lận bằng cách thay đổi từ đang nghĩ đến. Vì A chỉ giữ từ trong đầu mà không viết ra, trong quá trình chơi A có thể đổi sang một từ khác trong bộ từ, miễn là từ mới vẫn phù hợp với tất cả những câu trả lời đã đưa ra cho B. Độ dài từ vẫn phải bằng số đoạn thẳng đã vẽ.
Chẳng hạn, trong ván chơi trên, nếu bộ từ có RED, BED, LED, TED thì A có thể bảo đảm chiến thắng sau lượt thứ tư. A luôn trả lời rằng chữ cái B vừa đoán là sai. Mỗi lượt tiếp theo chỉ loại bỏ nhiều nhất một từ khỏi tập RED, BED, LED, TED. Đến khi thắng, A chỉ cần tiết lộ một từ vẫn còn lại trong tập đó.
Aidin cho rằng với một bộ từ thích hợp, A đôi khi có thể bảo đảm chiến thắng ngay từ đầu. Ví dụ, nếu chơi với từ có hai chữ cái và bộ từ chứa tất cả các từ ME, MD, DE, ED, AS, IS, AI, SI, thì A luôn có thể thắng.
Cho bộ từ, hãy xác định A có thể bảo đảm chiến thắng trước mọi chiến lược của B hay không. Cuối mỗi ván A thắng, A phải đưa ra được một từ thuộc bộ từ, phù hợp với toàn bộ câu trả lời của mình trong ván đó.
Dữ liệu vào
Dòng đầu chứa số nguyên \(C\), số bộ từ cần xét độc lập. Tiếp theo là \(C\) khối dữ liệu.
Mỗi khối bắt đầu bằng số nguyên \(K\), số từ trong bộ từ. Tiếp theo là \(K\) từ, được phân cách bởi dấu cách, ký tự tab hoặc dấu xuống dòng. Mỗi từ chỉ gồm các chữ cái tiếng Anh viết hoa, có độ dài nhỏ hơn \(7\), và không có chữ cái nào xuất hiện quá một lần trong cùng một từ.
Dữ liệu ra
Với mỗi bộ từ, in Yes trên một dòng nếu A có chiến lược luôn thắng, bất kể các chữ cái và chiến lược B lựa chọn. Nếu không, in No.
Ràng buộc
- \(1 \le C \le 20\).
- \(1 \le K \le 1000\) với mỗi bộ từ.
- Độ dài mỗi từ từ \(1\) đến \(6\).
- Kích thước tệp dữ liệu vào nhỏ hơn \(500\) KB.
Phân nhóm
Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.
Các điều kiện trong bảng áp dụng cho mọi bộ từ của dữ liệu vào.
| Nhóm |
Điểm |
Ràng buộc bổ sung |
| 1 |
20 |
Mỗi từ có nhiều nhất \(3\) chữ cái và mỗi bộ từ có nhiều nhất \(100\) từ. |
| 2 |
30 |
Mỗi từ có nhiều nhất \(4\) chữ cái và mỗi bộ từ có nhiều nhất \(300\) từ. |
| 3 |
50 |
Không có ràng buộc bổ sung. |
Ví dụ
Ví dụ 1
Input
2
12
SI ME AND AI ARE MD AS WHEN ED IS DE
HARPY
5
A B AB AC AD
Output
Yes
No
Nguồn
APIO 2011 — Guess My Word!
