[TIOJ 1358] 丟失的數

作法：

考慮這樣的問法：把這 n-1 的數的最右邊一位都問過一次，那麼就可以把問題從 n 變成 (n+1)/2 的問題了。直覺上因為每次都能保證把剩餘的數砍半，所以這樣會是最優的。

以下給個大概的證明：

首先，一定有其中一個 bit ，在 n-1 個數都有被問到，如果沒有的話，回答者可以讓每個 bit 都還剩下 0 或 1 兩種可能，例如這個 bit 在 n 個數裡照理說要有 x 個 0 和 y 個 1 ，那麼他只要回答 <=x-1 次 0 和 <=y-1 次 1 就好了。所以一定有一個 bit 被問了 n-1 次，如果不是最高位的 bit ，那問題的規模就可以被砍半，如果是的話，因為最高位的 bit 的 0 和 1 個數可能會差到大於 1 ，所以回答者只要控制把答案引向「會讓剩餘的可能數個數比較大」的方向，就會讓問題剩下的規模比 n 的一半多，所以這樣就不會是最佳的問法了。

code :

#include<bits/stdc++.h>
using namespace std;
 
int f(int x)
{
    if(x==1) return 0 ;
    return x-1+f((x+1)/2) ;
}
 
main()
{
    int n ;
    while(scanf("%d",&n)!=EOF) printf("%d\n",f(n)) ;
}