QOJ.ac

QOJ

时间限制: 3 s 内存限制: 512 MB 总分: 100 难度: [显示] 交互

#194. Lösenord

统计

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

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.