Нууц үг
Бодлогын өгүүлбэр
Эчнээ олимпиад - I. 2026-10-17 · Ангилал: Ахлах
Бидний өдөр тутам ашигладаг систем, апп-ын тоо олширч, хэрэглэгчид нууц үгээ мартах явдал түгээмэл болжээ. Би ч гэсэн тэдний нэг болж, нэгэн системд нэвтрэх нууц үгээ мартсан. Харин энэ систем нь зөвхөн латин цагаан толгойн жижиг үсгээр тогтсон нууц үг ашигладаг ба нууц үгээ мартсан тохиолдолд "Нууц үг буруу байна" гэж гардаггүй системээс өөр мэдээлэл өгдөг. Тухайлбал систем нь миний оруулсан тэмдэгт мөр (буруу нууц үг) нууц үгийн ямар нэг дэд дараалал (заавал зэрэгцэн байрлах албагүй) болж байвал түүний хамгийн урт угтварыг (prefix) хэлж өгдөг.
Томъёолбол системийн нууц үг P=p1p2…pN, миний оруулсан тэмдэгт мөр Q=q1q2…qN бол систем дараах нөхцөлийг хангах хамгийн их L тоог танд илгээнэ. Өөрөөр хэлбэл 1≤k1<k2<⋯<kL≤N байх бүх 1≤i≤L-ийн хувьд qi=pki нөхцөлийг хангах k1,k2,…,kL индексүүд олддог байх явдал юм.
Би харин нууц үгийнхээ урт (N) болон цагаан толгойн эхний хэдэн (S) ашигласан болохоо мэдэж байгаа.
Тухайлбал S=4 бол таны жинхэнэ нууц үг зөвхөн a,b,c,d үсгүүдээс тогтох ба эдгээр тэмдэгтүүдийг бүгдийг агуулах албагүй.
Та системээс ирсэн L тоог ашиглан өөрийнхөө нууц үгийг сэргээх программ бичнэ үү.
Хэрэгжүүлэлтийн мэдээлэл
Та дараах функцийг хэрэгжүүлнэ:
cppstring guess(int n, int s);
- Аргумент: n, s нь дээр тайлбарласан N ба S болно
- Буцаах утга: зөв нууц үг
Таны программ дараах функцийг дуудна.
cppint query(string str);
- Аргумент: цагаан толгойн эхний S үсгээс бүрдсэн N урттай тэмдэгт мөр
- Буцаах утга: системийн таны асуултад өгөх хариу болох тоо
Нэг тестэд энэ функцийг 50 000-с ихгүй удаа дуудах ёстой.
Анхаар: Зөвхөн дээрх функцийг бичнэ үү. main функц бичих эсвэл стандарт оролт/гаралт ашиглах шаардлагагүй — grader таны кодыг өөрийн кодтой холбож компайл хийнэ.
Оролтын формат
Шалгагч (grader): grader.cpp жишээ файл өгөгдөх ба дараах байдлаар оролтыг уншина.
- 1-р мөр: N S
- 2-р мөр: нууц үг
Гаралтын формат
Гаралт шаардлагагүй. guess функцийн буцаасан тэмдэгт мөр нь нууц үгтэй яг таарах ёстой.
Хязгаарлалт
- Хугацааны хязгаар: 0.5 секунд
- Санах ойн хязгаар: 512 MB
Дэд даалгавар
| Дугаар | Оноо | Хязгаарлалт |
|---|---|---|
| 1 | 10% | N≤S≤26; нууц үгийн бүх үсэг ялгаатай |
| 2 | 20% | 2≤N≤100, 2≤S≤4 |
| 3 | 20% | 2≤N≤2000, 2≤S≤20 |
| 4 | 30% | 2≤N≤3500 |
| 5 | 20% | 2≤N≤5000 |
Дэд даалгавар бүрийн оноо нь тухайн дэд даалгаврын бүх тест зөв давсан тохиолдолд олгогдоно. Нэг дэд даалгаварт алдаа гарвал бусад дэд даалгаврын оноо хадгалагдана.
Жишээ
3 2 aab
aab
Нууц үг "aab" ба n=3, s=2 бол grader нь guess(3, 2)-г дуудна.
| query(string str) | Буцаах утга | Тайлбар |
|---|---|---|
query("ab") | 2 | a 1-р байрлалд, b 3-т байрлалд байгаа тул ab нь урт угтвар болно |
query("abb") | 2 | a 1-р байрлалд, b 3-р байрлалд байгаа тул урт угтвар ab болно. b дахиж байхгүй |
query("bab") | 1 | b нь 3-р байрлалд байна. Түүний дараа a байхгүй тул зөвхөн b таарсан |
query("aab") | 3 | Бүгд таарсан |
Энэ үед guess(3, 2) нь "aab"-г буцаана.