记录编号	74312	评测结果	AAAAAAAAAAAAA
题目名称	二进制数01串	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2013-10-24 21:08:09	内存使用	0.28 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
ll C[51][51]={0};
void getC(void){
	C[0][0]=1;
	ll i,j;
	for(i=1;i<=50;i++){
		C[i][0]=1;
		for(j=1;j<=i;j++){
			C[i][j]=C[i-1][j-1]+C[i-1][j];
		}
	}
}
ll N,L,I;
//第i位就是右起第i位,从1开始计数
ll getbit(ll x,ll k){//得到x的二进制第k位
	return (x&(1<<(k-1)))!=0;
}
void outbit(ll x){//以二进制形式输出x
	ll i;
	for(i=N;i>=1;i--){
		printf("%lld",getbit(x,i));
	}
}
ll stat(ll x){//小于x且符合题意的数的个数
	ll sum=0;//前面有的1的个数,先算上最高位的1
	ll i,j;
	ll ans=0;
	for(i=N;i>=1&&sum-1<L;i--){
		if(getbit(x,i)==0) continue;
		else{//计算从这一位开始有差异的数的个数
			sum++;
			//第i位必须是0,已经放了sum-1个1
			//至多再放L-sum+1个1
			//接下来的i-1位可以任意放置不超过L-sum+1个1
			for(j=0;j<=L-sum+1;j++){
				ans+=C[i-1][j];
			}
		}
	}
	return ans;
}
ll find(ll left,ll right){//在[left,right]区间内找答案
	//若答案为ans,则stat(ans)=I-1且stat(ans+1)=I+1
	//stat值递增
	if(left==right) return left;
	ll mid=(left+right)&1?left+right+1:left+right;mid>>=1;
	if(stat(mid)<=I-1){
		return find(mid,right);
	}
	else{//就在[left,mid]中
		return find(left,mid-1);
	}
}
int main(){
	freopen("kimbits.in","r",stdin);
	freopen("kimbits.out","w",stdout);
	scanf("%lld%lld%lld",&N,&L,&I);
	getC();
	ll low,high;
	low=0;high=(1<<N)-1;
	outbit(find(low,high));printf("\n");
	return 0;
}