TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

63.0% (17/27)

Submission's AC Ratio

18.5% (37/200)

Tags

Description

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

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

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

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

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

也就是說對於每一次猜數字,當答案為 $K$ 的時候,你希望 $\sum{X_i}$ 不超過 $\text{Limit}$

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

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

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

#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 = 10^ {12}, \text{Limit} = 4N\lfloor\log_{2}{N}\rfloor$ 10
2 1 $N = 10^ 5, \text{Limit} = \max(8000, 400 + 4K^ {3/2} )$ 25
3 2 $N = 10^ {14}, \text{limit} = 4K (\lfloor\log_{2}{K}\rfloor + 1)^ 2$ 30
4 3 $N = 10^ {14}, \text{Limit} = 4K (\lfloor\log_{2}{K}\rfloor + 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