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