26. G.雷精靈的煩惱(互動題)
0 Judge
Code: 0
G.雷精靈的煩惱(互動題)
題目敘述
出外走一走後身心舒爽許多，回到伊布之家卻看到悶悶不樂的雷精靈在一旁的房間裡。火精靈上前詢問，才知道原來在表演時，雷精靈收藏的一個皮球不見了。
雷精靈原本有$2^k$個球，每個球上都有編號，依序由編號$0$至編號$2^k-1$。但是這些球太多了而且都沒有照順序擺好，讓他很傷腦筋不知道是編號幾號的球不見了。在一旁的太陽精靈直搖頭，如果是他絕對不會發生這種事的。
此時熱心的皮卡丘自告奮勇想幫助雷精靈！不果這工程太過浩大了，需要邀請你來一起聯手幫皮卡丘完成任務！再來我們需要知道與皮卡丘溝通的方法。在本題，你需要引入標頭檔Pikachu.h來取得溝通管道，再來介紹一下內含的翻譯工具來幫你跟皮卡丘對話：
| 翻譯工具 | |
|---|---|
| 溝通的函數 | 功能說明 |
int Init() |
回傳雷精靈原本有幾個皮球，保證這個數一定是2的某個次方。如果你重複問的話皮卡丘會跟你翻臉導致任務失敗，請小心！ |
int GetBit(int k,int b) |
向皮卡丘訊問第k個球的編號是多少。但皮卡丘有點鬧彆扭，他只想回答你當這個編號寫成二進位時，第b個位元的值是0還是1。假設數字是00110(2)的話，第0個位元是0，第一個位元是1，以此類推。如果你試圖問皮卡丘一個不存在的位元或是球或是問太多次的話，皮卡丘也會翻臉，請小心！ |
void Answer(int ans) |
當你知道答案時，就用這個告訴皮卡丘你的答案。這函數使用後，你的程式就會自動結束。然後雷精靈就會檢查這個球是不是真的不見了，如果你答對了他們就會高興地給你這一題的分數，如果答錯的話憤怒指數──或說上傳次數就會+1，有點可怕。 |
輸入說明
本題不需要輸入，解題方法參見題目敘述。
請注意任何的讀取都可能導任務失敗。
輸出說明
本題不需要輸出，解題方法參見題目敘述。請注意任何的輸出都可能導任務失敗。
範例輸入
無輸入
範例輸出
無輸出
配分方法
- 50% 球的數目$N\leq 1024$，可以問皮卡丘的次數$\leq NlogN$
- 100% $N\leq 2^{20}$，可以問皮卡丘的次數$\leq 2N$
Judge Setting
run-time limit: 1000 msmemory limit: 3276800 byte
測資數量: 0