QOJ.ac

QOJ

시간 제한: 3 s 메모리 제한: 512 MB 총점: 100 난이도: [표시] 인터랙티브

#194. Hasło

통계

Znowu zapomniałem swojego hasła! Siedzę przed komputerem i wpisuję błędne hasła. Pamiętam tylko tyle, że moje hasło składa się wyłącznie z małych liter. Na szczęście system logowania odpowiada czymś więcej niż tylko „błędne hasło”. Podaje mi również długość najdłuższego prefiksu mojego wejścia, który występuje jako (niekoniecznie spójny) podciąg w haśle. Formalnie, dla hasła $P = p_1 p_2 \dots p_N$ oraz wejścia $Q = q_1 q_2 \dots q_N$, odpowiedzią systemu logowania jest największe $L$, dla którego istnieją indeksy $1 \le k_1 < k_2 < \dots < k_L \le N$ takie, że $q_i = p_{k_i}$ dla wszystkich $1 \le i \le L$. System podaje mi także $N$, czyli długość mojego hasła, oraz $S$, co oznacza, że moje hasło używa wyłącznie pierwszych $S$ liter alfabetu. Na przykład $S = 4$ oznacza, że moje hasło zawiera wyłącznie litery $\text{a}$, $\text{b}$, $\text{c}$ oraz $\text{d}$ (ale niekoniecznie wszystkie z nich).

Proszę, pomóż mi odzyskać moje hasło!

Szczegóły implementacji

To zadanie jest interaktywne. Powinieneś zaimplementować funkcję

C:    char* guess(int n, int s);
C++:  string guess(int n, int s);
  • Argumenty: $N$ oraz $S$ zgodnie z powyższym opisem.
  • Wartość zwracana: poprawne hasło.

Twój program może wywoływać funkcję

C:    int query(char* str);
C++:  int query(string str);
  • Argument: napis złożony z od $1$ do $N$ liter spośród pierwszych $S$ liter alfabetu.
  • Wartość zwracana: liczba całkowita z przedziału od $0$ do długości str, oznaczająca odpowiedź systemu logowania na Twoje zapytanie.
  • Aby uniknąć błędów kompilacji, powinieneś zadeklarować tę funkcję przy użyciu dokładnie powyższego tekstu w dowolnym miejscu w zasięgu globalnym przed jej wywołaniem.
  • Możesz wywołać tę funkcję co najwyżej $50\,000$ razy dla każdego przypadku testowego.

Twój program może definiować dodatkowe funkcje.

Przykładowy grader

Przykładowy plik grader.{c,cpp} został udostępniony, abyś mógł przetestować swój kod lokalnie. Przykładowy grader wczytuje dane wejściowe z pliku password.in w formacie:

  • wiersz $1$: $N$ $S$
  • wiersz $2$: hasło

Możesz skompilować grader razem ze swoim rozwiązaniem. Następnie możesz uruchomić otrzymany plik wykonywalny, aby przetestować swoją strategię zgadywania na podanych danych wejściowych.

Podzadania

Przypadki testowe mogą być oceniane grupowo. Kolejne podzadania to:

Podzadanie Procent punktów Ograniczenia wejścia
1 10% $N \le S \le 26$; wszystkie litery w haśle są parami różne
2 20% $2 \le N \le 100$ oraz $2 \le S \le 4$
3 20% $2 \le N \le 2\,000$ oraz $2 \le S \le 20$
4 30% $2 \le N \le 3\,500$
5 20% $2 \le N \le 5\,000$

Przykład

Niech hasłem będzie $\text{aab}$. Grader wywołuje guess(3, 2). Dziennik wywołań może wyglądać następująco:

Wywołanie Wartość zwracana
guess("ab") 2
guess("abb") 2
guess("bab") 1
guess("aab") 3

W tym momencie guess(3, 2) powinno zwrócić "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.