1394. 兽笼

【题目背景】

一排兽舍用钢丝网隔成了m间笼子,用来养老虎,由于老虎性格凶猛,隔着钢丝网也可能把隔壁老虎抓伤,所以不能连续两间笼子都圈养老虎.

第一问:求最多能养多少只老虎

第二问:给出圈养老虎的所有方案.

【输入文件】

输入文件 tiger.in 第一行是一个整数 m （ m<=12 ）

【输出文件】

输出文件 tiger.out 的第一行包含一个整数 T ，下面接着有n行,每行是一种圈养老虎的方案。

【样例输入】

5

【样例输出】

3
00000
00001
00010
00100
00101
01000
01001
01010
10000
10001
10010
10100
10101

【样例解释】            

长度为5的笼舍,最多养3只老虎,象下面最后一行的方案10101,表示1,3,5号笼子养老虎,2,4号笼子空着            

第1种方案00000,表示一只老虎也不养,第2种方案00001,表示1号笼(从右边开始编号)养老虎,其它的笼子不养,依此类推.            

输出方案按字典序排序.