Олонлог Эгзэ сургуулийн сурагчид student.exe нэртэй WiFi -д холбогдохын тулд кодлогдсон мөрийг тайлж чадсанаар уг WiFi-ийн нэвтрэх нууц үгийг ашиглан интернетэд нэвтрэх боломжтой байдаг.

Сургууль нь сурагчиддаа WiFi-д нэвтрэх нууц кодыг гаргаж өгсөн. Энэ кодыг шууд ашиглаж болохгүй — эхлээд "засах" хэрэгтэй байдаг.

Та энэ кодоос зарим үсгүүдийг алгасаж, дарааллыг нь өөрчлөхгүйгээр шинэ дараалал (subsequence) үүсгэж болно.

Даалгавар

Танд нэг код бүхий s мөр өгөгдөнө.

Та дараах үйлдлүүдийг хийж болно:

Үсэг алгасах

• Дурын үсгүүдийг хасаж болно
• Гэхдээ үлдсэн үсгүүдийн дараалалыг өөрчлөхгүй
• Энэ нь subsequence үүсгэнэ

Үсэг өөрчлөх (хамгийн ихдээ K удаа)

• Нэг үсгийг дурын өөр үсэг болгож болно
• Энэ нь кодыг "засах" үйлдэл юм

WiFi-д нэвтрэх нөхцөл

Таны үүсгэсэн код:

• Palindrome байх ёстой
  (урдаас хойш, хойноос урагшаа адил)

Зорилго

• Хамгийн ихдээ K өөрчлөлт ашиглан
• Үүсгэж болох хамгийн урт palindrome subsequence -ийн урт болох тоогоор нь WiFi-ийг кодлосон байгаа

Оролт:

Эхний мөрөнд: s

хоёр дахь мөрөнд: K

• s — нууц код (string)
• K — засах боломжтой үсгийн тоо

Гаралт:

хамгийн урт palindrome subsequence-ийн урт

Хязгаарлалтууд:

• 1 ≤ |s| ≤ 200
• 0 ≤ K ≤ 200
• s нь зөвхөн жижиг латин үсгүүд (a–z)

Дэд бодлого

Жишээ:

Оролт-1

abca
1

Гаралт-1

4

Тайлбар-1

• Код: abca
• c → b болгож өөрчилбөл:

abba

• Энэ нь palindrome → WiFi unlock ✅
• Урт = 4

Оролт-2

abcdef
2

Гаралт-2

5

Тайлбар-2

• Жишээ:
  • abcde → abcba (2 өөрчлөлт)
• palindrome → урт = 5

Оролт-3

aaaa
0

Гаралт-3

4

Тайлбар

• Аль хэдийн зөв код
• Бүх үсгийг ашиглаж болно