F. Ахиад л хаалтын дараалал

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

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

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

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

Поликарпус-д нээх болон хаах хаалтуудын хязгаартай дараалал байв. Хичээл дээрээ унтахгүйн тулд Поликарпус уг дарааллаар тоглохоор шийджээ. Тэрээр 2 үйлдэл хийж болно:

  • ямар ч байрлалд хаалт нэмж болно (эхлэл, төгсгөл эсвэл 2 хаалтын хооронд);
  • цикл шилжүүлэлт -- та уг дарааллын сүүлийн хаалтыг дарааллын эхэнд шилжүүлэн авчирна.

Поликарпус уг дараалалд эдгээр үйлдлүүдийг хэдэн ч удаа хийж болох ба ямар ч дарааллаар цикл шилжүүлэлт хийж болно. Үр дүнд нь тэрээр боломжит хамгийн бага урттай зөв хаалтын дараалалтай болохыг хүсэж байгаа юм. Хэрэв тийм дараалал хэд хэд байвал Поликарпус хэл зүйн дарааллаар хамгийн багийг нь сонгох юм. Түүнд тийм дараалал олоход тусална уу.

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

Хэрэв $1$-ээс $n$-ын хүртэлх тоонуудаас $1 ≤ k < i$-ын хувьд $a_{k} = b_{k}$ болон $a_{i} < b_{i}$ байх $i$ тоо оршин байвал $a_{1}$ $a_{2}... a_{n}$ дарааллыг $b_{1}$ $b_{2}... b_{n}$ дарааллаас хэл зүйн хувьд бага байна гэж үзнэ. "(" $ < $ ")" гэж үзнэ үү.

Оролт

Эхний мөрөнд "(" болон ")" тэмдэгтүүдээс тогтох Поликарпус-ын дараалал өгөгдөнө. Уг мөр нь $1$-ээс $1 000 000$ хүртэл урттай байна.

Гаралт

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

Орчуулсан: Баатархүү

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

Оролт
()(())
Гаралт
(())()
Оролт
()(
Гаралт
(())

Тэмдэглэл

Эхний жишээний дараалал нь аль хэдийн зөв байна. Гэхдээ хэл зүйн хувьд хамгийн багийг гаргаж авахын тулд та 4-н ширхэг цикл шилжүүлэлт үйлдэл хийх хэрэгтэй. 2-дахь жишээнд та 2-р болон 3-р хаалтын хооронд хаах хаалт нэмэх хэрэгтэй ба нэг удаа цикл шилжүүлэлт хийх юм. Та эхлээд шилжүүлэлтээ хийж болох ба дараа нь төгсгөлийн хэсэгт хаалтаа нэмэх юм.

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