题目P:轰炸坦克

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0
Special Judge

原比赛ID为:376。建议做题之前查看比赛简介,和比赛的前两条公告。以上包含的问题概不回答。

题目描述

在某一条线段区域上出现了若干坦克,坐标为1到n(保证n>1)。之所以说坐标是1到n,是因为我们也不知道坦克在哪,只知道每一辆都是在1到n闭区间的某个整数点上。

最开始坦克静止在自己的初始点上。现在你可以选若干点开始轰炸。

你轰炸的点x上如果有一辆没有被轰炸过的坦克,你的攻击会使这个坦克受损,并且这辆坦克会向x-1或者x+1两点逃窜,当然如果它在x=1处被轰炸,它就只能向x=2处逃窜,x=n的时候同理;如果你轰炸的点上有一辆受损的坦克,你的攻击会使这个坦克被销毁,此时坦克就不会再移动了。

现在给出线段的长度n,问你需要至少多少次轰炸才能让所有坦克都被销毁,也就是任意位置的坦克、无论逃窜到何处,都需要被轰炸两次。并输出一个合理的轰炸方案。

输入

包括一行,一个整数n如题。

输出

输出两行,第一行一个整数m,表示你需要m次轰炸。

第二行m个数,表示这m次轰炸你选择的轰炸位置。

输入样例1

2

输出样例1

3
1 2 1

输入样例2

3

输出样例2

4
2 1 3 2

样例解释

对于样例1,在两个位置都可能有坦克,轰炸1之后,2处可能有完整的坦克和受损的坦克,在轰炸2之后,2处不会有未被销毁的坦克,而1处可能会有2处逃窜来的受损坦克,所以需要再轰炸1一次。一共三次。当然,如果你选择轰炸2 1 2也是正确的答案。

对于样例2,在2处轰炸后只会在1、3处有坦克,对13轰炸后,只会在2处有受损的坦克,再对2进行轰炸。一共四次。

数据范围

保证2≤n≤100000。

相关推荐