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 nk. 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

Problem Types: [Show]

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

Comments (Search)

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 descending order "

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.