娱乐 每 日 算 法 挑 战【特别篇（x）】

[原初の冷火]

主要今天要参加一个不得不参加的校赛

在最后的30分钟实在做不出来了

决定问问万能的网友（x）

54分更新：艹   原来这里有好无脑的方式做   现在已经做出来了

题目描述

Cubercsl 很喜欢 01 字符串，就像“她喜欢大海”，这一天他想送她一个由 01 字符串组成的集合。

他自然是希望这个集合越多样化越大越好。所以他希望这个集合满足以下条件。

• 每个字符串由 0 和 1 组成。
• 每个字符串长度在 1 到 n 之间，且两两长度不同。
• 集合中任何一个字符串都不是其他字符串的子串。

请你帮他找到满足他要求的最大的集合。
字符串 a 是 b 的子串当且仅当从 b 的头部和尾部删除一些字符（可以是零个或者所有）能得到的 a。

输入描述:

仅一行，包含一个整数 n(1≤n≤300)。

输出描述:

第一行输出这个集合的大小 k。
接下来 k 行每行输出一个 01 字符串，表示这个集合的一个元素。
答案不唯一，任何符合要求的答案都会被判为正确。

示例1

输入

1

输出

1
1

示例2

输入

5

输出

4
00
110
1010
11111

（反正菜鸡如我已经是做不来了）

四月 18, 2020，由原初の冷火修改

[yhz012]

霍夫曼编码

啊不对，霍夫曼只保证了不是前缀……

[Mr.K 018]

300?

才300的话二话不说先交一发暴搜再说√

不暴力搜索的话，我想想是不是能dp一下……

四月 18, 2020，由Mr.K 018修改

[原初の冷火]

4 小时前, Mr.K 018 说道:

300?

才300的话二话不说先交一发暴搜再说√

不暴力搜索的话，我想想是不是能dp一下……

其实啊

可以

00

010

0110

01110

……

[Mr.K 018]

9 小时前, 原初の冷火 说道:

其实啊

可以

00

010

0110

01110

……

啊？！

啊，这……

[ppzt]

20 小时前, 原初の冷火 说道:

其实啊

可以

00

010

0110

01110

……

那么问题就变成了证明最长N位的满足要求的集合 其元素数最大是N-1？

哦没事了 要求长度两两不一 那显然最大是N-1 因为不能有1位的

四月 19, 2020，由ppzt修改

[原初の冷火]

13 小时前, ppzt 说道:

那么问题就变成了证明最长N位的满足要求的集合 其元素数最大是N-1？

哦没事了 要求长度两两不一 那显然最大是N-1 因为不能有1位的

n=2和1的时候是可以有一位的