This is a explanation of this problem from USACO's training website. I have converted it to markdown. Please do not just copy code; you will not learn anything; at least type it out and understand so you can do it yourself in the future!

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 FORMAT

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

### SAMPLE INPUT (file kimbits.in)

``````5 3 19
``````

### OUTPUT FORMAT

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

### SAMPLE OUTPUT (file kimbits.out)

``````10011
``````

Java

C++

Pascal

## ANALYSIS

Russ Cox

Suppose we knew how to calculate the size of the set of binary numbers for a given nbits and nones. That is, suppose we have a function sizeofset(n, m) that returns the number of n-bit binary numbers that have at most m ones in them.

Then we can solve the problem as follows. We’re looking for the ith element in the set of size n with m bits. This set has two parts: the numbers the start with zero, and the numbers that start with one. There are sizeofset(n-1, m) numbers that start with zero and have at most m one bits, and there are sizeofset(n-1, m-1) numbers that start with one and have at most m one bits.

So if the index is less than sizeofset(n-1, m), the number in question occurs in the part of the set that is numbers that start with zero. Otherwise, it starts with a one.

This lends itself to a nice recursive solution, implemented by “printbits”.

The only difficult part left is calculating “sizeofset”. We can do this by dynamic programming using the property described above:

``````sizeofset(n, m) = sizeofset(n-1, m) + sizeofset(n-1, m-1)
``````

and sizeofset(0, m) = 1 for all m. We use double’s throughout for bits, but that’s overkill given the rewritten problem that requires only 31 bits intead of 32.

``````/*
PROG: kimbits
ID: rsc001
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

FILE *fout;

/* calculate binomial coefficient (n choose k) */
double sizeofset[33][33];

void
initsizeofset(void)
{
int i, j;

for(j=0; j<=32; j++)
sizeofset[0][j] = 1;

for(i=1; i<=32; i++)
for(j=0; j<=32; j++)
if(j == 0)
sizeofset[i][j] = 1;
else
sizeofset[i][j] = sizeofset[i-1][j-1] + sizeofset[i-1][j];
}

void
printbits(int nbits, int nones, double index)
{
double s;

if(nbits == 0)
return;

s = sizeofset[nbits-1][nones];
if(s <= index) {
fprintf(fout, "1");
printbits(nbits-1, nones-1, index-s);
} else {
fprintf(fout, "0");
printbits(nbits-1, nones, index);
}
}

void
main(void)
{
FILE *fin;
int nbits, nones;
double index;

fin = fopen("kimbits.in", "r");
fout = fopen("kimbits.out", "w");
assert(fin != NULL && fout != NULL);

initsizeofset();
fscanf(fin, "%d %d %lf", &nbits, &nones, &index);
printbits(nbits, nones, index-1);
fprintf(fout, "\n");

exit(0);
}
``````