User's AC Ratio

91.7% (44/48)

Submission's AC Ratio

33.6% (77/229)

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