Thomas

시간 제한1초메모리 제한2048 MB

요약

정수 n(1 이상 15 이하)이 주어질 때, 서로 정확히 한 자리만 다른 두 문자열이 없는 n비트 이진 문자열 집합의 최대 크기와 그 집합을 출력한다.

난이도: 보통10점 중 6점
유형: 그리디, 비트 연산, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

You are given an integer $n$ . Find the largest set of distinct binary strings of length $n$ such that no two strings in the set differ at exactly one index.

For example, for $n=5$ , the strings $10001$ and $11001$ could not both be in the set, because they only differ in their second positions.

입력

The first and only line of the input contains one integer $n$ ( $1 \leq n \leq 15$ ) --- the size of the binary strings in the set.

출력

The first line of output should contain a single integer $k$ ( $0 \leq k \leq 2^n$ ) --- the number of strings in your set.

Each of the next $k$ lines should contain a single binary string of size $n$ --- one of the strings in your set. No two of these strings should be equal, or differ in exactly one position.

If there are multiple solutions, you may print any.

힌트

In the first sample case, we choose the set $\\{0\\}$ , and in the second sample case, we choose the set $\\{00, 11\\}$ . Neither of these sets contain two strings that differ in exactly one position, and we can show that they are both of maximal size for their given $n$ .

예제2

예제 1
입력
```
1
```
예상 출력
```
1
0
```
예제 2
입력
```
2
```
예상 출력
```
2
00
11
```