传送门

Virtual Judge


Description

You are stuck at a boss level of your favourite video game. The boss battle happens in a circular room with n indestructible pillars arranged evenly around the room. The boss hides behind an unknown pillar. Then the two of you proceed in turns.

  • First, in your turn, you can throw a bomb past one of the pillars. The bomb will defeat the boss if it is behind that pillar, or either of the adjacent pillars.

  • Next, if the boss was not defeated, it may either stay where it is, or use its turn to move to a pillar that is adjacent to its current position. With the smoke of the explosion you cannot see this movement.

The last time you tried to beat the boss you failed because you ran out of bombs. This time you want to gather enough bombs to make sure that whatever the boss does you will be able to beat it. What is the minimum number of bombs you need in order to defeat the boss in the worst case? See Figure 1 for an example.

Figure 1:

Example for n=4. In this case 2 bombs are enough. Grey pillars represent pillars where the boss cannot be hiding. The bomb is represented in black.


Input

The input consists of:

One line with a single integer n (1 \le n \le 100), the number of pillars in the room.

Output

Output the minimum number of bombs needed to defeat the boss in the worst case.


Sample Input 1

4

Sample Output 1

2

Sample Input 2

7

Sample Output 2

5


题目大意:

有环形的n根柱子,只有一根柱子后面有boss,每次向一根柱子投一个炸弹,炸弹波及范围为那根柱子和相邻的柱子,若boss在这三根柱子后面,则boss被炸死,若boss没有被炸死,则boss会选择原地不动或者走到相邻的柱子,问最坏情况下要用多少个炸弹。

解题思路:

n \le 3时,答案是1

n > 3时,观察可得答案是n−2。因为在每次扔完炸弹后,第二次扔在那个炸弹的顺时针数两个的位置,这样boss不可能在的位置就会增加一个(不可能存在的位置为一个连续的区间,顺时针最前增加两个位置,最后减少一个位置),最后剩下三个不确定的位置时,把炸弹扔到中间的柱子即可。

Code:

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
int main(){int n=read();write(n<3?1:n-2);}