QOJ.ac

QOJ

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

#194. Salasana

통계

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 str pituus, 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".

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.