Codeforces Round #803 (Div. 2)
22:47:44 |
Codeforces Round #804 (Div. 2)
6 өдрийн дараа |
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$".