USACO/Stringsobits.c at master · sunheehnus/USACO · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/*
ID: sunheco1
LANG: C
TASK: kimbits
*/
#include<stdio.h>
int result[33];
unsigned int CC(int j,int i)
{
	unsigned int k;
	int visit[33],temp,l;
	if(i>=j>>1)
		i=j-i;
	temp=i;
	for(l=2;l<=i;l++)
		visit[l]=0;
	for(k=1;i>0;i--,j--)
	{
		k*=j;
		for(l=2;l<=temp;l++)
		{
			if(visit[l]==0&&k%l==0)
			{
				k/=l;
				visit[l]=1;
			}
		}
	}
	for(l=2;l<=temp;l++)
	{
		if(visit[l]==0&&k%l==0)
		{
			k/=l;
			visit[l]=1;
		}
	}
	return k;
}
int main()
{
	unsigned int N,L,I,i,j,k,tot;
	unsigned int total[33][33];
	FILE *fin  = fopen ("kimbits.in", "r");
    FILE *fout = fopen ("kimbits.out", "w");
	fscanf(fin,"%d %d %u",&N,&L,&I);
	if(I==1)
	{
		while(N)
		{
			fprintf(fout,"%d",0);
			N--;
		}
		fprintf(fout,"\n");
		return 0;
	}
	for(j=0;j<=32;j++)
	{
		total[j][0]=1;
	}
	for(i=1;i<=32;i++)
	{
		for(j=1;j<=i;j++)
		{
			total[i][j]=CC(i,j);
		}
	}
	for(i=1;;i++)
	{
		for(k=0,tot=0;k<=L&&k<i;k++)
		{
			tot+=total[i-1][k];
		}
		for(k=0;k<L&&k<i;k++)
		{
			tot+=total[i-1][k];
		}
		if(tot>=I)
			break;
	}
	for(k=0,tot=0;k<=L&&k<i;k++)
	{
		tot+=total[i-1][k];
	}
	result[i]=1;
	L--;
	I-=tot;
	I--;
	while(I)
	{
		i--;
		for(k=0,tot=0;k<=L&&k<i;k++)
		{
			tot+=total[i-1][k];
		}
		if(tot>I)
			continue;
		I-=tot;
		result[i]=1;
		L--;
	}
	while(N)
	{
		fprintf(fout,"%d",result[N]);
		N--;
	}
	fprintf(fout,"\n");
	return 0;
}