B. Даалууны нөлөө

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

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

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

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

Бяцхан Крис даалуу тоглохыг хөгжилтэй биш гэдгийг мэддэг, тэр даалуу нь хэтэрхий санамсаргүй буюу чадвар шаарддаггүй гэж боддог. Үүний оронд Крис даалуунуудаар "даалууны үзүүлбэр" хийж тоглохоор шийдсэн.

Крис $n$ даалууг шулуун дээр өрсөн, даалуу бүрийг босоогоор байрлуулсан. Эхэндээ зарим даалууг зүүн эсвэл баруун тийш түлхсэн. Ижил чиглэлд түлхэгдсэн хоёр даалуу бүрийн хооронд ядаж нэг эсрэг чиглэлд түлхэгдсэн даалуу байна.

Секунд бүрийн дараа зүүн тийшээ унаж буй даалуу бүр хөрш зүүн талын даалууг зүүн тийш түлхэнэ. Үүнтэй адилаар баруун тийшээ унаж буй даалуунууд баруун талд босоогоороо байгаа даалуунуудыг баруун тийш түлхэнэ. Хэрвээ босоо байгаа даалууруу хоёр талаас нь даалуу унаж байвал энэ даалуу хүчнүүдийн тэнцвэрийг хадгалж үлдэнэ. Зурагт үйл явдлын боломжит нэг жишээг харуулсан байна.

Крисын түлхсэн даалуунуудын анхны чиглэл өгөгдсөн бол үйл явдлын төгсгөлд босоогоороо үлдэх даалуунуудын тоог ол.

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 3000$) байх буюу шулуун дээр байгаа даалуунуудын тоо. Дараагийн мөрөнд $n$ урттай тэмдэгт мөр $s$ байна. Тэмдэгт мөрийн $i$-р тэмдэгт $s_{i}$ нь:

  • хэрвээ $i$-р даалуу зүүн тийш түлхэгдсэн бол "$L$";
  • хэрвээ $i$-р даалуу баруун тийш түлхэгдсэн бол "$R$";
  • хэрвээ $i$-р даалуу түлхэгдээгүй бол "$.$"-тэй тэнцүү байна.

Хэрвээ $s_{i} = s_{j} = $"$L$" ба $i < j$ байвал $i < k < j$ ба $s_{k} = $"$R$" байх $k$ оршин байна; хэрвээ $s_{i} = s_{j} = $"$R$" ба $i < j$ байвал $i < k < j$ and $s_{k} = $"$L$" байх $k$ оршин байх нь тодорхой.

Гаралт

Үйл явдлын дараа босоо хэвээрээ үлдэх даалуунуудын тоог илэрхийлэх нэг ширхэг бүхэл тоон утгыг хэвлэ.

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

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

Оролт
14
.L.R...LR..L..
Гаралт
4
Оролт
5
R....
Гаралт
0
Оролт
1
.
Гаралт
1

Тэмдэглэл

Эхний жишээний тохиолдлыг зурагт үзүүлсэн байна. Улбар шар өнгөөр тодруулсан дөрвөн даалуу босоо хэвээрээ үлдэнэ.

Хоёр дахь жишээн дээр эхний даалуу бусад бүх даалууг унагах учир бүх даалуу унана.

Сүүлийн жишээн дээр нэг ширхэг даалуу аль ч чиглэлд түлхэгдээгүй байна.

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