C. Гүйлтийн зам

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Аярат нэртэй хүү AMI-1511 нэртэй гараг дээр амьдардаг. Энэ гарагийн энэхүү оршин суугч нь авъяастай. Ялангуяа Аярат гүйх дуртай ч энэ нь түүнд хангалтгүй санагддаг. Тэр гүйлтийг жинхэнэ урлаг болгохыг мөрөөддөг.

Хамгийн эхэнд тэр гүйлтийн замыг $t$ хучлагаар байгуулахыг хүссэн. Гараг AMI-1511 дээр тус бүрийг нь жижиг англи үсгээр тэмдэглэж өнгийн дарааллаар будсан блокуудаар замыг хучна. Тиймээс хучлага бүр нь цуваа шиг байхаар боловруулсан.

Харамсалтай нь блокуудыг бизнес эрхэлдэггүй үйлчлүүлэгчдэд худалдаггүй ч гэсэн Аярат хязгааргүй $s$ хучлагуудын тоог олсон. Бас түүнд хайч болон цавуу байгаа. Аярат цөөн хэдэн $s$ хучлагыг худалдаж авахаар болж дараа нь тэдгээрийн тус бүрийг таслан нэг хэсгээр (дэд тэмдэгт мөрөөр)нь үргэлжлүүлэн өөрийн замынхаа хучлагын төгсгөл хүртэл нь наасан. Түүгээр ч барахгүй тэр энэ блокыг наахаасаа өмнө эргүүлэн харуулж болно. Аярат түүний гүйлтийн замд худалдан авах шаардлагатай $t$ хучлагыг хучих хамгийн бага $s$ тооны хучлагыг мэдэхийг хүсч байгаа. Мэдээж хэрэг тэр зарим нэг аргаар асуултынхаа хариултыг олж авахыг хүсч байгаа.

Оролт

Оролтын эхний мөрөнд $s$ тэмдэгт мөр байх ба дэлгүүрт байгаа хучлага. Хоёр дахь мөрөнд цуваа $t$ тэмдэгт мөр байх ба Аяратын авахыг хүсч байгаа хучлага. Хоёр тэмдэгт мөрнүүд нь хоосон биш бөгөөд тэдгээрийн урт нь $2100$-аас хэтрэхгүй ба ганцхан жижиг англи үсэгнүүдээс бүтнэ.

Гаралт

Эхний мөрөнд $n$ хучлагануудаас хэрэгтэй тооны хамгийн бага утга байх ба хэрвээ сэтгэлд нийцсэн хучлагыг бүтээж чадахгүй бол $-1$-г хэвлэ.

Хэрвээ хариулт $-1$ биш бол дараах $n$ мөрнүүд нь хоёр бүхэл тоон утгыг агуулсан байх шаардлагатай. $x_{i}$ and $y_{i}$ -- Сүүлчийн блокд харгалзах хэсгийн тоо. Хэрвээ $x_{i}$ ≤ $y_{i}$ бол энэ хэсэг нь ердийн дараалалд хэрэглэгдэх бөгөөд хэрвээ $x_{i}$ > $y_{i}$ бол энэ хэсэг нь эсрэг дараалалд хэрэглэгдэнэ. Тэдний $t$ тэмдэгт мөрийг гарган авахыг тулд наах ёстой хэсгүүдийг хэвлэ.

Орчуулсан: Г. Мэндбаяр

Жишээ тэстүүд

Оролт
abc
cbaabc
Гаралт
2
3 1
1 3
Оролт
aaabrytaaa
ayrat
Гаралт
3
1 1
6 5
8 7
Оролт
ami
no
Гаралт
-1

Тэмдэглэл

Эхний жишээн дэх тэмдэгт мөр "$cbaabc$" = "$cba$" + "$abc$".

Хоёр дахь жишээнд: "$ayrat$" = "$a$" + "$yr$" + "$at$".

Сэтгэгдлүүдийг ачааллаж байна...