[測試題]打地鼠

Description

小明聽說打地鼠是一件很好玩的游戲，于是他也開始打地鼠。地鼠只有一只，而且一共有N個洞，編號為1到N排成一排，兩邊是墻壁，小明當然不可能百分百打到，因為他不知道地鼠在哪個洞。小明只能在白天打地鼠，而且每次打了都覺得好累，感覺再也不會打了，必須休息到第二天才能再次打地鼠，也就是說他每天只有一次打地鼠的機會。

地鼠非常聰明，為了盡可能的不被打到，它每天晚上都會跑向相鄰的兩個洞中的一個，如果一邊是墻壁就只有往另一邊跑，而且它很固執，每天晚上肯定會跑，也就是說不會連續呆在同一個洞。

盡管小明很累，但是他明白要想拿到一等獎，就必須打到地鼠，所以他想知道怎樣才能在最短的天數內保證肯定打到地鼠。

Input

輸入文件mouse只有一行，該行有一個整數N，表示N個洞并排在一起。地鼠在隨機一個洞。

Output

輸出文件mouse.out只有一行，該行有一個整數，表示小明肯定能打中至少需要的天數。

Sample Input

4

Sample Output

4

Hint

40% n<=10

100% n<=100.

題解

? ?這道題首先是要考慮怎樣才能夠保證一定能夠打中。如果每天選擇洞的規律和地鼠移動的規律一樣，也就是每天都選前一天相鄰的一個洞，那么可以發現，每次你選擇的洞口和地鼠所在洞口的距離要么不變，要么增加二或者減少二，按這樣從一邊墻壁檢查到另一邊墻壁，如果沒有發現地鼠，那就說明地鼠的初始位置和你的初始檢查距離為奇數，這個時候再重復檢查一次你剛檢查過的洞口，那么因為地鼠必須要移動，你們的距離就修改成了偶數，這樣再從另一邊檢查回來，就保證一定能夠發現地鼠。這樣算下來的結果是$2N$。

??但是可以再分析一下，第一遍掃描的$N$次的意義在與檢查你和地鼠的距離是否為偶數，第二次的意義在于把奇數變為偶數。那么第一次完全可以只從$N-1$掃描到$2$（因為地鼠如果在$N$號洞或者$1$號洞與你的距離都為奇數，和第一次的任務沒有關系），第二次也從$2$掃描到$N-1$（因為距離如果是偶數那么相遇時肯定是地鼠與你相向運動，也就是地鼠從相遇點后面過來的，所以不可能會在$1$號和$N$號洞相遇）。最后再考慮只有$1$，和$2$兩個洞這兩種特殊情況。

來自@Z-Y-Y-S的一個例子：

（感謝@Z-Y-Y-S！！）

?

//It is made by Awson on 2017.9.19
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Abs(a) ((a) < 0 ? (-(a)) : (a))
#define lowbit(x) ((x)&(-(x)))
using namespace std;

int n;
void work() {
    if (n <= 2) printf("%d\n", n);
    else printf("%d\n", 2*(n-2));
}
int main() {
    while (~scanf("%d", &n))
        work();
    return 0;
}

?