Takina 和 Chisato 正在參加一個水果大會。在與他們最喜愛的水果扮演者合影一天後，他們來到了一個遊戲攤位。
遊戲規則如下： 共有 $n$ 個水果，每個水果都有一個從 $1$ 到 $n$ 的不同標籤。 其中恰好有一個水果是檸檬，但 Takina 和 Chisato 目前都不知道是哪一個。 * Takina 將會逐一收到這 $n$ 個水果。她的目標是將檸檬的標籤傳達給 Chisato（在此過程中 Chisato 被蒙住雙眼）。
在收到任何水果之前，Takina 會得到一個陣列 $p$，代表水果標籤出現的順序。$p[1]$ 將是第一個出現的水果標籤，$p[2]$ 將是第二個，依此類推。接著，Takina 將寫下一個僅包含 $0$ 和 $1$ 的二進位字串 $b$。該字串長度不得超過 $5000$ 個字元，但可以是空字串。令 $x$ 為 $b$ 的長度。
隨後，水果會按照上述順序逐一交給 Takina。在收到每個水果時，Takina 會被告知它是否為檸檬。 如果該水果不是檸檬，Takina 可以選擇是否吃掉它。此決定必須在收到下一個水果之前做出，且一旦做出便無法更改。 如果該水果是檸檬，Takina 不得吃掉它。
令 $y$ 為 Takina 吃掉的水果總數。
最後，Chisato 會收到字串 $b$ 以及未被吃掉的水果標籤的排序列表。利用這些資訊，Chisato 必須判斷出哪個水果是檸檬。
Takina 和 Chisato 決定進行 $t$ 次此遊戲。請為他們設計一個策略，在正確識別檸檬的同時，最小化 $x$ 和 $y$。
實作細節
這是一個通訊任務。請勿從標準輸入讀取或向標準輸出寫入。
你需要實作三個程序。
對於 Takina，你應該實作：
std::string init(int subtask, int n, std::vector<int> p)subtask：測試案例所屬的子任務索引。n：水果的數量。p：一個長度為 $n + 1$ 的陣列，其中：- $p[0] = 0$，且
- 對於每個 $1 \le i \le n$，$p[i]$ 是將交給 Takina 的第 $i$ 個水果的標籤。
- 此程序在每個測試案例中會被呼叫 $t$ 次，即每場遊戲開始時呼叫一次。
此程序應回傳字串 $b$，長度介於 $0$ 到 $5000$（含）之間，且僅包含 $0$ 和 $1$。如果回傳了長度或格式無效的字串，你將收到 Wrong Answer 判決。
bool receive_fruit(int id, bool is_lemon)id：交給 Takina 的水果標籤。is_lemon：如果給定的水果是檸檬則為true，否則為false。- 此程序在每場遊戲中會被呼叫 $n$ 次，即每個水果呼叫一次。
此程序應在應該吃掉該水果時回傳 true，否則回傳 false。如果在 is_lemon 為 true 時回傳 true，你將收到 Wrong Answer 判決。
對於 Chisato，你應該實作：
int answer(int subtask, int n, std::string b, std::vector<int> uneaten)subtask：測試案例所屬的子任務索引。n：水果的數量。b：由init回傳的字串。uneaten：一個長度為 $n - y + 1$ 的排序向量，包含 Takina 未吃掉的水果標籤，其中：uneaten[0] = 0，且uneaten[i]是未吃掉水果中第 $i$ 小的標籤。
- 此程序在每個測試案例中會被呼叫 $t$ 次，即每場遊戲結束時呼叫一次。
此程序應回傳一個整數，即檸檬的標籤。如果回傳值與正確標籤不符，你將收到 Wrong Answer 判決。
在實際評測中，呼叫上述程序的程式會執行兩次：
- 在第一次執行中，以下步驟會執行 $t$ 次：
init被呼叫一次。receive_fruit被呼叫 $n$ 次，遵循給 Takina 的水果順序。- 你的程式可以在連續的呼叫中儲存並保留資訊。
- 在第二次執行中，遊戲的順序可能與第一次執行不同。對於 $t$ 場遊戲中的每一場：
answer被呼叫一次。除了傳遞給answer的參數外，你的程式不得存取來自第一次執行的資訊。
由於程序可能會被多次呼叫，你應該注意先前呼叫的剩餘資料對當前呼叫的影響。
資料範圍
對於所有測試案例，輸入將滿足以下限制： $1 \le t \le 10\,000$ $n = 500$ 對於所有 $1 \le i \le n$，$1 \le p[i] \le n$ 恰好有一個檸檬。
對於每個子任務，你的程式將根據 Takina 寫下的字串長度 $x$ 以及她吃掉的水果數量 $y$ 進行不同的評分。每個測試案例的分數是根據所有 $t$ 場遊戲中 $x$ 的最大值以及 $y$ 的最大值計算得出。
| 子任務 | 分數 |
|---|---|
| 1 | 若 $y > 2$，分數為 0。否則，分數為 $10 \times \min \left( \frac{288}{x}, 1 \right)$。 |
| 2 | 若 $y > 9$，分數為 0。否則，分數為 $30 \times \min \left( \frac{30}{x}, 1 \right)$。 |
| 3 | 分數為 $60 \times \min \left( \frac{20}{x+y}, 1 \right)$。 |
範例
輸入格式 1
(範例輸入資料)
輸出格式 1
(範例輸出資料)
說明
考慮單場遊戲 ($t = 1$) 且 $n = 4$ 的情況。假設 Takina 得到的順序為 $p = [0, 3, 1, 4, 2]$，且標籤為 $4$ 的水果是檸檬。一種可能的呼叫序列如下：
| 步驟 | 程序呼叫 | 參數 | 回傳值 |
|---|---|---|---|
| 1 | init |
(subtask, 4, [0, 3, 1, 4, 2]) |
"101" |
| 2 | receive_fruit |
(3, false) |
true |
| 3 | receive_fruit |
(1, false) |
false |
| 4 | receive_fruit |
(4, true) |
false |
| 5 | receive_fruit |
(2, false) |
true |
| 6 | answer |
(subtask, 4, "101", [0, 1, 4]) |
4 |
在此範例中，Takina 吃掉了標籤為 $3$ 和 $2$ 的水果，因此未吃掉的水果為 $\{1, 4\}$。傳遞給 answer 的向量 uneaten 因此為 [0, 1, 4]。此策略成功在 $x = 3$ 和 $y = 2$ 的情況下正確識別出檸檬。
測試
你可以從附件中下載範例評測程式 (grader.cpp)、標頭檔 (lemon.h) 和解決方案模板 (lemon.cpp)。提供了兩個輸入檔案供你測試：sample1.txt 和 sample2.txt。你可以使用 compile.sh 腳本進行編譯，並使用 run.sh 執行你的解決方案進行測試。
此問題不支援 CMS 使用者測試。
範例評測程式
提供了一個範例評測程式以協助你在本地測試你的實作。與正式評測程式不同，範例評測程式僅執行你的程式一次，且不會改變 Takina 和 Chisato 的測試順序。
輸入格式
輸入的第一行包含一個整數 subtask。
第二行包含一個整數 $t$。
接下來的 $t$ 行輸入每行描述一場遊戲。每場遊戲描述如下：
一行包含兩個以空格分隔的整數 $n$ 和 $l$，分別代表水果數量和檸檬的標籤。
一行包含 $n$ 個以空格分隔的整數 $p[1], p[2], \dots, p[n]$。
輸出格式
範例評測程式輸出一個實數，代表根據所有遊戲中 $x$ 和 $y$ 的值計算出的分數比例。
說明
額外的診斷訊息可能會列印到標準錯誤。範例評測程式不會模擬正式評測程式的行為。