B. Код задлах

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

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

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

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

Бяцхан Витали ялгаатай алгоритмуудад дуртай. Өнөөдөр тэр танд зориулж шинэ алгоритм зохиосон. Виталигийн алгоритм "$x$" ба "$y$" тэмдэгтүүдээс тогтсон $s$ тэмдэгт мөртэй ажилладаг ба ажиллах үедээ дараах хоёр үйлдлийг ашигладаг:

  1. Тэмдэгт мөрөөс эхний үсэг нь $y$ хоёр дахь үсэг нь $x$ байх дараалласан хоёр тэмдэгтийг олж байрыг нь солих. Хэрвээ тохиромжтой хэд хэдэн хос тэмдэгт байвал бид тэмдэгт мөрийн эхлэлтэй хамгийн ойр байгаа хос тэмдэгтийг сонгоно.
  2. Тэмдэгт мөрөөс эхний үсэг нь $x$ хоёр дахь үсэг нь $y$ байх дараалласан хоёр тэмдэгтийг олно. Эдгээр тэмдэгтүүдийг тэмдэгт мөрөөс устгана. Хэрвээ тохиромжтой хэд хэдэн хос тэмдэгт байвал бид тэмдэгт мөрийн эхлэлтэй хамгийн ойр байгаа хос тэмдэгтийг сонгоно.

Шинэ алгоритмын оролт нь $s$ тэмдэгт мөр ба алгоритм дараах байдлаар ажиллана:

  1. Хэрвээ та тэмдэгт мөр дээр тодорхойлсон үйлдлүүдийн ядаж нэгийг нь хийх боломжтой байвал алхам 2 дээр очно. Бусад тохиолдолд алгоритмыг зогсоогоод одоо байгаа тэмдэгт мөрийг хэвлэнэ.
  2. Хэрвээ та 1 дугаартай үйлдлийг хийх боломжтой бол хийнэ. Бусад тохиолдолд 2 дугаартай үйлдлийг хийнэ. Та үйлдэл хийснийхээ дараа алгоритмын алхам 1 дээр очно.

Одоо Витали хэрвээ оролтонд $s$ тэмдэгт мөр ирсэн бол алгоритмын ажиллагааны үр дүнд юу хэвлэгдэх вэ гэж бодож байна.

Оролт

Эхний мөрөнд хоосон биш тэмдэгт мөр $s$ байна.

Тэмдэгт мөр зөвхөн "$x$" ба "$y$" тэмдэгтүүдээс тогтоно. Тэмдэгт мөр хамгийн ихдээ $10^{6}$ тэмдэгтээс тогтоно. Алгоритмын ажиллагааны үр дүнд хоосон тэмдэгт мөр үлдэхгүй.

Гаралт

Алгоритмын ажиллагааны үр дүнд үүсэх тэмдэгт мөрийг нэг мөрөнд хэвлэ.

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

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

Оролт
x
Гаралт
x
Оролт
yxyxy
Гаралт
y
Оролт
xxxxxy
Гаралт
xxxx

Тэмдэглэл

Эхний жишээн дээр алгоритм маань ямар ч үйлдэл гүйцэтгэх боломжгүй учир алгоритмын эхний алхмын дараа дуусна. Иймээс тэмдэгт мөр өөрчлөгдөхгүй.

Хоёр дахь жишээн дээр өөрчлөлт дараах байдалтай харагдана:

  1. "$yxyxy$" тэмдэгт мөр "$xyyxy$" болно;
  2. "$xyyxy$" тэмдэгт мөр "$xyxyy$" болно;
  3. "$xyxyy$" тэмдэгт мөр "$xxyyy$" болно;
  4. "$xxyyy$" тэмдэгт мөр "$xyy$" болно;
  5. "$xyy$" тэмдэгт мөр "$y$" болно.

Үр дүнд нь бид "$y$" тэмдэгт мөртэй болно.

Гурав дахь жишээн дээр нэг өөрчлөлт явагдах буюу "$xxxxxy$" тэмдэгт мөр "$xxxx$" болно. Ингээд хариулт "$xxxx$" байна.

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