Stringsobits 

                                                  Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB 

                                                            Total submit users: 40, Accepted users: 22 

                                                               Problem 10490 : No special judgement 

Problem description

Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.

This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.

 

Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.

 

Input

A single line with three space separated integers: N, L, and I.

 

Output

A single line containing the integer that represents the Ith element from the order set, as described.

 

Sample Input

5 3 19

 

Sample Output

10011

 

Problem Source

HNU Contest

 

 

搞了一上午终于AC了，一开始就一个个试探着作，果然严重超时，因为N最大为31，I最大就会超过2^31，显然不能一个个试探着做。总感觉这总能用一种式子算出来，先看输出样例是怎么得出来的：

5         3  19

按照顺序将集合依次展开：

00000

00001

00010

00011

00100

00101

00110

00111

01000

01001

01010

01011

01100

01101

01110

10000

10001

10010

10011

.

.

.

我们关注一下这样的数字： 00000  01000  10000 我们总能计算出这样的数字排在的几位，怎么得出来的呢？

拿10000 作为例子吧。我们将最右边的“1”的位数记为S，10000前面的数的所有1都排列在前S-1上，那么10000前面的数就应该有 C(S-1,0)+C(S-1,1)+C(S-1,2)+C(S-1,3) = 15个。而19 > 10000 所以我们可以确定S位上必为“1”。以此类推：S-1位、S-2位、S-3位…..1。代码写的有点乱。

#include
     
       #include
      
        #include
       
         using namespace std; char res[40]; __int64 b[40][40]; int main() {
   int i,j,k,N,L,s,t;     __int64 I,count,sum,kk; for(i=0;i<=32;i++) b[i][0]=b[0][i]=1; for(i=1;i<=32;i++)     {
   for(j=1;j<=32;j++)             b[i][j]=b[i][j-1]*(i-j+1)/j;     } while(scanf("%d %d %I64d",&N,&L,&I)!=EOF)     {
   /*kk=0;         for(i=0;i<=L;i++)             kk+=b[N][i];         printf("%I64d\n",kk);*/         memset(res,0,sizeof(res));         count=sum=0;         s=L;//记录还有几个“1”没有确定         while(1)         {
               sum=1; t=0; while(count+sum
        
         < t-1 ? s-1 : t-1; for(i=0;i<=k;i++) sum+=b[t-1][i];             }             res[t]=1; if(--s <= 0) break;            } for(i=N;i>=1;i--) printf("%d",res[i]);         printf("\n");     } return 0; }