兽笼

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 tiger.in 输出文件 tiger.out

【题目背景】

一排兽舍用钢丝网隔成了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号笼(从右边开始编号)养老虎,其它的笼子不养,依此类推.            

输出方案按字典序排序.