[ codeforces ] ACM ICPC 2015–2016, Northeastern European Regional J Jump

題目:
http://codeforces.com/gym/100851
互動題，猜字串遊戲，輸入n表示字串長度，你要輸出一個字串給他
他會輸入你猜的字串的回傳值，只有當猜對的字元數=n/2或n時回傳值才會是猜對的字元數，否則回傳值是0
n<=1000，你要在n+500次內猜出他的字串是什麼

解法:
根據斯特靈(Stirling)公式

可知隨機找出剛好一半字元是正確的機率近似於

幾乎可以在sqrt(n)次內找出剛好一半字元是正確的字串，接下因為字串有一半是錯的，所以可以把字元分成兩堆，設字串為s，分法如下:

分成A、B兩堆
設s[0]屬於A，對於s[1]~s[n-1]，把他們分別跟s[0]取not，假設現在是第i個字元
s[0]^=1;
s[i]^=1;
輸出答案進行判斷，如果回傳值仍是n/2表示s[i]屬於A，否則s[i]屬於B
如果過程中出現回傳值=n就結束程式

最後先對A裡面所有字元取not，如果不是答案再把整個字串取not即可
記住記得要清空輸出的緩衝區確保及時輸出
c用fflush(stdout);
c++用cout.flush();

code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

#include<bits/stdc++.h> using namespace std; int n,an; char s[1005]; bool is[1005]; int main(){ srand(time(0)); scanf("%d",&n); for(;;){ for(int i=0;i<n;++i){ s[i]=rand()%2+'0'; } puts(s);fflush(stdout); scanf("%d",&an); if(an)break; } if(an==n)return 0; s[0]^=1; for(int i=1;i<n;++i){ s[i]^=1; puts(s);fflush(stdout); scanf("%d",&an); if(an==n)return 0; if(an)is[i]=1; s[i]^=1; } s[0]^=1; for(int i=0;i<n;++i){ if(is[i])s[i]^=1; } puts(s);fflush(stdout); scanf("%d",&an); if(an==n)return 0; for(int i=0;i<n;++i){ s[i]^=1; } puts(s);fflush(stdout); scanf("%d",&an); return 0; }