ytp ytp-senior ytp-2025

本題請不要使用標準輸入輸出流，不過你仍然可以輸出除錯訊息至標準錯誤流（stderr）。

你的程式需要在一開始使用前置處理器引入 lib0970.h，詳細請參考範例實作。

你需要完成以下的兩個函式，詳細執行流程請參考後面的內容：

std::string Alice(int n, int L, std::vector<int> a);

• 在一筆測試資料中，Alice 會被呼叫恰 $1$ 次。
• 引數 $n$ 代表神秘語言的字元數量。
• 引數 $L$ 代表 Alice 傳送給 Bob 訊息的最大長度
• 引數 $a$ 為一個長度為 $n$ 的正整數陣列。其中 $a[i]$（$0 \le i \le n-1$）表示出現次數第 $(i+1)$ 頻繁的字元的出現次數。$a$ 是非嚴格遞減的，也就是說 $a[i] \geq a[i + 1]$ 對於所有 $0 \le i \le n-2$。
• 回傳值需為一個由 0, 1 字元組成的字串，且字串長度不得超過 $L$。

std::vector<std::string> Bob(std::string s);

• 在一筆測試資料中，Bob 會被呼叫恰 $1$ 次。
• 引數 $s$ 是 Alice(n, L, a) 回傳的字串。
• 回傳值需為一個陣列包含 $n$ 個 $\texttt{01}$ 字串 ${h[0], h[1], \ldots, h[n-1]}$，其中 $h[i]$ 代表出現次數第 $(i+1)$ 頻繁的字元的編碼。

你回傳的 ${h[0], h[1], \ldots, h[n-1]}$ 需要同時滿足以下條件：

1. 對所有 $0 \le i \le n-1$，$h[i]$ 的長度皆不為 0，且只包含字元 $\texttt{0}$ 與／或 $\texttt{1}$。
2. 對任意 $0 \le i, j \le n-1$ 且 $i \ne j$，$h[i]$ 不是 $h[j]$ 的前綴。
3. 在所有同時滿足 (1.) 與 (2.) 的可能輸出中，使 $\sum_{i=0}^ {n-1} |h[i]| \cdot a[i]$ 的值最小。若有多組解，回傳其中任意一組皆可。

如果任意一個條件沒有被滿足，你的程式會被判斷為 Wrong Answer 並且獲得 0 分，否則，你的程式將依照 Scoring 中的敘述評分。

而評測系統會用以下執行的過程：

• 執行參賽者的程式，以測試資料的引數 $n, L, a$ 呼叫 $1$ 次 Alice()，並將回傳的字串 $s$ 儲存起來。
• 重新執行參賽者的程式，以之前 Alice() 回傳的字串 $s$ 為引數呼叫 $1$ 次 Bob()，如果回傳的結果符合上述所有條件，則會視為 Accepted。

一個被判斷為 Accepted 的範例互動狀況如下：

評測程式端	參賽者程式端
系統第一次執行參賽者的程式。
呼叫 Alice(5, 512, [11, 8, 7, 7, 3])。
	回傳 "111111111110111111110111111101111111011100"。
系統第二次執行參賽者的程式。
呼叫 Bob("111111111110111111110111111101111111011100")。
	回傳 $[\texttt{01}, \texttt{10}, \texttt{001}, \texttt{11}, \texttt{000}]$。

這時候評分程式會檢查：
$$\sum_{i=0}^ {n-1} |h[i]| \cdot a[i] = 2 \cdot 11 + 2 \cdot 8 + 3 \cdot 7 + 2 \cdot 7 + 3 \cdot 3 = 82$$，這是最小的可能之一。

另一個被判斷為 Accepted 的範例互動狀況如下：

評測程式端	參賽者程式端
系統第一次執行參賽者的程式。
呼叫 Alice(64, 512, [1, 1, ..., 1])。
	回傳 ""（空字串）。
系統第二次執行參賽者的程式。
呼叫 Bob("")。
	回傳 $[\texttt{000000}, \texttt{000001}, \ldots, \texttt{111111}]$。

這時候評分程式會檢查：
$$\sum_{i=0}^ {n-1} |h[i]| \cdot a[i] = 6 \cdot 64 = 384$$，這是最小的可能之一。

• $1 \le n \le 64$。
• $2^ {22} > a[0] \ge a[1] \ge \cdots \ge a[n-1] \ge 1$。
• $L = 512$。

對於子任務 1、2 與 3，你只需通過所有測資即可獲得所有分數。

對於子任務 4，令 $J = |s|$ 為你在 Alice 子程式所回傳字串的最大長度，你在本子任務的得分依下表計算：

$J$	$512$	$448$	$384$	$320$	$256$	$192$	$128$	$64$	$60$	$0$
分數	$1$	$2$	$3.5$	$5.5$	$8$	$11$	$15$	$20$	$22$	$22$

你的得分將由上表透過線性內插計算得到。舉例來說，當 $J = 267$ 時，你的得分為

$$
8 + \frac{5.5 - 8}{320 - 256} \cdot (267 - 256) \approx 7.57
$$

分。

範例評分程式以下列方式輸入：

• line $1$: $\;\; n \;\; L$
• line $2$: $\;\; a[0] \;\; a[1] \;\; \ldots a[n-1]$

範例評分程式的輸出格式如下：

• line $1$: $\;\;$ [Alice] s = "${s}"
• line $2+i$ ($0 \le i \le n-1$): $\;\;$ [Bob] h[i] = "${h[i]}"
• line $n+2$: $\;\;$ The length of s is ${|s|} and the cost is ${cost}.
  • 其中，$\text{cost} = \sum_{i=0}^ {n-1} |h[i]| \cdot a[i]$。

如果評分程式發現錯誤，則輸出格式如下：

• Judge Error [1]：輸入的 ${a[0], a[1], \ldots, a[n-1]}$ 沒有按照從大到小排序。
• Judge Error [2]：輸入的 $a[0] \ge 2^ {22}$。
• Judge Error [3]：輸入的 $a[n-1] \le 0$。
• Wrong Answer [4]：Alice 傳給 Bob 的字串長度超過 $L$。
• Wrong Answer [5]：Alice 傳給 Bob 的字串內容包含 $\texttt{0}$ 或 $\texttt{1}$ 以外的字元。
• Wrong Answer [6]：Bob 構造的 $H$ 長度不為 $n$。
• Wrong Answer [7]：Bob 構造的 $H$ 包含 $\texttt{0}$ 或 $\texttt{1}$ 以外的字元。
• Wrong Answer [8]：Bob 構造的 $H$ 存在 $i \ne j$ 滿足 $h[i]$ 是 $h[j]$ 的前綴。

請注意，範例評分程式不會檢查你的 $\text{cost}$ 是不是最小值。

編譯及測試教學請參考下列說明。

• 如果你的系統是 Linux 或 MacOS，你可以直接執行 compile.sh 編譯你的程式，編譯結果會是 mysterious，請直接用命令列執行該檔案。
• 如果你的系統是 Windows，你有以下的選擇：
  1. 本地測試時加入 #include "grader.cpp"，並且以單一檔案的編譯執行方式測試，請注意這一行上傳時需要刪除，否則你會獲得一個 Compile Error。
  2. 直接執行 compile.bat 編譯你的程式，編譯結果會是 mysterious，請注意你需要確保 g++ 在系統的環境變數 PATH 中。
  3. 如果你的電腦已經有 WSL (Windows Subsystem for Linux)，你可以直接使用 WSL 並按照 Linux 的做法。

YTP 2025 高中組程式挑戰營 p20