USACO: kimbits

## Problem:

Stringsobits
Kim Schrijvers
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.

`10011`

## Solution:

First, I tried to solve this problem recursively, while data set #7 always make my code exceed time limit(ETL),

## Source Code:

`Code Got Passed.`
```/*
ID: ***
LANG: JAVA
*/
import java.io.FileWriter;
import java.io.PrintWriter;

/**
* @author antonio081014
* @time Feb 21, 2013, 7:37:09 PM
*/
public class kimbits {

private int N;
private int L;
private long I;
private long[][] mark;
private PrintWriter out;

public static void main(String[] args) throws Exception {
kimbits main = new kimbits();
main.run();
System.exit(0);
}

private void run() throws Exception {
out = new PrintWriter(new FileWriter("kimbits.out"));

String[] strs = br.readLine().split("\\s");
N = Integer.parseInt(strs[0]);
L = Integer.parseInt(strs[1]);
I = Long.parseLong(strs[2]);
br.close();

mark = new long[N + 1][L + 1];
for (int i = 0; i <= N; i++)
mark[i][0] = 1L;
for (int i = 0; i <= L; i++) {
mark[0][i] = 1L;
}

for (int i = 1; i <= N; i++) {
for (int j = 1; j <= L; j++)
if (i >= j)
mark[i][j] = mark[i - 1][j - 1] + mark[i - 1][j];
else
mark[i][j] = mark[i][i];
}
// print(N, L, I);
printbit(N, L, I);
out.write('\n');
out.close();
}

private void print(int n, int l, int i) {
if (l > n)
l = n;
if (mark[n][l] == i) {
for (int j = 0; j < i; j++)
out.write('1');
for (int j = i; j < n; j++)
out.write('0');
} else {
if (i > mark[n - 1][l]) {
out.write('1');
print(n - 1, l - 1, (int) ((long) i - mark[n - 1][l]));
} else {
out.write('0');
}
}
}

void printbit(int i, int j, long K) {
if (j > i)
j = i;

if (K == mark[i][j]) {
for (int t = 1; t <= j; t++)
out.write('1');
for (int t = 1; t <= i - j; t++)
out.write('0');
} else {

if (K <= mark[i - 1][j]) {
out.write('0');
printbit(i - 1, j, K);
} else {
out.write('1');
printbit(i - 1, j - 1, K - mark[i - 1][j]);
}
}
}
}
```

```/*
ID: ***
LANG: JAVA
*/
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.PrintWriter;

public class kimbits {

private int L;
private int N;
private int I;
private String[] list;
private PrintWriter out;
private boolean flag;
private int top;

public static void main(String[] args) throws Exception {
kimbits main = new kimbits();
main.run();
System.exit(0);
}

private void run() throws Exception {
out = new PrintWriter(new BufferedWriter(new FileWriter("kimbits.out")));
String[] strs = br.readLine().split("\\s");
br.close();
flag = true;
N = Integer.parseInt(strs[0]);
L = Integer.parseInt(strs[1]);
I = Integer.parseInt(strs[2]);
// System.out.println(String.format("N %d, L %d, I %d", N, L, I));
list = new String[I];
top = 0;
rec("", 0);
out.close();
}

private void rec(String s, int ones) {
if (s.length() == N) {
if (ones <= L && flag)
list[top++] = s;
if (top == I && flag) {
out.write(s + "\n");
flag = false;
}
return;
}
if (flag == false)
return;
rec(s + "0", ones);
rec(s + "1", ones + 1);
}
}
```