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

49愛的鼓勵 6訂閱站台

Consider a closed world and a set of features that are defined for all the objects in the world. Each feature can be answered with ``yes" or ``no". Using those features, we can identify any object from the rest of the objects in the world. In other words, each object can be represented as a fixed-length sequence of booleans. Any object is different from other objects by at least one feature.

You would like to identify an object from others. For this purpose, you can ask a series of questions to someone who knows what the object is. Every question you can ask is about one of the features. He/she immediately answers each question with ``yes" or ``no" correctly. You can choose the next question after you get the answer to the previous question.

You kindly pay the answerer 100 yen as a tip for each question. Because you don't have surplus money, it is necessary to minimize the number of questions in the worst case. You don't know what is the correct answer, but fortunately know all the objects in the world. Therefore, you can plan an optimal strategy before you start questioning.

The problem you have to solve is: given a set of boolean-encoded objects, minimize the maximum number of questions by which every object in the set is identifiable.

Input 

The input is a sequence of multiple datasets. Each dataset begins with a line which consists of two integers, m and n: the number of features, and the number of objects, respectively. You can assume 0 < m11 and 0 < n128. It is followed by n lines, each of which corresponds to an object. Each line includes a binary string of length m which represent the value (``yes" or ``no") of features. There are no two identical objects.

The end of the input is indicated by a line containing two zeros. There are at most 100 datasets.

Output 

For each dataset, minimize the maximum number of questions by which every object is identifiable and output the result.

Sample Input 

8 1 
11010101 
11 4 
00111001100 
01001101011 
01010000011 
01100110001 
11 16 
01000101111 
01011000000 
01011111001 
01101101001 
01110010111 
01110100111 
10000001010 
10010001000 
10010110100 
10100010100 
10101010110 
10110100010 
11001010011 
11011001001 
11111000111 
11111011101 
11 12 
10000000000 
01000000000 
00100000000 
00010000000 
00001000000 
00000100000 
00000010000 
00000001000 
00000000100 
00000000010 
00000000001 
00000000000 
9 32 
001000000 
000100000 
000010000 
000001000 
000000100 
000000010 
000000001 
000000000 
011000000 
010100000 
010010000 
010001000 
010000100 
010000010 
010000001 
010000000 
101000000 
100100000 
100010000 
100001000 
100000100 
100000010 
100000001 
100000000 
111000000 
110100000 
110010000 
110001000 
110000100 
110000010 
110000001 
110000000 
0 0

Sample Output 

0 
2 
4 
11 
9

---

題目描述：
有很多物件，然後都具有共同屬性，而屬性只有 yes or no，接著要求規劃詢問屬性的順序，
使之可以在任一個物件詢問答次數的最大值最小化。

將狀態壓縮一下，把詢問過的屬性進行壓縮，同時也將剩餘的問題分成 yes or no 兩堆。
因此當對於問題 i 發問時，根據當前剩餘的問題進行分兩堆
因此 ans = min(ans, max(yes_state, no_state)+1);

再次聲明狀態 [使用過的題目][剩餘的問題]
由於剩餘的問題 128 題, 可以用兩個 unsigned long long 去填裝, 因此進行壓縮，
用 lowbit 去抓取 // x&-x 仍是可以在 unsigned long long 中找到最後一位

//0.332 ms, rank 14
#include <stdio.h>
#include <map>
using namespace std;
struct ELE {
    int probUsed, objItem;
    unsigned long long obj1, obj2;
    ELE(int a, int b, unsigned long long c, unsigned long long d):
        probUsed(a),objItem(b),obj1(c), obj2(d){}
    bool operator<(const ELE &a) const {
        if(obj1 != a.obj1)
            return obj1 < a.obj1;
        if(probUsed != a.probUsed)
            return probUsed < a.probUsed;
        return obj2 < a.obj2;
    }
};
int obj[128], n, m;
map<ELE, int> dp[1<<11];
//map<unsigned long long, int> low2bit;
int low2bit[1008];
int dfs(ELE &node) {
    if(node.objItem <= 1)
        return 0;
    if(dp[node.probUsed].find(node) != dp[node.probUsed].end())
        return dp[node.probUsed][node];
    int &res = dp[node.probUsed][node];
    int i, j, left, right;
    res = 0xffff;
    for(i = 0; i < n; i++) {
        if(!((node.probUsed>>i)&1)) {
            ELE yes(node.probUsed|(1<<i),0,0,0);
            ELE no(node.probUsed|(1<<i),0,0,0);
            unsigned long long x = node.obj1, v;
            while(x) {
                v = x&-x;
                j = low2bit[v%1007];
                if((obj[j]>>i)&1) {
                    yes.objItem++;
                    yes.obj1 |= 1ULL<<j;
                } else {
                    no.objItem++;
                    no.obj1 |= 1ULL<<j;
                }
                x ^= v;
            }
            x = node.obj2;
            while(x) {
                v = x&-x;
                j = low2bit[v%1007];
                if((obj[j+64]>>i)&1) {
                    yes.objItem++;
                    yes.obj2 |= 1ULL<<j;
                } else {
                    no.objItem++;
                    no.obj2 |= 1ULL<<j;
                }
                x ^= v;
            }
            left = dfs(yes);
            if(left+1 >= res)
                continue;
            right = dfs(no);
            res = min(res, max(dfs(yes),dfs(no))+1);
        }
    }
    return res;
}
int main() {
    int i, j;
    char s[20];
    for(i = 0; i < 64; i++) {
        //if(low2bit.find((1ULL<<i)%1007) != low2bit.end())
        //    puts("XX");
        low2bit[(1ULL<<i)%1007] = i;
    }
    while(scanf("%d %d", &n, &m) == 2) {
        if(n == 0)  break;
        for(i = 0; i < m; i++) {
            scanf("%s", s);
            obj[i] = 0;
            for(j = 0; s[j]; j++) {
                if(s[j] != '0')
                    obj[i] |= 1ULL<<j;
            }
        }
        for(i = (1<<n)-1; i >= 0; i--)
            dp[i].clear();
        ELE node(0,m,0,0);
        for(i = 0; i < m; i++) {
            if(i >= 64)
                node.obj2 |= 1ULL<<(i-64);
            else
                node.obj1 |= 1ULL<<i;
        }
        printf("%d\n", dfs(node));
    }
    return 0;
}