3614 - 侦察兵
N个士兵站成一列，他们的编号分别为1......n,要求选出一些士兵，送他们去侦察.
为了达成这个目的，要执行若干次下列的操作： 如果这列的士兵不少于3个。则把所有的奇数编号的剔除
或者把所有偶数编号的剔除。
经过上述操作后，如果这列士兵数目刚好是3，则将他们送去侦察，如果小于个，则重新来过。
问题是，有被选去侦察的士兵有多少种？
注意，如果队列小于3个，不做考虑
0<=N<=10 000 000
Input
每一行输入N，直到输入流程结束。
Output
每行输出为对应的种类
Examples
Input
10 4
Output
2 0
Solution C
#include <stdio.h> int solve(int n) { if(n<3) return 0; else if(n==3) return 1; else return (solve(n/2)+solve(n-n/2)); } int main() { int n; while(scanf("%d",&n)!=EOF) { printf("%d\n",solve(n)); } return 0; }
Solution C++
#include <bits/stdc++.h> using namespace std; int d[10000005]; int dp(int n) { if (d[n]!=-1) return d[n]; else return d[n]=dp(n/2)+dp(n-n/2); } int main() { int n; while(~scanf("%d",&n)){ memset(d,-1,sizeof(d)); d[0]=d[1]=d[2]=0; d[3]=1; printf("%d\n",dp(n)); } return 0; }