Test
Time limit2sMemory limit256 MB
List all 2^n binary strings of length n so that the number of ones never increases and consecutive strings differ in at most two positions.
- Level
Medium7 of 10
- Topics
- Bit manipulation, Combinatorics, Greedy, Implementation
- Solved
- No attempts yet
Problem
Artem is taking an educational test in an electronic system. A test question contains n statements, some of which are true and must be marked with checkboxes. After setting some of the checkboxes, the answer can be checked for correctness. An answer to a question is considered correct if all true statements are marked with checkboxes and all false ones are not.
Artem is too lazy to think, so he decided to simply enumerate all possible checkbox arrangements. For this, he makes a list of all 2 * n arrangements of the checkboxes. Each arrangement of checkboxes must appear in the list exactly once.
Intuitively, he thinks there are many true statements, so he wants to enumerate the arrangements in decreasing order of the number of set checkboxes. Besides, Artem is very lazy and wants the number of positions in which two consecutive arrangements differ to be at most two. Help Artem.
Input
The first line contains an integer n (1 ≤ n ≤ 16).
Output
Print 2 * n lines. In the i-th line, print n characters 0 or 1, the state of each checkbox for the i-th answer, with 1 for a set checkbox and 0 for an unset one. The number of ones in the answers must be non-increasing. The number of positions in which two adjacent lines differ must be at most two.