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

PROGRAM NAME: kimbits

INPUT FORMAT

SAMPLE INPUT (file kimbits.in)

5 3 19

OUTPUT FORMAT

SAMPLE OUTPUT (file kimbits.out)

10011

題意：
找出N為的二進制數(shù)中1個數(shù)小于等于L的第I個數(shù)

代碼如下：

/*
LANG: C
TASK: kimbits
*/
#include<stdio.h>
long long cmb[33][33];
void setCmb(long long n)
{
    long long i, j;
    for (i = 0; i <= n; i++)//零位數(shù)中'1'個數(shù)為0的情況數(shù)是1 
    {
        cmb[i][0] = 1;
        //cmb[i][i+1] = 0;
    }
    for (i = 1; i <= n; i++)//i位數(shù)中恰好有j個'1'的個數(shù) 
    {
        for (j = 1; j <= i; j++)
        {
            cmb[i][j] = cmb[i-1][j-1] + cmb[i-1][j];
        }
    }
    for (i = 0; i <= n; i++)//i位數(shù)中'1'個數(shù)小于等于j的情況數(shù) 
    {
        for (j = 1; j <= n; j++)
        {
            cmb[i][j] += cmb[i][j-1];
        }
    }
}
void find(long long n, long long m, long long th)
{
    long long i;
    for (i = n; i >= 1; i--)
    {
        //如果i-1位數(shù)中1個數(shù)大于等于th,說明前i-1位就能滿足th個'1'個數(shù)小于等于m的數(shù)。
        if (cmb[i-1][m] >= th) 
        {
            printf("0");
        }
        else//否則，說明第i位是1，要利用到第i位 
        {
            printf("1");
            //情況數(shù)th減去第i位是0的前i-1位'1'個數(shù)小于等于m的情況數(shù),剩下第i位是1，前i-1位'1'個數(shù)小于等于m-1的情況數(shù) 
            //已經(jīng)定了一個'1'，接下來找小于等于m-1個'1'的情況
            th -= cmb[i-1][m--];            
        }
    }
    printf("\n");
}
int main()
{
    freopen("kimbits.in", "r", stdin), freopen("kimbits.out", "w", stdout);
    long long n, m, th;
    scanf("%lld%lld%lld", &n, &m, &th);
    setCmb(n);
    find(n, m, th);
    fclose(stdin), fclose(stdout);
    //system("pause");
    return 0;
}