1996 Canadian Computing Competition, Stage 1

Problem C: Pattern Generator

Write a program that repeatedly reads two numbers n and k and prints all bit patterns of length n with k ones in descending order (when the bit patterns are considered as binary numbers). You may assume that 30 ≥ n > 0, 8 > k ≥ 0, and n ≥ k. The first number in the input gives the number of pairs n and k. The numbers n and k are separated by a single space. Leading zeroes in a bit pattern should be included. See the example below.

Sample Input

3
2 1
2 0
4 2

Sample Output

The bit patterns are
10
01

The bit patterns are
00

The bit patterns are
1100
1010
1001
0110
0101
0011

All Submissions
Best Solutions

Point Value: 10
Time Limit: 10.00s
Memory Limit: 16M
Added: Sep 28, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Can somebody help me check my code?
My samples are right but I just cannot get any point.Thanks a lot !

Which of your own test cases have you tried?

Your logic is simply incorrect.

Do you need to use recursion for this problem?
Only asking because it says in problem type "recursion" and a comment says you need to use recursion

You can use anything you want (other than hardcoding); the problem type is just a very general umbrella. 

Can someone check my code? I'm pretty sure the algorithm works. Thanks.

You go out of bounds.

Can you be A little bit more detail? Is it array out of bound or int out of bound? 

Generally, out of bounds implies array. If I meant you exceeded the limits of a numeric type, I'd say that you overflowed (on ints or doubles) or underflowed (on doubles).

Edit: However, after looking a bit more, it's not your only problem. Try some more test cases.

Thanks. My code works.

I'm pretty sure I'm doing this problem right, can someone help me?

":"
lol
//made the same mistake

also your algorithm does not print the patterns in the order specifieddsdss

"Write a program that prints all bit patterns of length n with k ones in [i][b] descending order [/b][/i]" 

Still doesn't work. Does that mean i did this problem right >_<

What's wrong with my program? I tried it with the test cases and I got them right, but I got wrong answer for it.

~helios26

Try some more test cases. Trying all (n,k) with 0 <= k <= n <= 5 might be a good starting point.

I'm still getting 0/10 and I tried all of the n, k under 5 and I also checked some bigger nums. I found my error with clearing one of the strings, but nothing else. Any hints?

Thanks,
~helios26

I'm afraid your algorithm just isn't correct (though it does work on some cases, such as small ones). You need to use a concept known as "recursion".

do we just output nothing if no patterns fit the given conditions (n and k)?

How is that possible?

when k>n

"You may assume that 30 >= n > 0, 8 > k >= 0, and n >= k"

Maybe read the problem statement more carefully next time.