QOJ.ac

QOJ

Süre Sınırı: 3 s Bellek Sınırı: 512 MB Toplam puan: 100 Zorluk: [göster] Etkileşimli

#194. Passwort

İstatistikler

Ich habe schon wieder mein Passwort vergessen! Ich sitze an meinem Computer und tippe falsche Passwörter ein. Alles, woran ich mich erinnere, ist, dass mein Passwort nur Kleinbuchstaben enthält. Glücklicherweise antwortet das Anmeldesystem mit mehr als nur „falsches Passwort“. Es verrät mir außerdem die Länge des längsten Präfixes meiner Eingabe, das als (nicht notwendigerweise zusammenhängende) Teilfolge im Passwort vorkommt. Formal ist für ein Passwort $P = p_1 p_2 \dots p_N$ und eine Eingabe $Q = q_1 q_2 \dots q_N$ die Antwort des Anmeldesystems das größte $L$, für das Indizes $1 \le k_1 < k_2 < \dots < k_L \le N$ existieren, sodass $q_i = p_{k_i}$ für alle $1 \le i \le L$ gilt. Das System verrät mir außerdem $N$, die Länge meines Passworts, und $S$, was bedeutet, dass mein Passwort nur die ersten $S$ Buchstaben des Alphabets verwendet. Beispielsweise bedeutet $S = 4$, dass mein Passwort nur $\text{a}$, $\text{b}$, $\text{c}$ und $\text{d}$ enthält (aber nicht notwendigerweise alle davon).

Bitte hilf mir, mein Passwort wiederherzustellen!

Implementierungsdetails

Diese Aufgabe ist interaktiv. Du sollst die folgende Funktion implementieren:

C:    char* guess(int n, int s);
C++:  string guess(int n, int s);
  • Argumente: $N$ und $S$ wie oben beschrieben.
  • Rückgabewert: das korrekte Passwort.

Dein Programm darf die folgende Funktion aufrufen:

C:    int query(char* str);
C++:  int query(string str);
  • Argument: eine Zeichenkette aus $1$ bis $N$ Buchstaben aus den ersten $S$ Buchstaben des Alphabets.
  • Rückgabewert: eine ganze Zahl zwischen $0$ und der Länge von str, welche die Antwort des Anmeldesystems auf deine Anfrage darstellt.
  • Um Kompilierfehler zu vermeiden, solltest du diese Funktion mit genau dem obigen Text irgendwo im globalen Gültigkeitsbereich deklarieren, bevor du sie aufrufst.
  • Du darfst diese Funktion für jeden Testfall höchstens $50\,000$-mal aufrufen.

Dein Programm darf zusätzliche Funktionen definieren.

Beispiel-Grader

Ein Beispiel-grader.{c,cpp} wird bereitgestellt, damit du deinen Code lokal testen kannst. Der Beispiel-Grader liest die Eingabe aus der Datei password.in im folgenden Format:

  • Zeile $1$: $N$ $S$
  • Zeile $2$: Passwort

Du kannst den Grader zusammen mit deiner Lösung kompilieren. Anschließend kannst du die erzeugte ausführbare Datei starten, um deine Ratestrategie mit der gegebenen Eingabe zu testen.

Teilaufgaben

Testfälle können gruppenweise bewertet werden. Der Reihe nach lauten die Teilaufgaben:

Teilaufgabe Punkteanteil Eingabebeschränkungen
1 10% $N \le S \le 26$; alle Buchstaben im Passwort sind paarweise verschieden
2 20% $2 \le N \le 100$ und $2 \le S \le 4$
3 20% $2 \le N \le 2\,000$ und $2 \le S \le 20$
4 30% $2 \le N \le 3\,500$
5 20% $2 \le N \le 5\,000$

Beispiele

Sei das Passwort $\text{aab}$. Der Grader ruft guess(3, 2) auf. Das Aufrufprotokoll könnte wie folgt aussehen:

Aufruf Rückgabewert
guess("ab") 2
guess("abb") 2
guess("bab") 1
guess("aab") 3

An diesem Punkt sollte guess(3, 2) den Wert "aab" zurückgeben.

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.