"猜單詞"是一個雙人遊戲,在伊朗的青年學生中廣為流行。
假設有兩個遊戲者A 和B,A 作為先手,首先在一個雙方都知道的語料庫中選出一個單詞,並記在腦海中。
隨後,他在一張小紙片上劃下與單詞字母數相等的小橫線(不妨設為 n 條)。
接下來,B嘗試猜出這個單詞。每一輪,B選擇一個字母並告訴A。 A 按如下規則回應:
※若B 所說的字母在單詞中出現,A就把它寫在對應的橫線上。如果整個單詞已經完整(所有的字母已經被猜出),B獲勝。
※否則,如果字母沒有在單詞中出現,A就把它寫在最左側的下方仍為空白的橫線下。
如果所有橫線下的空白處都已經有字母(也就是說,在這一輪前B已經猜了n個錯誤字母),那麼B就輸了,A獲勝。
例如,A 從語料庫中選出了單詞RED,且B 已經依次猜了字母A, E, C, D, B和 R。
每一步的結果都在下圖中展現。最終B獲勝。但如果B在最後一步猜了S而不是R,他就輸了。
Aidin 是猜單詞遊戲迷。他相信,如果給定的語料庫足夠大,且其中的單詞相對好,
那麼玩家A(先手)可以採取一種不公平的行動——修改選擇的單詞。
也就是說,既然玩家A只將單詞記在腦海中而不寫下來,那他能夠在遊戲過程中隨時變化這個單詞,
只要使得和當前已經給出的結果仍然一致即可。
例如,在上面的遊戲中,如果單詞RED, BED, LED 和TED 都在語料庫中,那麼在第4步之後,A就可以確信他將勝利。
他將總是把B給出的字母寫在橫線下(也就是認定其為錯誤的字母),
那麼每一次他將至多在集合{RED, BED, LED, TED} 中失去一個備選單詞。
最終他將向B 宣布:「這個單詞是,嗯,...」,然後在他的集合中說出一個剩下的單詞。
Aidin 想,如果語料庫足夠好,那麼A 甚至可能在遊戲一開始就確定獲勝。
例如,如果選擇的單詞長度為2,而集合{ME, MD, DE, ED, AS, IS, AI, SI}中的單詞都在語料庫中,
那麼A總能獲勝。請自己找出A獲勝的策略。
給定一個語料庫,Aidin 想知道是否無論B如何進行遊戲,玩家A 一定能獲勝?
請注意在任何一次遊戲結束時,
如果A獲勝,A需要能夠給出一個語料庫中的單詞作為被選出的單詞,這個單詞應當與A 所有給出的回答一致。
輸入包含若干個語料庫。每個語料庫應該被獨立地處理。
輸入的第一行是一個整數C,代表語料庫的數目。隨後C個語料庫以C個模塊的形式出現在輸入中。
每兩個模塊之間以一個空行隔開。 1 ≤ C ≤ 20。
對於每個輸入模塊,第一行包含一個正整數k,表示語料庫中單詞的個數。
接下來的若干行中包含 k 個單詞。
相鄰的單詞以空格、製表符或換行符分隔。每個單詞由小於7 個大寫英語字母組成。
每個單詞都由不同的字母組成,也就是說,同一個字母在一個單詞中出現的次數不會超過 1 次。
對於20%的測試數據,k ≤ 100,每個單詞的長度不超過3;
對於50%的測試數據,k ≤ 300,每個單詞的長度不超過4;
對於所有測試數據中,k ≤ 1000。
對於每個語料庫,如果玩家A 有必勝策略(也就是說,不論B 按什麼方法猜,A 總能獲勝),
輸出一行"Yes"。否則輸出一行"No"。輸出不包含引號。
原TIOJ1750 / APIO '11
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 3 |
2 | 1 | 3 |
3 | 2 | 3 |
4 | 3 | 3 |
5 | 4 | 3 |
6 | 5 | 3 |
7 | 6 | 3 |
8 | 7 | 3 |
9 | 8 | 3 |
10 | 9 | 3 |
11 | 10 | 3 |
12 | 11 | 3 |
13 | 12 | 3 |
14 | 13 | 3 |
15 | 14 | 3 |
16 | 15 | 3 |
17 | 16 | 3 |
18 | 17 | 3 |
19 | 18 | 3 |
20 | 19 | 3 |
21 | 20 | 3 |
22 | 21 | 3 |
23 | 22 | 3 |
24 | 23 | 3 |
25 | 24 | 3 |
26 | 25 | 3 |
27 | 26 | 3 |
28 | 27 | 3 |
29 | 28 | 3 |
30 | 29 | 13 |