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