Нууц үг

500ms

512MB

1800

InteractiveString

Систем хэрэглэгчийн нууц үгийг зөвхөн латин цагаан толгойн эхний $S$ жижиг үсгээр тогтоодог. Та нууц үгийнхээ урт $N$ болон цагаан толгойн хэмжээ $S$ -ийг мэдэх боловч нууц үгээ мартжээ.

Систем таны оруулсан тэмдэгт мөр нь нууц үгийн дэд дараалал (заавал зэрэгцэн байрлах албагүй) болж байвал түүний хамгийн урт угтварын уртыг хэлж өгдөг. Өөрөөр хэлбэл query(t) нь $t$ -ийн хамгийн урт угтвар болох, нууц үгийн дэд дараалал байх угтварын уртыг буцаана.

Та системээс ирэх хариултуудыг ашиглан нууц үгийг сэргээх программ бичнэ үү.

Хэрэгжүүлэлт

Та дараах функцийг хэрэгжүүлнэ:

cpp
string guess(int n, int s);

n — нууц үгийн урт $N$ ;
s — цагаан толгойн эхний хэдэн үсэг ашиглагдсан $S$ ;
Буцаах утга — зөв нууц үг: урт нь n, зөвхөн эхний s жижиг латин үсгээс тогтоно.

Таны программ дараах функцийг дуудна:

cpp
int query(string str);

query(str) нь str-ийн хамгийн урт угтварын уртыг буцаана, хэрэв энэ угтвар нууц үгийн дэд дараалал бол. Нэг тестэд query-г хамгийн ихдээ 50 000 удаа дуудаж болно.

Анхаар: Зөвхөн дээрх функцийг бичнэ үү. main функц бичих эсвэл стандарт оролт/гаралт ашиглах шаардлагагүй — grader таны кодыг өөрийн кодтой холбож компайл хийнэ.

Жишээ

n = 3, s = 2, нууц үг aab үед:

Дуудлага	Буцаах утга	Тайлбар
`query("ab")`	2	`a` 1-р байрлалд, `b` 3-р байрлалд байна
`query("abb")`	2	`ab` таарна, дараагийн `b` байхгүй
`query("bab")`	1	`b` 3-р байрлалд; түүний дараа `a` байхгүй
`query("aab")`	3	Бүх тэмдэгт таарна

Тиймээс guess(3, 2) нь "aab"-г буцаана.

Оролтын формат

Оролтыг grader уншина: эхний мөрөнд $N$ ба $S$ , хоёр дахь мөрөнд нууц үг. Таны програм оролтыг унших шаардлагагүй.

Гаралтын формат

Гаралт шаардлагагүй. guess функцийн буцаасан тэмдэгт мөр нууц үгтэй яг таарах ёстой.

Хязгаарлалт

$2 \le N \le 5000$
$2 \le S \le 26$
Нэг тестэд query дуудлагын тоо $\le 50\,000$
Хугацааны хязгаар: 0.5 секунд
Санах ойн хязгаар: 512 MB

Дэд даалгавар

№	Оноо	Хязгаарлалт
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 2000$ , $2 \le S \le 20$
4	30%	$2 \le N \le 3500$
5	20%	$2 \le N \le 5000$

Дэд даалгавар бүрийн оноо нь тухайн дэд даалгаврын бүх тест зөв давсан тохиолдолд олгогдоно. Нэг дэд даалгаварт алдаа гарвал бусад дэд даалгаврын оноо хадгалагдана.

Жишээ

Оролт1

3 2
aab

Гаралт1

aab

query("ab") = 2, query("abb") = 2, query("bab") = 1, query("aab") = 3. Тиймээс guess(3, 2) нь "aab"-г буцаана.

0.4 / 64 KiB

Редактор уншиж байна...