Jeg har glemt passordet mitt igjen! Jeg sitter ved datamaskinen min og taster inn feil passord. Alt jeg husker er at passordet mitt bare inneholder små bokstaver. Heldigvis svarer innloggingssystemet med mer enn bare «feil passord». Det forteller meg også lengden på det lengste prefikset av inndataen min som forekommer som en (ikke nødvendigvis sammenhengende) delsekvens i passordet. Formelt, for et passord $P = p_1 p_2 \dots p_N$ og inndata $Q = q_1 q_2 \dots q_N$, er innloggingssystemets svar den største $L$ som det finnes indekser $1 \le k_1 < k_2 < \dots < k_L \le N$ for slik at $q_i = p_{k_i}$ for alle $1 \le i \le L$. Systemet forteller meg også $N$, lengden på passordet mitt, og $S$, som betyr at passordet mitt bare bruker de første $S$ bokstavene i alfabetet. For eksempel betyr $S = 4$ at passordet mitt bare inneholder $\text{a}$, $\text{b}$, $\text{c}$ og $\text{d}$ (men ikke nødvendigvis alle sammen).
Vær så snill å hjelpe meg med å gjenopprette passordet mitt!
Implementasjonsdetaljer
Denne oppgaven er interaktiv. Du skal implementere funksjonen
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- Argumenter: $N$ og $S$ som beskrevet ovenfor.
- Returverdi: det riktige passordet.
Programmet ditt kan kalle funksjonen
C: int query(char* str);
C++: int query(string str);
- Argument: en streng med $1$ til $N$ bokstaver blant de første $S$ bokstavene i alfabetet.
- Returverdi: et heltall mellom $0$ og lengden på
str, som representerer innloggingssystemets svar på spørringen din. - For å unngå kompileringsfeil bør du deklarere denne funksjonen med nøyaktig teksten ovenfor, hvor som helst i det globale scopet før du kaller den.
- Du kan kalle denne funksjonen høyst $50\,000$ ganger for hvert testtilfelle.
Programmet ditt kan definere ekstra funksjoner.
Eksempelretter
En eksempelretter grader.{c,cpp} er oppgitt slik at du kan teste koden din lokalt. Eksempelretteren leser inndata fra filen password.in på følgende format:
- linje $1$: $N$ $S$
- linje $2$: passord
Du kan kompilere retteren sammen med løsningen din. Deretter kan du kjøre den resulterende binærfilen for å teste gjettestrategien din mot de gitte inndataene.
Deloppgaver
Testtilfeller kan bli vurdert gruppevis. I rekkefølge er deloppgavene:
| Deloppgave | Prosentandel av poeng | Begrensninger på inndata |
|---|---|---|
| 1 | 10% | $N \le S \le 26$; alle bokstavene i passordet er forskjellige |
| 2 | 20% | $2 \le N \le 100$ og $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ og $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
Eksempler
La passordet være $\text{aab}$. Retteren kaller guess(3, 2). Kalloggen kan være
| Kall | Returverdi |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
På dette tidspunktet skal guess(3, 2) returnere "aab".