巡逻的士兵

#include <iostream>
#include <map>

using namespace std;
typedef long long ll;
map<ll,ll> m;

ll f(ll n)
{
    if(n<3) return 0;
    if(n==3) return 1;
    if(m.find(n)!=m.end()) return m[n];
    return m[n]=f(n/2)+f((n+1)/2);
}

int main()
{
    ll n;
    while(cin>>n,n!=0)
        cout<<f(n)<<endl;
    return 0;
}

计算情况数。

每一次都筛掉随机一半，所以把一次选择变成被拆分后的两次选择相加，可以想到，如果人数是偶数，(n＋1)/2并不影响结果，而如果人数是奇数，那一定会被拆成两个连续的数字相加，此时(n＋1)/2可以表示较大的那个数