送上今年微軟的一道筆試題

作者：瀟一 2014-04-29 14:58:24

這里送上一道微軟的筆試題，大家可能會認為這是一個全排列的問題，但是全排列在問題在于不能很好的知道每個數到底排在第幾位，并且時間上肯定是不能通過的，遞歸的效率大家應該都知道。

這里送上一道微軟的筆試題，具體題目如下：

Time Limit: 10000ms

Case Time Limit: 1000ms

Memory Limit: 256MB

Description

Consider a string set that each of them consists of {0, 1} only. All strings in the set have the same number of 0s and 1s.

Write a program to find and output the K-th string according to the dictionary order. If such a string doesn’t exist,

or the input is not valid, please output “Impossible”. For example, if we have two ‘0’s and two ‘1’s,

we will have a set with 6 different strings, {0011, 0101, 0110, 1001, 1010, 1100}, and the 4th string is 1001.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10000),

the number of test cases, followed by the input data for each test case.

Each test case is 3 integers separated by blank space: N, M(2 <= N + M <= 33 and N , M >= 0),

K(1 <= K <= 1000000000). N stands for the number of ‘0’s, M stands for the number of ‘1’s,

and K stands for the K-th of string in the set that needs to be printed as output.

Output

For each case, print exactly one line. If the string exists, please print it, otherwise print “Impossible”.

Sample In

2 2 2

2 2 7

4 7 47

Sample Out

0101

Impossible

01010111011

其實說了這么多，意思很簡單，就是輸入N個0，M個1.然后求出由M，N個1,0組成的第K大的數。如果不存在則輸出impossible.

初來乍到的，大家可能會認為這是一個全排列的問題，但是全排列在問題在于不能很好的知道每個數到底排在第幾位，并且時間上肯定是不能通過的，遞歸的效率大家應該都知道。

我們可能會想到另外一種解決方案，直接列舉，從最小的000...1111開始，一直列舉到1111..000然后記錄下當前是否是含N個0，M個1。這種方式是最容易理解的了，但是如果數字比較大，比如17個1,17個0,我們且不說這么大的整數不能保存，就這個時間上也不合算啊，雖然他是線性復雜度，但是這個線性數也太大了點。。。

OK，我接下來又想到了是否可以通過樹的遍歷，想了想被我否了。

終于想到了一種方式，就是通過不斷的交換獲得。我們想到，如果從一個第1大的數變成第2大的數，必然要使這個數增大，那么怎么個增大法？才能使得這兩個數是最接近的，也就是說我們只增加了1，而不是中間還存在很多數呢？

那就是從左到右掃描數據，直到遇到10就交換，并且在該1之前的1要和***位的0交換。好的思路已經完全暴露了，我這里就列舉一個例子。

比如5個1，5個0的情況。

我們保存的格式是1111100000(實際數為0000011111)，它是最小的數(輸出的時候倒著輸出，這種結構主要為了理解方便)。***的數是0000011111.（記住，是倒著哈！）

當我們要增加的時候在J=5的時候，出現了0，且j=4時,它為1，這樣就交換他們，j=4之前的1和低位的0交換，這里沒有0就不需要交換了。得到1111010000（實際數為0000101111）.

當我們出現0011101100(實際數為0011011100)要使數字增加1應該怎么做呢？顯然，還是J=5時出現了0且j-1=4時為1交換他們，并且j=4之前的1和***位的0開始不斷交換，***我們會得到結果：1100011100.(實際數為00111000011).

Ok,說到這里大家應該就完全懂了，且看算法源代碼：[集思廣益，你們有沒有更好的解決方案？]

//M：0的個數，N，1的個數。K要輸出第幾個數。 
bool test(int N,int M,int K){ 
    if(calculateTotalNum(M+N,M)<K)//若實際上的數少于k，返回false,則輸出impossible 
        return false; 
    int L=M+N,count=1; 
    bitset<MaxLength> bit; 
    map<int,bitset<MaxLength>> mapStr; 
    for(int i=0;i<M;i++)//初始話最小數，即0都在最左邊比如0011 
        bit[i]=1; 
    if(K==1){ 
        print(bit,M+N);//輸出 
        return true; 
    } 
    int j=0;//表示從低位一直搜索到高位，有沒有遇到01，有的話就不斷交換。 
    while(!isLast(bit,M,N)){//沒有搜索到***一個數字 
        if(j>=M+N-1) 
            j=0;//已經搜索到***位了，這個時候就需要從0位搜索 
        if(1==bit[j]&&0==bit[j+1]){ 
            int right=j-1,left=0; 
            //從J的前一個搜素，并且該之前的1全部移動到最左邊 
            while(right>=0&&bit[right]==1&&left<right){ 
                bool temp=bit[right]; 
                bit[right]=bit[left]; 
                bit[left]=temp; 
                right--,left++; 
            } 
            bit[j]=0;//交換0,1 
            bit[j+1]=1; 
            count++;//統計是第幾個大的數了 
            if(count==K){ 
                print(bit,M+N); 
                return true; 
            } 
            j=0;//重新回過頭來搜素 
        } 
        else 
            j++; 
    } 
    return true; 
} 
 
int calculateTotalNum(int N,int M){//組合問題，計算一共多少個數。C(M,N)=A(N,N)/(A(M,M)*A(N-M,N-M)) 
    int result=1; 
    for(int i=1;i<=N;i++) 
        result*=i; 
    for(int i=1;i<=M;i++) 
        result/=i; 
    for(int i=1;i<=N-M;i++) 
        result/=i; 
    return result; 
} 
bool isLast(bitset<MaxLength> bit,int M,int N){ 
    int i=0; 
    while(i<N&&0==bit[i]) 
        i++; 
    if(i==N) 
        return true; 
    else 
        return false; 
} 
void print(bitset<MaxLength> bit,int N){// 
    for(int i=N-1;i>=0;i--) 
        cout<<bit[i]; 
    cout<<"　　"; 
}