2013年7月23日 星期二

1262 - Password

Shoulder-surfing 是一種偷看別人電子設備螢幕的行為,如筆記型電腦、手機螢幕、平板電腦,都很容易遭到 Shoulder-surfing 而被竊取到個人資料。

假設我們手上有一台智慧型手機,如果採用直接輸入密碼的方式,很容易遭到 Shoulder-surfing 的窺視,為了防止這種行為,接下來將介紹混淆它的方法:


你將會得到一個 6 x 5 的表格,每一列(column) 將會被視為一個滾輪的一部分,而只要密碼可以在 6 x 5 的表格中即可,而每個滾輪將會有 26 個大寫英文字母,如下圖一:

假設長度為 5 的密碼 p1 p2 p3 p4 p5 ,根據順序 pi 會出現在 i-th column,如果都出現即這個密碼將會被解開。舉個例子來說,假設密碼為 "COMPU",而下圖二的形式即可作為一組開啟的可能。



在這個密碼系統中,在每列(column)中對應的密碼字元的位置毫無意義,因為只要有出現即可。假使每一個滾輪採用隨機的方式分配字元,使用者轉動每個列後,就可以按下 Enter 進入,但 should-surfer 沒有辦法可以直接地獲得密碼,在 6 x 5 的區域中,將能要嘗試 65 = 7776 種才有可能進入。這是一種很基礎的想法,用來改善
shoulder-surfer 所造成的問題。


但是很不幸,如果 shoulder-surfer 看到多次的進入盤面,需要嘗試的次數將會大幅下降。舉個例子:使用者設定的密碼為 "COMPU",但 "DPMAG" 也是個一種可能的密碼。如下圖三:





你將被給予兩張圖,而這兩張圖具有共同的密碼,現在要找到所有可能的密碼,由於可能的密碼太多種,輸出第 k-th 的密碼即可。

例如圖三中,將會前 5 組可能的合法密碼,分別為 `ABGAG' , `ABGAS', `ABGAU', `ABGPG', `ABGPS',對於每筆測資 k 會不同如果第 k-th 的密碼不存在,表示 k 已經大於所有可能的密碼總數,輸出 "NO" 即可。

Input 

輸入第一行將會有一個整數 T,表示接下來有多少測資組。

對於每組測資,第一行會有一個整數 K (1 <= K < 7777),接下來將會有 6 行表示第一張圖,另外 6 行表示第二張圖。


Output  

對於每組測資,輸出 k-th 的字串,如果不存在則輸出 "NO"。

Sample Input 


3
1
AYGSU
DOMRA
CPFAS
XBODG
WDYPK
PRXWO
CBOPT
DOSBG
GTRAR
APMMS
WSXNU
EFGHI
5
AYGSU
DOMRA
CPFAS
XBODG
WDYPK
PRXWO
CBOPT
DOSBG
GTRAR
APMMS
WSXNU
EFGHI
64
FGHIJ
EFGHI
DEFGH
CDEFG
BCDEF
ABCDE
WBXDY
UWYXZ
XXZFG
YYFYH
EZWZI
ZGHIJ

Sample Output 


ABGAG
ABGPS
NO

沒有留言:

張貼留言