我又忘記密碼了!我正坐在電腦前不斷敲入錯誤的密碼。我只記得我的密碼僅包含小寫字母。幸運的是,登入系統給出的回饋不僅僅是「密碼錯誤」。它還會告訴我,我的輸入中作為密碼的(不一定連續的)子序列出現的最長前綴的長度。形式化地說,對於密碼 $P = p_1 p_2 \dots p_N$ 與輸入 $Q = q_1 q_2 \dots q_N$,登入系統的回答是最大的 $L$,使得存在下標 $1 \le k_1 < k_2 < \dots < k_L \le N$,滿足對於所有 $1 \le i \le L$ 都有 $q_i = p_{k_i}$。系統還會告訴我密碼的長度 $N$,以及 $S$,表示我的密碼僅使用字母表中的前 $S$ 個字母。例如,$S = 4$ 表示我的密碼僅包含 $\text{a}$、$\text{b}$、$\text{c}$ 和 $\text{d}$(但不一定全部包含)。
請幫我找回我的密碼!
實作細節
本題為互動題。你需要實作以下函式:
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- 參數:如上所述的 $N$ 與 $S$。
- 回傳值:正確的密碼。
你的程式可以呼叫以下函式:
C: int query(char* str);
C++: int query(string str);
- 參數:一個由字母表前 $S$ 個字母組成的、長度為 $1$ 到 $N$ 的字串。
- 回傳值:一個介於 $0$ 到
str長度之間的整數,表示登入系統對你的詢問所給出的回答。 - 為了避免編譯錯誤,在呼叫此函式之前,你應當在全域作用域的任意位置使用與上述完全相同的文字宣告此函式。
- 對於每筆測試資料,你至多可以呼叫此函式 $50\,000$ 次。
你的程式可以定義其他函式。
範例評測程式
我們提供了一個範例 grader.{c,cpp} 供你在本機測試程式碼。範例評測程式會按以下格式從檔案 password.in 讀取輸入:
- 第 $1$ 行:$N$ $S$
- 第 $2$ 行:密碼
你可以將評測程式與你的解答一起編譯,然後執行產生的執行檔,以針對給定的輸入測試你的猜測策略。
子任務
測試資料可能按組計分。各子任務依序如下:
| 子任務 | 分數佔比 | 輸入限制 |
|---|---|---|
| 1 | 10% | $N \le S \le 26$;密碼中的所有字母皆相異 |
| 2 | 20% | $2 \le N \le 100$ 且 $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ 且 $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
範例
設密碼為 $\text{aab}$。評測程式呼叫 guess(3, 2)。呼叫紀錄可能如下:
| 呼叫 | 回傳值 |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
此時,guess(3, 2) 應當回傳 "aab"。