АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Шерлок Холмес өөрийн заналт дайсан Професор Мориарти дахин ямар нэг хорон төлөвлөгөө боловсруулж байх вий гэж сэжиглэж эхлэв.

Шерлокийн туслах Доктор Ватсон Мориартийг MI6-ийн супер компьютер Араатангийн асуудалд холбоотой байх хэмээн таамаглав.

Шерлок удалгүй мөрдлөг явуулж эхэлтэл Мориартигаас Араатанд вирус суулгаснаа бахдалтайгаар зарласан захидал хүлээн авлаа.

Мориарти түүнд бяцхан түлхүүр болох бүхэл тоо өгөв.

Шерлок вирусыг устгахын тулд Мориартигийн өгсөн тоотой ижил тооны цифртэй хамгийн их “Decent тоо”-г олох хэрэгтэй гэж тогтоов.

“Decent тоо” гэдэг нь доорх нөхцөлийг бүгдийг хангасан байна:

Мориартигийн вирус нь Араатангийн дэлгэц дээр урвуу тоолж буй цаг харуулах бөгөөд энэ нь Шерлокт хэр хугацаа үлдсэнийг сануулна.

Таны даалгавар бол Араатанг устахаас өмнө нууц үгийг олох юм.

Жишээ нь

55533333 болон 555555 нар нь “Decent тоо” юм. Учир нь эхний тоонд 3 ширхэг 5-ийн тоо болон 5 ширхэг 3-ийн тоо байна.

Харин хоёр дахь тоонд 6 ширхэг 5-ийн тоо байна. Эдгээр тоонууд нь хоёулаа тухайн урттай хамгийн их боломжит тоо юм.

Функцийн тайлбар

DecentNumber гэдэг функцийг бичнэ үү. Өгөгдсөн урттай “Decent тоо”-г эсвэл боломжгүй бол -1 ийг хэвлэх үүрэгтэй.

DecentNumber доорх өгөгдөлийг хүлээн авна

• N: бүхэл тоо ба энэ нь “Decent тоо”-ний уртыг илэрхийлнэ

Оролтын бүтэц

Эхний мөрөнд бүхэл тоо , t , тестийн тоо

Дараагийн t  мөрөнд бүхэл тоо , N , тооний урт буюу цифрийн тоо

Хязгаарлалт

1 <= t<= 20

1 <= n <= 100,000

Гаралтын бүтэц

“Decent тоо”-г эсвэл боломжгүй бол -1 ийг хэвлэ.

Жишээ

Оролт

4

1

3

5

11

Гаралт

-1

555

33333

55555533333

Тайлбар

N=1 үед 1 оронтой decent тоо байхгүй тул -1

N=3 үед 555 бол цор ганц боломжит decent тоо (Decent тоо-ний 3-р нөхцөл).

N=5 үед 33333 бол цор ганц боломжит decent тоо (Decent тоо-ний 2-р нөхцөл).

N=11 үед 55555533333 бол decent тоо. Эдгээр цифрүүдийн бусад бүх сэлгэмэл нь decent тоо биш. (Decent тоо-ний 4-р нөхцөл).

Орчуулсан : Б.Мөнхбаяр АНУ