Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
C. Зөв хаалтын дараалал үүсгэх
хугацааны хязгаарлалт 1 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Танд дөрвөн төрлийн нээх болон хаах хаалтуудаас $<>$, ${}$, $[]$, $()$ бүрдсэн $s$ урттай тэмдэгт мөр өгөгдсөн. Хоёр төрлийн хаалт байна: нээх ба хаах. Та дурын хаалтыг ижил төрлийн хаалтаар сольж чадна. Жишээлбэл та $<$ хаалтыг { хаалтаар сольж чадах боловч $)$ эсвэл $>$ хаалтаар сольж чадахгүй.
Зөв хаалтны дарааллын дараах тайлбарыг ихэнх хүмүүс мэддэг учир танд ойр санагдах болно.
Зөв хаалтын дарааллыг (RBS) тодорхойлцгооё. Хоосон тэмдэгт мөр RBS байна. $s_{1}$ ба $s_{2}$ нь RBS байг тэгвэл <$s_{1}$>$s_{2}$, {$s_{1}$}$s_{2}$, [$s_{1}$]$s_{2}$, ($s_{1}$)$s_{2}$ тэмдэгт мөрүүд ч мөн RBS байна.
Жишээлбэл "$[[(){}]<>]$" тэмдэгт мөр нь RBS боловч "$[)()$" болон "$][()()$" тэмдэгт мөрүүд нь RBS биш.
$s$ тэмдэгт мөрийг RBS болгохын тулд солих үйлдлийн хамгийн бага тоог ол.
Оролт
Нэг мөрөнд зөвхөн дөрвөн төрлийн нээх болон хаах хаалтуудаас бүрдэх хоосон биш тэмдэгт мөр $s$ байна. $s$ тэмдэгт мөрийн урт $10^{6}$-с ихгүй байна.
Гаралт
Хэрвээ $s$-с RBS үүсгэх боломжгүй бол $Impossible$ гэж хэвлэ.
Бусад тохиолдолд $s$-г RBS болгоход шаардлагатай солих үйлдлийн хамгийн бага тоог хэвлэ.
Орчуулсан: Г.Мэндбаяр
Жишээ тэстүүд
Оролт
[<}){}
Гаралт
2
Оролт
{()}[]
Гаралт
0
Оролт
]]
Гаралт
Impossible