QOJ.ac

QOJ

実行時間制限: 3 s メモリ制限: 512 MB 満点: 100 難易度: [表示] インタラクティブ

#194. Kata Sandi

統計

Saya lupa kata sandi saya lagi! Saya sedang duduk di depan komputer sambil mengetikkan kata sandi yang salah. Yang saya ingat hanyalah bahwa kata sandi saya hanya berisi huruf kecil. Untungnya, sistem masuk (login) merespons lebih dari sekadar "kata sandi salah". Sistem tersebut juga memberi tahu saya panjang prefiks terpanjang dari masukan saya yang muncul sebagai upabarisan (tidak harus berurutan secara berdampingan) di dalam kata sandi. Secara formal, untuk kata sandi $P = p_1 p_2 \dots p_N$ dan masukan $Q = q_1 q_2 \dots q_N$, jawaban sistem masuk adalah nilai $L$ terbesar sehingga terdapat indeks $1 \le k_1 < k_2 < \dots < k_L \le N$ yang memenuhi $q_i = p_{k_i}$ untuk semua $1 \le i \le L$. Sistem juga memberi tahu saya $N$, yaitu panjang kata sandi saya, dan $S$, yang berarti kata sandi saya hanya menggunakan $S$ huruf pertama dalam alfabet. Sebagai contoh, $S = 4$ berarti kata sandi saya hanya berisi $\text{a}$, $\text{b}$, $\text{c}$, dan $\text{d}$ (tetapi tidak harus memuat semuanya).

Tolong bantu saya memulihkan kata sandi saya!

Detail Implementasi

Soal ini bersifat interaktif. Anda harus mengimplementasikan fungsi

C:    char* guess(int n, int s);
C++:  string guess(int n, int s);
  • Argumen: $N$ dan $S$ sebagaimana dijelaskan di atas.
  • Nilai kembalian: kata sandi yang benar.

Program Anda dapat memanggil fungsi

C:    int query(char* str);
C++:  int query(string str);
  • Argumen: sebuah string berisi $1$ hingga $N$ huruf dari $S$ huruf pertama dalam alfabet.
  • Nilai kembalian: sebuah bilangan bulat antara $0$ hingga panjang str, yang menyatakan jawaban sistem masuk terhadap kueri Anda.
  • Untuk menghindari kesalahan kompilasi, Anda harus mendeklarasikan fungsi ini menggunakan teks persis seperti di atas, di mana saja dalam cakupan global sebelum memanggilnya.
  • Anda boleh memanggil fungsi ini paling banyak $50\,000$ kali untuk setiap kasus uji.

Program Anda boleh mendefinisikan fungsi tambahan.

Contoh Penilai

Sebuah contoh grader.{c,cpp} disediakan agar Anda dapat menguji kode Anda secara lokal. Contoh penilai membaca masukan dari berkas password.in dengan format:

  • baris $1$: $N$ $S$
  • baris $2$: kata sandi

Anda dapat mengompilasi penilai tersebut bersama dengan solusi Anda. Kemudian Anda dapat menjalankan berkas biner yang dihasilkan untuk menguji strategi tebakan Anda terhadap masukan yang diberikan.

Subsoal

Kasus uji dapat dinilai per kelompok. Secara berurutan, subsoalnya adalah:

Subsoal Persentase poin Batasan masukan
1 10% $N \le S \le 26$; semua huruf dalam kata sandi berbeda satu sama lain
2 20% $2 \le N \le 100$ dan $2 \le S \le 4$
3 20% $2 \le N \le 2\,000$ dan $2 \le S \le 20$
4 30% $2 \le N \le 3\,500$
5 20% $2 \le N \le 5\,000$

Contoh

Misalkan kata sandinya adalah $\text{aab}$. Penilai memanggil guess(3, 2). Catatan pemanggilannya mungkin berupa

Pemanggilan Nilai kembalian
guess("ab") 2
guess("abb") 2
guess("bab") 1
guess("aab") 3

Pada titik ini, guess(3, 2) harus mengembalikan "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.