User's AC Ratio

92.0% (46/50)

Submission's AC Ratio

33.8% (79/234)

Description

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

請在你的程式碼最前面加上 #include "lib0020.h"

丟雞蛋問題是一個經典的題目，你現在正身處於一棟 $M$ 層樓高的大樓，手上有 $60$ 顆一模一樣的雞蛋，
已知這些雞蛋只要在超過 $h\ (h\leq M)$ 樓的地方將其摔出就會破裂；不超過則不會。
但由於我們目前還不知道 $h$ 是多少，請你在摔完這些雞蛋之前，回答出 $h$ 的值。

你需要完成以下函式：
long long height_limit(long long M);

$M$ 代表 $h$ 的範圍介於 $[1,M]$ ，其中 $h$ 為整數。
該函式需要在被呼叫後，回傳 $h$ 的正確數值。

你的程式可以呼叫以下函式：
int is_broken(long long k);

代表你要將一顆雞蛋從高度 $k$ 的樓層摔下去， is_broken(k) 會回傳 $1$ 或 $0$ ，如果回傳 $1$ 代表雞蛋破了； $0$ 則代表雞蛋沒破。 $k$ 必須是一個介於 $[1,M]$ 的整數。
該函式只能被呼叫 $60$ 次，即使雞蛋沒破，你也無法將其回收。

如果不滿足上述條件或是回傳值不符合題目要求，你的程式會被判為 WA；否則你的程式會被判為 AC 。

Input Format

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

Output Format

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

Sample Input 1

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

80 25

Sample Output 1

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

Accept: query %d times (其中 %d 的值因你的查詢次數而變動)

Hints

這邊提供一份範例標頭檔以及一份可以 AC 子任務一的程式碼。

#include "lib0020.h"

long long height_limit(long long M){
  if(is_broken(2)) return 1;
    return 2;
}

若在本機使用這份標頭檔與這份程式碼執行時，輸入格式如下：

第 $1$ 列： $M\ h$

其中 $M,h\ (1\leq h\leq M\leq10^ {18})$ 如題目所述。

考慮以下測試資料： $M=10,h=4$ 。
評分程式呼叫 height_limit(10) ，一個被評分程式判斷為 AC 的互動例子顯示如下：

Call	Return
is_broken(1)	0
is_broken(2)	0
is_broken(3)	0
is_broken(4)	0
is_broken(5)	1
	4

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

invalid broken query: 不合法的 is_broken() 呼叫。
too many queries: 呼叫上述函式的總次數超過 $60$ 次。
incorrect height: height_limit(M) 回傳的值與題目的 $h$ 不相符。

Problem Source

Subtasks

No.	Testdata Range	Constraints	Score
1	0~1	$M=2$	12
2	0~7	$M\leq60$	20
3	0~16	無特別限制	68

Testdata and Limits

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

Submit

Status

Ranklist

20 . 丟雞蛋問題