TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

60.7% (17/28)

Submission's AC Ratio

17.9% (37/207)

Tags

Description

聽說 casper 又要請大家吃拉麵了,
不過當然沒有這麼簡單,你必須要先猜中他心裡的數字才行。

假設答案是 K 你知道 K 一定介於 [1,N] 之間。
同時 你每次可以問一個問題 : 請問 X>K 嘛?

這時候,casper 會告訴你,X 是否 >K

可是,沒有這麼簡單,每次詢問的時候,你都必須付出 X 元給它才行。

雖然猜中答案就有拉麵,可是付太多錢也很虧,所以你的目標,就是希望不要多付太多錢

也就是說對於每一次猜數字,當答案為 K 的時候,你希望 Xi 不超過 Limit

本題為互動題,請引入"lib2184.h"

可以使用的函式:
bool Compare(int64_t X) : 這時候 casper 會回答你 X>K 嘛? 其中 1XN
請你實做下列函式:
int64_t find_k(int64_t N) : 答案會介於 [1,N] 之間,請回傳一個你覺得是答案的值

注意 int64_t find_k(int64_t N) 可能會被呼叫至多 105 次。
一個符合格式的範例程式碼

#include "lib2184.h"

int64_t find_k(int64_t N) {
    if (Compare(2)) 
        return 1;
    return 2;
}

請千萬不要實做 int main() 函式 , 會 CE

Input Format

本題沒有輸入,如果你輸入了任何東西,可能會導致各種不可預期的結果。

Output Format

本題沒有輸出,如果你輸出了任何東西,可能會導致各種不可預期的結果。

Hints

提供一份 本機測試用的標頭檔
不管你找出來的 K 和答案不一樣,或是付出的 Cost 過多,都會拿到一個 WA

Problem Source

by kevin_zhang

Subtasks

No. Testdata Range Constraints Score
1 0 N=1012,Limit=4Nlog2N 10
2 1 N=105,Limit=max(8000,400+4K3/2) 25
3 2 N=1014,limit=4K(log2K+1)2 30
4 3 N=1014,Limit=4K(log2K+1) 35

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 2
2 1000 65536 65536 3
3 1000 65536 65536 4