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'.
PROGRAM NAME: kimbits
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
Analysis
At first glance of it, it is nice for a single integer saving situations rather than string which is told in the description. But for the 10th data, it seems small for 31 31 2^31. To deal with it, take it away and print answer independently. For other situations, find the maximum bit recursively.
Code
/**//*
ID:braytay1
PROG:kimbits
LANG:C++
*/
#include <iostream>
#include <fstream>
using namespace std;
int cmb_lab[34][34];
int cmb_num[34][34];
int n,l;
long long int no;
int count(long long int s)
{
int ret=0;
while (s){
s&=(s-1);
ret++;
}
return ret;
}
long long int dealing(long long int a,int l1){
if (a<=1) return 0;
int cur;
long int cur_sum=0;
for (cur=0;cur<=n;cur++){
cur_sum+=cmb_num[cur][l1 ];
if (cur_sum>=a) break;
}
long long int leave;
long long int res;
leave=a-cur_sum+cmb_num[cur][l1];
res=1<<(cur-1);
res+=dealing(leave,l1-1);
return res;
}
int main(){
ifstream fin("kimbits.in");
ofstream fout("kimbits.out");
fin>>n>>l>>no;
if (no==1){
for (int i=1;i<=n;i++)
fout<<0;
fout<<endl;
return 0;
}
memset(cmb_lab,0,sizeof(cmb_lab));
cmb_lab[0][0]=1;
for (int i=1;i<=32;i++){
for (int j=0;j<=32;j++){
if (j==0||j==i) cmb_lab[i][j]=1;
else cmb_lab[i][j]=cmb_lab[i-1][j-1]+cmb_lab[i-1][j];
}
}
for (int k=0;k<=l;k++){
if (k>0) cmb_num[0][k]=1;
else cmb_num[0][k]=0;
for (int i=1;i<=n;i++){
int sum=0;
for (int j=0;j<k;j++){
sum+=cmb_lab[i-1][j];
}
cmb_num[i][k]=sum;
}
}
long long int res;
if (n==31&&l==31) {
res=no-1;
for (int i=n-1;i>=0;i--){
if (res&(1<<i)) fout<<1;
else fout<<0;
}
fout<<endl;
return 0;
}
res=dealing(no,l);
for (int i=n-1;i>=0;i--){
if (res&(1<<i)) fout<<1;
else fout<<0;
}
fout<<endl;
return 0;
}