Jag har glömt mitt lösenord igen! Jag sitter vid min dator och knappar in felaktiga lösenord. Allt jag minns är att mitt lösenord bara innehåller små bokstäver. Lyckligtvis svarar inloggningssystemet med mer än bara ”fel lösenord”. Det talar också om längden på det längsta prefixet av min inmatning som förekommer som en (inte nödvändigtvis sammanhängande) delsekvens i lösenordet. Formellt, för ett lösenord $P = p_1 p_2 \dots p_N$ och en inmatning $Q = q_1 q_2 \dots q_N$, är inloggningssystemets svar det största $L$ för vilket det finns index $1 \le k_1 < k_2 < \dots < k_L \le N$ sådana att $q_i = p_{k_i}$ för alla $1 \le i \le L$. Systemet ger mig också $N$, längden på mitt lösenord, och $S$, vilket betyder att mitt lösenord endast använder de $S$ första bokstäverna i alfabetet. Till exempel betyder $S = 4$ att mitt lösenord endast innehåller $\text{a}$, $\text{b}$, $\text{c}$ och $\text{d}$ (men inte nödvändigtvis alla av dem).
Snälla hjälp mig att återställa mitt lösenord!
Implementeringsdetaljer
Detta problem är interaktivt. Du ska implementera funktionen
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- Argument: $N$ och $S$ enligt beskrivningen ovan.
- Returvärde: det korrekta lösenordet.
Ditt program får anropa funktionen
C: int query(char* str);
C++: int query(string str);
- Argument: en sträng med $1$ till $N$ bokstäver bland de $S$ första bokstäverna i alfabetet.
- Returvärde: ett heltal mellan $0$ och längden på
str, som representerar inloggningssystemets svar på din fråga. - För att undvika kompileringsfel bör du deklarera denna funktion med exakt texten ovan, var som helst i det globala scopet innan du anropar den.
- Du får anropa denna funktion högst $50\,000$ gånger för varje testfall.
Ditt program får definiera ytterligare funktioner.
Exempelbedömare
En exempelbedömare grader.{c,cpp} tillhandahålls så att du kan testa din kod lokalt. Exempelbedömaren läser inmatningen från filen password.in i formatet:
- rad $1$: $N$ $S$
- rad $2$: lösenord
Du kan kompilera bedömaren tillsammans med din lösning. Därefter kan du köra den resulterande binärfilen för att testa din gissningsstrategi mot den givna inmatningen.
Deluppgifter
Testfall kan poängsättas i grupp. I ordning är deluppgifterna:
| Deluppgift | Andel av poängen | Inmatningsbegränsningar |
|---|---|---|
| 1 | 10% | $N \le S \le 26$; alla bokstäver i lösenordet är olika |
| 2 | 20% | $2 \le N \le 100$ och $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ och $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
Exempel
Låt lösenordet vara $\text{aab}$. Bedömaren anropar guess(3, 2). Anropsloggen kan se ut så här:
| Anrop | Returvärde |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
Vid denna tidpunkt ska guess(3, 2) returnera "aab".