本題為互動題,僅限使用 C/C++ 作答
小嵐不久之前當上了某個神秘的小鎮的鎮長,鎮上的門牌號碼從 $0$ 開始編號,
並且總共有 $n$ 戶住戶,也就是說門牌號碼最大到 $n - 1$,
而小嵐當上鎮長之後第一件要做的事情就是了解居民大致的財政狀況。
在交接時,小嵐從前任鎮長得知了這個城鎮的秘密,這個城鎮存在兩個神祕數字 $x,y$,
且門牌號碼小於 $x$ 的住戶的年收入都大於 $y$ 元,而其餘的住戶的年收入都小於等於 $y$ 元。
但是由於在交接時小嵐並沒有很注意聽前任鎮長講話,
因此他忘記了 $x$ 的值,只記得 $x$ 會在 $[0, n]$ 這個區間內,
所以小嵐請你幫忙他找出神秘數字 $x$。
小嵐幫你請了一個幫手,你只要告訴這個幫手說你想要調查哪一戶的收入狀況,
他就會去現場幫你調查該戶的年收入為多少,並且回報給你實際的數字。
由於幫手只有這麼一個人,他的體力也不是無限的,加上這個小鎮的規模也不小,
因此你最多只能派他去調查 $40$ 次,超過這個次數的話幫手就會因為體力不支而無法前往現場,
也就代表你無法達成小嵐的要求。
本題沒有輸入,若你輸入了任何東西,可能會導致各種不可預期的結果。
請記得 #include "lib0133.h"
,以下幾個是你可以使用的函式:
void Init(int *pn, int *py)
:此函式會將 $n, y$ 分別存到 pn
, py
指向的位址,代表這個小鎮的住戶數量以及神祕數字 $y$。
int Query(int i)
:此函式會回傳門牌號碼為 $i$ 的住戶的年收入,且 $i$ 必須在 $[0, n)$ 這個區間內。你最多只能呼叫此函式 $40$ 次。
void Ans(int x)
:回傳你認為的 $x$ 的值,而 $x$ 必須在 $[0, n]$ 這個區間內,最後這個函式會自動幫你結束程式。
本題沒有輸出,若你輸出了任何東西,你將會得到一個 WA。
這裡提供一份範例標頭檔可以使用。
若在本機使用這份標頭檔執行時,輸入格式如下:
輸入只有一行,包含三個整數 $n, x, y$。
如果你的程式被評為 WA,範例評分程式會輸出 "Wrong Answer: MSG",其中 MSG 格式與意義如下:
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~11 | 無特別限制 | 100 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 |