ฉันลืมรหัสผ่านอีกแล้ว! ตอนนี้ฉันนั่งอยู่หน้าคอมพิวเตอร์และพิมพ์รหัสผ่านผิดซ้ำไปซ้ำมา สิ่งเดียวที่ฉันจำได้คือรหัสผ่านของฉันประกอบด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็กเท่านั้น โชคดีที่ระบบเข้าสู่ระบบตอบกลับมากกว่าแค่คำว่า "รหัสผ่านไม่ถูกต้อง" แต่ยังบอกความยาวของคำนำหน้าที่ยาวที่สุดของข้อมูลที่ฉันป้อนซึ่งปรากฏเป็นลำดับย่อย (ไม่จำเป็นต้องติดกัน) ในรหัสผ่านอีกด้วย กล่าวอย่างเป็นทางการ สำหรับรหัสผ่าน $P = p_1 p_2 \dots p_N$ และข้อมูลที่ป้อน $Q = q_1 q_2 \dots q_N$ คำตอบของระบบเข้าสู่ระบบคือค่า $L$ ที่มากที่สุดซึ่งมีดัชนี $1 \le k_1 < k_2 < \dots < k_L \le N$ ที่ทำให้ $q_i = p_{k_i}$ สำหรับทุก $1 \le i \le L$ นอกจากนี้ ระบบยังบอกค่า $N$ คือความยาวของรหัสผ่านของฉัน และค่า $S$ ซึ่งหมายความว่ารหัสผ่านของฉันใช้เฉพาะตัวอักษร $S$ ตัวแรกของลำดับตัวอักษรเท่านั้น ตัวอย่างเช่น $S = 4$ หมายความว่ารหัสผ่านของฉันประกอบด้วย $\text{a}$, $\text{b}$, $\text{c}$ และ $\text{d}$ เท่านั้น (แต่ไม่จำเป็นต้องมีครบทุกตัว)
ได้โปรดช่วยฉันกู้คืนรหัสผ่านด้วย!
รายละเอียดการเขียนโปรแกรม
โจทย์ข้อนี้เป็นแบบโต้ตอบ คุณต้องเขียนฟังก์ชันต่อไปนี้
C: char* guess(int n, int s);
C++: string guess(int n, int s);
- อาร์กิวเมนต์: $N$ และ $S$ ตามที่อธิบายไว้ข้างต้น
- ค่าที่ส่งกลับ: รหัสผ่านที่ถูกต้อง
โปรแกรมของคุณสามารถเรียกใช้ฟังก์ชันต่อไปนี้
C: int query(char* str);
C++: int query(string str);
- อาร์กิวเมนต์: สตริงความยาวตั้งแต่ $1$ ถึง $N$ ตัวอักษร โดยเลือกจากตัวอักษร $S$ ตัวแรกของลำดับตัวอักษร
- ค่าที่ส่งกลับ: จำนวนเต็มที่มีค่าระหว่าง $0$ ถึงความยาวของ
strซึ่งแทนคำตอบของระบบเข้าสู่ระบบต่อคำถามของคุณ - เพื่อหลีกเลี่ยงข้อผิดพลาดในการคอมไพล์ คุณควรประกาศฟังก์ชันนี้โดยใช้ข้อความข้างต้นทุกประการ ไว้ที่ใดก็ได้ในขอบเขตระดับโกลบอลก่อนเรียกใช้งาน
- คุณสามารถเรียกใช้ฟังก์ชันนี้ได้ ไม่เกิน $50\,000$ ครั้ง ต่อหนึ่งชุดข้อมูลทดสอบ
โปรแกรมของคุณสามารถนิยามฟังก์ชันเพิ่มเติมได้
โปรแกรมตรวจคำตอบตัวอย่าง
มีไฟล์ตัวอย่าง grader.{c,cpp} เตรียมไว้ให้คุณใช้ทดสอบโค้ดบนเครื่องของคุณเอง โปรแกรมตรวจคำตอบตัวอย่างจะอ่านข้อมูลนำเข้าจากไฟล์ password.in ตามรูปแบบดังนี้:
- บรรทัดที่ $1$: $N$ $S$
- บรรทัดที่ $2$: รหัสผ่าน
คุณสามารถคอมไพล์โปรแกรมตรวจคำตอบร่วมกับโค้ดคำตอบของคุณ จากนั้นจึงรันไฟล์ไบนารีที่ได้เพื่อทดสอบกลยุทธ์การเดารหัสผ่านกับข้อมูลนำเข้าที่กำหนด
งานย่อย
ชุดข้อมูลทดสอบอาจ คิดคะแนนเป็นกลุ่ม งานย่อยเรียงตามลำดับมีดังนี้:
| งานย่อย | สัดส่วนคะแนน | ข้อจำกัดของข้อมูลนำเข้า |
|---|---|---|
| 1 | 10% | $N \le S \le 26$; ตัวอักษรทุกตัวในรหัสผ่านแตกต่างกันทั้งหมด |
| 2 | 20% | $2 \le N \le 100$ และ $2 \le S \le 4$ |
| 3 | 20% | $2 \le N \le 2\,000$ และ $2 \le S \le 20$ |
| 4 | 30% | $2 \le N \le 3\,500$ |
| 5 | 20% | $2 \le N \le 5\,000$ |
ตัวอย่าง
สมมติว่ารหัสผ่านคือ $\text{aab}$ โปรแกรมตรวจคำตอบจะเรียก guess(3, 2) บันทึกการเรียกฟังก์ชันอาจเป็นดังนี้
| การเรียก | ค่าที่ส่งกลับ |
|---|---|
guess("ab") |
2 |
guess("abb") |
2 |
guess("bab") |
1 |
guess("aab") |
3 |
ณ จุดนี้ guess(3, 2) ควรส่งกลับค่า "aab"