E. Зөв хаалтын дараалал засварлагч

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

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

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

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

Саяхан Поликарп зөвхөн зөв хаалтын дарааллуудтай (CBS гэж товчлоно) ажилладаг текст засварлагч програм хөгжүүлж эхэлсэн.

Зөв хаалтын дараалал гэдэг нь уг дараалал дээр "$+$" ба "$1$"-үүдийг нэмснээр зөв математик илэрхийлэл гаргаж авч болох дарааллыг хэлнэ. Жишээлбэл "$(())()$", "$()$" ба "$(()(()))$" дарааллууд нь зөв ба "$)($", "$(()$" ба "$(()))($" дарааллууд нь буруу юм. "$(()(()))$" хаалтыг жишээ болгон авч үзье:

  • 1-р хаалт 8-р хаалттай хослоно,
  • 2-р хаалт 3-р хаалттай хослоно,
  • 3-р хаалт 2-р хаалттай хослоно,
  • 4-р хаалт 7-р хаалттай хослоно,
  • 5-р хаалт 6-р хаалттай хослоно,
  • 6-р хаалт 5-р хаалттай хослоно,
  • 7-р хаалт 4-р хаалттай хослоно,
  • 8-р хаалт 1-р хаалттай хослоно.

Поликарпийн засварлагч CBS хэрэглэх үедээ зөвхөн гурван үйлдэл л дэмжинэ. Засварлагч дахь курсор нэг хаалтын бүхэл байрлалыг эзлэнэ (хаалтуудын хоорондох зай биш!). Гурван үйлдлийг дэмжинэ:

  • «$L$» -- курсорыг зүүн тийш нэг байрлал шилжүүлнэ,
  • «$R$» -- курсорын баруун тийш нэг байрлал шилжүүлнэ,
  • «$D$» -- курсорын байрлаж буй хаалтыг устгах, энэ хаалттай хослосон хаалт ба эдгээрийн хоорондох бүх хаалтыг устгах (курсор байрласан хаалт болон уг хаалттай хослосон хаалт хоёрын хоорондох дэд тэмдэгт мөрийг устгах).

"$D$" үйлдлийн дараа курсор баруун талын хамгийн ойр хаалтруу шилжинэ (мэдээж устгагдаагүй хаалтруу). Хэрвээ ийм хаалт байхгүй бол (CBS-н дагавар устгагдсан бол) курсор хамгийн ойр зүүн талын хаалтруу шилжинэ (мэдээж устгагдаагүй хаалтруу).

Доорх зурагт "$D$" үйлдлийн хэд хэдэн хэрэглээг дүрсэлсэн байна.

Бүх зөв биш үйлдлүүдийг (курсорыг CBS-н төгсгөлд шилжүүлэх, CBS-г бүхэлд нь устгах гэх мэт) Поликарпийн засварлагч дэмжихгүй.

Поликарп өөрийн хөгжүүлэлтэндээ маш бахархалтай байгаа, та түүний засварлагчийн үйл ажиллагааг хэрэгжүүлж чадах уу?

Оролт

Эхний мөрөнд гурван эерэг бүхэл тоо $n$, $m$ ба $p$ ($2 ≤ n ≤ 500 000$, $1 ≤ m ≤ 500 000$, $1 ≤ p ≤ n$) байх буюу зөв хаалтын дараалал дахь хаалтуудын тоо, үйлдлүүдийн тоо ба курсорын анхны байрлал байна. Дараалал дахь байрлалууд нь зүүнээс баруун тийш нэгээс эхлэн дугаарлагдана. $n$ нь тэгш тоо байх нь тодорхой.

Дараа нь зөв хаалтын дарааллыг бүрдүүлэх $n$ ширхэг "$($" ба "$)$" тэмтэгтүүдээс бүрдсэн тэмдэгт мөр байна.

Тэгээд үйлдлүүдийн дараалал буюу "$L$", "$R$" ба "$D$" тэмдэгтүүдээс бүрдсэн $m$ тэмдэгттэй тэмдэгт мөр байна. Үйлдлүүд эхнээсээ сүүл хүртлээ нэг нэгээрээ гүйцэтгэгдэнэ. Өгөгдсөн үйлдлүүд хэзээ ч курсорыг хаалтуудын дарааллаас гаргахгүй ба бүх үйлдлүүдийн дараа хаалтын дараалал хоосон болохгүй.

Гаралт

Анхны дараалал дээр бүх үйлдлийг гүйцэтгэсний дараа гарах зөв хаалтын дарааллыг хэвлэ.

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

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

Оролт
8 4 5
(())()()
RDLD
Гаралт
()
Оролт
12 5 3
((()())(()))
RRDLD
Гаралт
(()(()))
Оролт
8 8 8
(())()()
LLLLLLDD
Гаралт
()()

Тэмдэглэл

Эхний жишээн дээр курсор анх $5$ байрлалд байсан. Засварлагчийн үйлдлүүдийг авч үзье:

  1. "$R$" комманд -- курсор баруун тийш $6$ байрлалд шилжинэ;
  2. "$D$" комманд -- $5$ байрлалаас $6$ байрлал хүртэлх хаалтуудыг устгана. Үүний дараа CBS $(())()$ хэлбэртэй болно, курсор $5$ байрлалд байна;
  3. "$L$" комманд -- курсор зүүн тийшээ $4$ байрлалд шилжинэ;
  4. "$D$" комманд -- $1$ байрлалаас $4$ байрлал хүртэлх хаалтуудыг устгана. Үүний дараа CBS $()$ хэлбэртэй болно, курсор $1$ байрлалд байна;

Ингээд хариулт $()$-тай тэнцүү.

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