### USACO help again

Posted:

**Mon Dec 20, 2004 7:43 pm**I'm on problem kimbits,

I think it has something to do with the piece of code with comment, but I really don't know. Does anyone know where I'm going wrong, or a different way to figure out the number of strings of length temp that fits the description? Thanks.

And I'm using the algorithm mentioned here after trying about 10 other ways to do the problem. I'm having trouble though on test case 12 -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

, I don't know where to start debugging my program ---------------------------

31 26 123456789

--------------------------

Here are the respective outputs:

----- our output ---------

0000111010110111100110100010100

---- your output ---------

0001000001100110000110010110101

--------------------------

Code: Select all

```
#include <stdio.h>
#include <math.h>
FILE *input, *output;
long long numbits, numones, ith, count, total;
long long wrong[2], fact[33], string[33];
long long fac(long long num, long long start)
{
long long i, f=1;
if(fact[num] > 0 && start == 1)
return fact[num];
for(i=start+1; i<= num; i++)
f *= i;
if(start == 1)
fact[num] = f;
return f;
}
int main()
{
long long i, length, numright=0, k, temp=-1, j, numwrong, ornum;
input = fopen("kimbits.in", "r");
output = fopen("kimbits.out", "w");
fscanf(input, "%lld %lld %lld\n", &numbits, &numones, &ith);
ith--;
for(j=1; j<numbits; j++)
{
temp = numbits-j;
numright = 0;
for(i=0; i<=numones && i<=temp; i++) //figure out the number of strings of length temp that fit //the decription
{
if(i > numbits-i)
numright += fac(temp, i)/fac(temp-i, 1);
else
numright += fac(temp, temp-i)/fac(i, 1);
}
if(ith >= numright)
{
ith -= numright;
numones--;
fprintf(output, "1");
}
else
fprintf(output, "0");
}
if(ith >= 1)
{
fprintf(output, "1");
}
else
fprintf(output, "0");
fprintf(output, "\n");
return 0;
}
```