QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100 Difficulty: [show] Interactive

#194. Passord

Statistics

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".

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
EditorialOpen Official EditorialQingyu- Download

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.