Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
E. Хоёртын түлхүүр
хугацааны хязгаарлалт 4 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Бидэнд хайрцаг ба түлхүүрийг илэрхийлэх $p$, $q$ гэсэн хувьсагчид ($q$ хувьсагч нь зөвхөн "0" ба "1" тэмдэгтүүдээс тогтоно) байгаа болог. Түлхүүрийг ашиглан хайрцагнаас нууцлагдсан зурвасыг дараах алгоритмаар гарган авдаг байя:
i = 0;
j = 0;
s = <>;
давталт (i нь p тэмдэгт мөрийн уртаас бага бол)
{
хэрэв (q[j] == 1) бол, s тэмдэгт мөрийн баруун талд p[i] тэмдэгтийг нэм;
i, j хувьсагчуудын утгыг 1-ээр нэм;
хэрэв (j хувьсагчийн утга q тэмдэгт мөрийн урттай тэнцүү) бол, j = 0;
}
Өгөгдсөн псевдо кодонд $i$, $j$ нь бүхэл тоон утга, $s$ нь тэмдэгт мөр, '=
' нь утга оноох үйлдэл, '==
' нь харьцуулах үйлдэл, '[]
' тухайн дугаар дахь тэмдэгтийг заах зүйлдэл, '<>
' нь хоосон тэмдэгт мөр болно. Бид бүх тэмдэгт мөр дэх тэмдэгтүүд нь 0-ээс эхлэн дугаарлагдсан гэж үзэв.
Энэ алгоритмыг програмчилж бичих нь амархан харагдаж байгаа биз. Тиймээс таны даалгавар арай өөр байх буюу өгөгдсөн $p$ хайрцагнаас $s$ зурвасыг гарган авж болох $k$ урттай түлхүүрүүдээс цагаан толгойн дарааллаараа хамгийн эхэнд байхыг нь олох юм. Зарим тохиолдолд ийм шаардлагыг хангах түлхүүр олдохгүй байж болно.
Оролт
Оролтын эхний $2$ мөрөнд харгалзан хайрцаг ба зурвасыг илтгэх $p$, $s$ тэмдэгт мөрүүд ($1 ≤ |p| ≤ 10^{6}$, $1 ≤ |s| ≤ 200$) өгөгдөнө. Эдгээр тэмдэгт мөрүүд нь $32$-оос $126$ хүртэлх ASCII кодтой ямар ч тэмдэгтийг агуулж болно.
$3$ дахь мөрөнд түлхүүрийн урт болох нэг бүхэл тоо $k$ ($1 ≤ k ≤ 2000)$ байна.
Гаралт
Хайж буй түлхүүрийг хэвлэнэ. Түлхүүр нь $k$ урттай, зөвхөн "0", "1" тэмдэгтүүдээс тогтсон тэмдэгт мөр байх ёстой. Хэрэв түлхүүр олдохгүй бол дан ганц "0" тэмдэгтийг хэвлэнэ.
Орчуулсан: Солонго
Жишээ тэстүүд
Оролт
abacaba aba 6
Гаралт
100001
Оролт
abacaba aba 3
Гаралт
0
Тэмдэглэл
$x = x_{1}x_{2} ... x_{p}$ ба $y = y_{1}y_{2}... y_{q}$ гэсэн хоёр тэмдэгт мөрийн хувьд дараах тохиолдлуудын аль нэг нь биелэж байвал $x$ тэмдэгт мөрийг $y$-ээс цагаан толгойн дарааллын хувьд эхэнд байна гэж үзнэ:
$p < q$ ба $x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{p} = y_{p}$ байвал
$x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{r} = y_{r}$ ба $x_{r+1} < y_{r+1}$ байх $(0 ≤ r < min(p, q))$ байх $r$ бүхэл тоо оршин байвал (Тэмдэгтүүд нь ASCII кодын дугаараараа эрэмбэлэгдэнэ).