ham

The Hamming distance between two binary sequences is equal to the number of positions having different values in the two sequences. E.g. Lets take the following two sequences of length N=10:
A: 0 1 0 0 1 0 1 0 0 0
B: 1 1 0 1 0 1 0 1 0 0
The Hamming distance between A and B is 6.

Task

Knowing length N and distance H, write a program that determines all sequences of length N that are at a given Hamming distance H from a given sequence.

Input Data

Input file ham.in contains two lines. Line one contains positive integers N and H separated by a space. Line two contains N binary digits representing the given sequence.

Output Data

Output file ham.out will contain the requested sequences, one sequence per line. The sequences will be in lexical-graphical order. The elements of a sequence (located on the same line) won't be separated by spaces.

Constraints and Statements

• 0 < H <= N <= 18

Time limit: 0.2 seconds/test

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com