P7168: 终极BOSS

---

【题目描述】

【题目描述】
你被困在你最喜欢的电子游戏的BOSS级别。BOSS之战发生在一个圆形房间里，房间周围均匀地排列着n根可摧毁的柱子。BOSS躲在一根不知名的柱子后面。然后你们两个轮流进行。
首先，轮到你时，你可以把一枚炸弹扔到其中一根柱子下。如果BOSS在那根柱子后面，或者在相邻的柱子后面，炸弹就会击败BOSS。
接下来，如果BOSS没有被击败，它可能会留在原地，或者利用轮到它的回合移动到与其当前位置相邻的柱子上。在爆炸的烟雾中，你看不到这种运动。
你上一次试图打败BOSS时失败了，因为你的炸弹用完了。这一次，你想收集足够的炸弹，以确保无论BOSS做什么，你都能打败它。在最坏的情况下，你需要多少炸弹才能打败BOSS？示例见图1。

图1：n=4的示例。在这种情况下，两枚炸弹就足够了。灰色柱子代表老板无法藏身的柱子。炸弹用黑色表示。
【输入】
输入包括：
一行中有一个整数n（1≤n≤100），即房间中柱子的数量。
【输出】
在最坏的情况下输出击败BOSS所需的最少炸弹数量。
【样本输入1】
4
【样本输出1】
2
【样本输入2】
7
【样本输出2】
5

题目类型~

初级 难度1.9 

咻咻~

提交答案 状态 返回