Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Shoulder-surfing is the behavior of intentionally and stealthily watching the screen of another person's electronic device, such as laptop computer or mobile phone. Since mobile devices prevail, it is getting serious to steal personal information by shoulder-surfing.

Suppose that we have a smart phone. If we touch the screen keyboard directly to enter the password, this is very vulnerable since a shoulder-surfer easily knows what we have typed. So it is desirable to conceal the input information to discourage shoulder-surfers around us. Let me explain one way to do this.

You are given a 6 x 5 grid. Each column can be considered the visible part of a wheel. So you can easily rotate each column wheel independently to make password characters visible. In this problem, we assume that each wheel contains the 26 upper letters of English alphabet. See the following Figure 1.

Assume that we have a length-5 password such as p₁ p₂ p₃ p₄ p₅. In order to pass the authentication procedure, we should construct a configuration of grid space where each p_i appears in the i-th column of the grid. In that situation we say that the user password is accepted.

Let me start with one example. Suppose that our password was set `COMPU'. If we construct the grid as shown in Figure 2 on next page, then the authentication is successfully processed.

In this password system, the position of each password character in each column is meaningless. If each of the 5 characters in p₁ p₂ p₃ p₄ p₅ appears in the corresponding column, that can be considered the correct password. So there are many grid configurations allowing one password. Note that the sequence of letters on each wheel is randomly determined for each trial and for each column. In practice, the user is able to rotate each column and press ``Enter" key, so a should-surfer cannot perceive the password by observing the 6 x 5 grid since there are too many password candidates. In this 6 x 5 grid space, maximally 6⁵ = 7, 776 cases are possible. This is the basic idea of the proposed password system against shoulder-surfers.

Unfortunately there is a problem. If a shoulder-surfer can observe more than two grid plate configurations for a person, then the shoulder-surfer can reduce the searching space and guess the correct password. Even though it is not easy to stealthily observe other's more than once, this is one weakness of implicit grid passwords.

Let me show one example with two observed configurations for a grid password. The user password is `COMPU', but `DPMAG' is also one candidate password derived from the following configuration.

You are given two configurations of grid password from a shoulder-surfer. Suppose that you have succeeded to stealthily record snapshots of the target person's device (e.g. smart phone). Then your next task is to reconstruct all possible passwords from these two snapshots. Since there are lots of password candidates, you are asked for the k-th password among all candidates in lexicographical order. In Figure 3, let us show the first 5 valid password. The first 5 valid passwords are `ABGAG' , `ABGAS', `ABGAU', `ABGPG' and `ABGPS'.

The number k is given in each test case differently. If there does not exist a k-th password since k is larger than the number of all possible passwords, then you should print `NO' in the output.

Input 

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. The first line of each test case contains one integer, K, the order of the password you should find. Note that 1K7, 777. Next the following 6 lines show the 6 rows of the first grid and another 6 lines represent the 6 rows of the second grid.

Output 

Your program is to write to standard output. Print exactly the k-th password (including `NO') in one line for each test case.

The following shows sample input and output for three test cases.

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

---

題目描述：

一般的密碼鎖是中間一排對應道的密碼都要正確才會開啟，但是這個密碼鎖只要出現在能看到的 6x5 中的每一列中都出現密碼的對應的那個即可，也就是不用對齊。
給定兩張都具備共同密碼的圖示，可能會有很多種可能的密碼，按照字典排序後，輸出第 k-th 個

題目解法：

把兩張圖的每一列計算交集的字母，然後依序窮舉，直到個數 = K

因為 K 最多也才 7776，就可以依序窮舉，而不用使用數學計算的剪枝。

#include <stdio.h>
#include <string.h>
int board[6][26], n;
int cnt, found;
char ret[10];
void dfs(int idx) {
    if(found == 1)  return;
    if(idx == 5) {
        cnt++;
        if(cnt == n) {
            ret[idx] = '\0';
            puts(ret);
            found = 1;
        }
        return;
    }
    int i;
    for(i = 0; i < 26; i++) {
        if(board[idx][i] == 2) {
            ret[idx] = i+'A';
            dfs(idx+1);
        }
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        memset(board, 0, sizeof(board));
        int i, j, k;
        char s[6][10];
        scanf("%d", &n);
        for(i = 0; i < 6; i++)
            scanf("%s", s[i]);
        for(i = 0; i < 5; i++) {
            int ss[26] = {};
            for(j = 0; j < 6; j++)
                ss[s[j][i]-'A'] = 1;
            for(j = 0; j < 26; j++)
                if(ss[j])
                    board[i][j]++;
        }
        for(i = 0; i < 6; i++)
            scanf("%s", s[i]);
        for(i = 0; i < 5; i++) {
            int ss[26] = {};
            for(j = 0; j < 6; j++)
                ss[s[j][i]-'A'] = 1;
            for(j = 0; j < 26; j++)
                if(ss[j])
                    board[i][j]++;
        }
        cnt = 0, found = 0;
        dfs(0);
        if(found == 0)
            puts("NO");
    }
    return 0;
}