User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

42.9% (3/7)

Description

本題為互動題,僅限使用 C/C++ 作答

小嵐不久之前當上了某個神秘的小鎮的鎮長,鎮上的門牌號碼從 $0$ 開始編號,
並且總共有 $n$ 戶住戶,也就是說門牌號碼最大到 $n - 1$,
而小嵐當上鎮長之後第一件要做的事情就是了解居民大致的財政狀況。

在交接時,小嵐從前任鎮長得知了這個城鎮的秘密,這個城鎮存在兩個神祕數字 $x,y$,
且門牌號碼小於 $x$ 的住戶的年收入都大於 $y$ 元,而其餘的住戶的年收入都小於等於 $y$ 元。

但是由於在交接時小嵐並沒有很注意聽前任鎮長講話,
因此他忘記了 $x$ 的值,只記得 $x$ 會在 $[0, n]$ 這個區間內,
所以小嵐請你幫忙他找出神秘數字 $x$。

小嵐幫你請了一個幫手,你只要告訴這個幫手說你想要調查哪一戶的收入狀況,
他就會去現場幫你調查該戶的年收入為多少,並且回報給你實際的數字。

由於幫手只有這麼一個人,他的體力也不是無限的,加上這個小鎮的規模也不小,
因此你最多只能派他去調查 $40$ 次,超過這個次數的話幫手就會因為體力不支而無法前往現場,
也就代表你無法達成小嵐的要求。

Input Format

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

請記得 #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]$ 這個區間內,最後這個函式會自動幫你結束程式。

  • $1 \leq n \leq 2 \cdot 10^9$
  • $1 \leq y \leq 2 \cdot 10^9$

Output Format

本題沒有輸出,若你輸出了任何東西,你將會得到一個 WA

Sample Input 1

注意:本題沒有輸入,本輸入僅供範例標頭檔使用 (參見 Hints)

3 3 3

Sample Output 1

注意:本題沒有輸出,本輸出僅供範例標頭檔使用 (參見 Hints)

Correct x.
Totally make %d queries.

Sample Input 2

注意:本題沒有輸入,本輸入僅供範例標頭檔使用 (參見 Hints)

3 0 10

Sample Output 2

注意:本題沒有輸出,本輸出僅供範例標頭檔使用 (參見 Hints)

Correct x.
Totally make %d queries.

Hints

這裡提供一份範例標頭檔可以使用。

若在本機使用這份標頭檔執行時,輸入格式如下:

輸入只有一行,包含三個整數 $n, x, y$。

如果你的程式被評為 WA,範例評分程式會輸出 "Wrong Answer: MSG",其中 MSG 格式與意義如下:

  • Out of query range:代表在詢問時 $i$ 超出範圍
  • Out of answer range:代表回報的 $x$ 超出範圍
  • Helper dead:代表你的詢問次數過多
  • Not correct x:代表你回報的 $x$ 與原本的 $x$ 不相同

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~11 無特別限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1