Unohdin taas salasanani! Istun tietokoneeni ääressä näppäilemässä vääriä salasanoja. Muistan vain sen, että salasanani sisältää ainoastaan pieniä kirjaimia. Onneksi kirjautumisjärjestelmä vastaa muullakin kuin pelkällä ”väärä salasana” -ilmoituksella. Se kertoo myös pisimmän sellaisen syötteeni alkuosan pituuden, joka esiintyy (ei välttämättä yhtenäisenä) osajonona salasanassa. Täsmällisesti ilmaistuna salasanalle $P = p_1 p_2 \dots p_N$ ja syötteelle $Q = q_1 q_2 \dots q_N$ kirjautumisjärjestelmän vastaus on suurin $L$, jolle on olemassa indeksit $1 \le k_1 < k_2 < \dots < k_L \le N$ siten, että $q_i = p_{k_i}$ kaikilla $1 \le i \le L$. Järjestelmä kertoo minulle myös luvun $N$, joka on salasanani pituus, sekä luvun $S$, mikä tarkoittaa, että salasanani käyttää vain aakkoston $S$ ensimmäistä kirjainta. Esimerkiksi $S = 4$ tarkoittaa, että salasanani sisältää vain kirjaimia $\text{a}$, $\text{b}$, $\text{c}$ ja $\text{d}$ (mutta ei välttämättä niitä kaikkia).
Auta minua palauttamaan salasanani!
Toteutuksen yksityiskohdat
Tämä tehtävä on vuorovaikutteinen. Sinun tulee toteuttaa funktio
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- Argumentit: $N$ ja $S$ kuten edellä on kuvattu.
- Paluuarvo: oikea salasana.
Ohjelmasi voi kutsua funktiota
C: int query(char* str);
C++: int query(string str);
- Argumentti: $1$–$N$ kirjaimen pituinen merkkijono, jonka merkit kuuluvat aakkoston $S$ ensimmäisen kirjaimen joukkoon.
- Paluuarvo: kokonaisluku väliltä $0$ ja merkkijonon
strpituus, joka kuvaa kirjautumisjärjestelmän vastausta kyselyysi. - Käännösvirheiden välttämiseksi sinun tulee esitellä tämä funktio täsmälleen yllä olevaa tekstiä käyttäen missä tahansa globaalissa näkyvyysalueessa ennen sen kutsumista.
- Voit kutsua tätä funktiota enintään $50\,000$ kertaa kutakin testitapausta kohden.
Ohjelmasi voi määritellä apufunktioita.
Esimerkkitarkistin
Paikallista testausta varten tarjotaan esimerkkitiedosto grader.{c,cpp}. Esimerkkitarkistin lukee syötteen tiedostosta password.in seuraavassa muodossa:
- rivi $1$: $N$ $S$
- rivi $2$: salasana
Voit kääntää tarkistimen yhdessä ratkaisusi kanssa. Tämän jälkeen voit suorittaa syntyneen binääritiedoston testataksesi arvausstrategiaasi annetulla syötteellä.
Osatehtävät
Testitapaukset voidaan pisteyttää ryhminä. Osatehtävät ovat järjestyksessä seuraavat:
| Osatehtävä | Pisteosuus | Syötteen rajoitukset |
|---|---|---|
| 1 | 10% | $N \le S \le 26$; kaikki salasanan kirjaimet ovat keskenään eri kirjaimia |
| 2 | 20% | $2 \le N \le 100$ ja $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ ja $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
Esimerkit
Olkoon salasana $\text{aab}$. Tarkistin kutsuu guess(3, 2). Kutsuloki voi olla seuraava:
| Kutsu | Paluuarvo |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
Tässä vaiheessa kutsun guess(3, 2) tulee palauttaa "aab".