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.
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.
For each case, print exactly one line. If the string exists, please print it, otherwise print “Impossible”.
3 2 2 2 2 2 7 4 7 47
0101 Impossible 0101011101
对于任何一个0*1*0*1*... 串， 能够给出下一个升序的排列的项。关键是设计出一个move的函数，对于当前任何一个串，能够得出其下一个的01字符串是什么。具体如何移动/交换字符串中的01位置，详见代码。
#include <iostream>
#include <cstdio> //包含语言重定向函数freopen的库
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
void swap(int &a, int &b){
int temp=a;
a = b;
b = temp;
}
long long jiecheng(long k){
if(k!=1){
return jiecheng(k-1)*k;
}else
return 1;
}
void print(int *a, int length){
for(int i=0; i<length; ++i){
cout<<a[i];
}
cout<<endl;
}
void move(int* a, int length){
bool tail0=false;;
int tail0Num=0;
int i=length-1;
if(a[i] == 0)
tail0 = true;
while( a[i] == 0 ){
tail0Num++;
i--;
}
while( a[i]== 1){
i--;
}
if(tail0== true){
int beg=i+2;
int end=length-1;
for( int i=0; i<tail0Num; ++i){
if(beg != end ){
swap(a[beg],a[end]);
}
beg++;
end--;
}
}
}
int main()
{
int t;
cin>>t;
for( int i=0; i<t; ++i){
int n ,m , k;
cin>>n>>m>>k;
if( (jiecheng(n+m)/ jiecheng(m)) /jiecheng(n)<k ){
cout<<"Impossible"<<endl;
}else{
int* a = new int[n+m];
for(int i=0; i<n; ++i){
a[i]= 0 ;
}
for(int i=n; i<m+n; ++i){
a[i]= 1 ;
}
print(a,n+m);
for( int i=0; i<k-1; ++i){
move(a,n+m);
print(a,n+m);
}
print(a,n+m);
}
}
return 0;
}
微软2014实习生及秋令营技术类职位在线测试之 2. K-th String,布布扣,bubuko.com
微软2014实习生及秋令营技术类职位在线测试之 2. K-th String
原文：http://blog.csdn.net/acema/article/details/23557373