聽說 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
本題沒有輸入,如果你輸入了任何東西,可能會導致各種不可預期的結果。
本題沒有輸出,如果你輸出了任何東西,可能會導致各種不可預期的結果。
提供一份 本機測試用的標頭檔
不管你找出來的 $K$ 和答案不一樣,或是付出的 Cost 過多,都會拿到一個 WA
by kevin_zhang
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 |