首页 > 代码库 > [微软实习生2014]K-th string

[微软实习生2014]K-th string

2024-07-04 20:25:19   224人阅读

很久之前的事情了，微软2014实习生的在线测试题，记录下来以备后用。

题目描述：

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”.

样例输入

3
2 2 2
2 2 7
4 7 47

样例输出

0101
Impossible
01010111011

题解：

　　这道题目本身不是很难，题目的大概意思是让我们从N个0、M个1组成的二进制数从小到大排列中找出第k个。话虽这么说，但事实上肯定不能这么做，N和M虽然不大(最大到33)，但其排列组合的规模依然非常可观，暴力法的时间消耗是不能接受的。

　　说说我的想法吧。首先从0、1排列的那些数从小到大的排列中，一个很显然的是第一个数是0的肯定比第一个数是1的要小，而且我们要找的那个第k个数，要么在首位为0的那一拨里，要么在首位为1的那一拨里，也就是说，我们只要比较首位为0的数的个数与k的大小，就知道应该是属于哪一拨！至于怎么计算首位为0的数的个数，这是排列组合的基本知识。首先N个0和M个1组成的所有数的数目为(N+M)!/(N!*M!),那么，固定首位为0，就是求N-1个0和M个1组成的所有数的数目，即(N-1+M)!/((N-1)!*M!)

　　有了这个基本的想法，我们接下来只要递归得做这样一件事情就行。以题中的输入2 2 2为例，对于初始情形，2个0和2个1共有6种组合，其中第一位为0的有3个，由k小于3，所以肯定这个数在首位为0的那一拨里，这时就可以输出第一位“0”，如果这里k大于3，那么输出首位为“1”，并在首位为1的那一拨里找第k-3大的，这么递归下去即可。

　　代码如下：

 

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 int jiecheng(int n)
 6 {
 7     if(n==1 || n==0) return 1;
 8     return n*jiecheng(n-1);    
 9 }
10 
11 int allNum(int n,int m)
12 {
13     return jiecheng(n+m)/(jiecheng(n)*jiecheng(m));
14 }
15 
16 void fun(int n,int m,int k)
17 {
18     int znum;
19     if(k>allNum(n,m)) return;
20     if(n==0)
21         znum=0;
22     else
23         znum = allNum(n-1,m);
24     if(m==0 && n==0)
25         return;
26     if(m==0 && n!=0)
27     {
28         for(int i=0; i<n; i++)
29             cout<<"0";
30         return;        
31     }
32     if(k>znum)//在以1开头的里面 
33     {
34         cout<<"1";
35         fun(n,m-1,k-znum);         
36     }
37     else
38     {
39         cout<<"0";
40         fun(n-1,m,k);
41     }
42 }
43 int main()
44 {
45     int T;
46     int N,M,K;
47     int total;
48     cin>>T;
49     while(T--)
50     {
51         cin>>N>>M>>K;
52         if(N==0 && M==0)
53         {
54             cout<<"Impossible"<<endl;
55             continue;      
56         }
57         if(N!=0 && M==0 && K==1)
58         {
59             for(int i=0; i<N; i++)
60                 cout<<"0";
61             cout<<endl;
62             continue;      
63         }
64         total = allNum(N,M);
65         if(K>total)
66         {
67             cout<<"Impossible"<<endl;
68             continue;
69         }
70         fun(N,M,K);
71         cout<<endl;
72     }
73     return 0;    
74 }
View Code

 

　　ps：这个代码比较丑陋，有一个重要的问题是，当N+M很大时，(N+M)!/(N!*M!)会超出int的表示范围，这时候需要用一些其他的高精度类型来表示，这算是本题的一个陷阱，不是核心内容，具体不表。


联系
我们